C++中如何实现图的表示与存储_产品动态_资讯中心

发布时间:2026-04-27 19:00:50

阅读量:1

在C++中，可以使用邻接矩阵或邻接表来表示和存储图。

邻接矩阵表示法：

#include 
#include 

using namespace std;

const int MAX_V = 100;

// 邻接矩阵表示图
class Graph {
private:
    int V; // 图中顶点数
    int E; // 图中边数
    int adj[MAX_V][MAX_V]; // 邻接矩阵

public:
    Graph(int V) {
        this->V = V;
        this->E = 0;
        for(int i = 0; i < V; i++) {
            for(int j = 0; j < V; j++) {
                adj[i][j] = 0;
            }
        }
    }

    void addEdge(int v, int w) {
        adj[v][w] = 1;
        adj[w][v] = 1;
        E++;
    }

    void printGraph() {
        for(int i = 0; i < V; i++) {
            for(int j = 0; j < V; j++) {
                cout << adj[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.printGraph();

    return 0;
}

邻接表表示法：

#include 
#include 

using namespace std;

// 邻接表表示图的边
struct Edge {
    int dest; // 目标顶点
};

// 邻接表表示图的顶点
struct Vertex {
    vector edges; // 与该顶点相连的边
};

// 邻接表表示图
class Graph {
private:
    int V; // 图中顶点数
    vector adjList; // 邻接表

public:
    Graph(int V) {
        this->V = V;
        adjList.resize(V);
    }

    void addEdge(int v, int w) {
        Edge edge1 = {w};
        adjList[v].edges.push_back(edge1);

        Edge edge2 = {v};
        adjList[w].edges.push_back(edge2);
    }

    void printGraph() {
        for(int i = 0; i < V; i++) {
            cout << i << ": ";
            for(int j = 0; j < adjList[i].edges.size(); j++) {
                cout << adjList[i].edges[j].dest << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.printGraph();

    return 0;
}