C++图数据结构详解（从零开始掌握图的表示与实现）

图的两种表示方法

在 C++ 中，图主要有两种表示方式：邻接矩阵 和 邻接表。它们各有优缺点，适用于不同场景。

1. 邻接矩阵（Adjacency Matrix）

邻接矩阵使用一个二维数组来表示图。如果顶点 i 和顶点 j 之间有边，则 matrix[i][j] = 1（或边的权重），否则为 0。

优点：查询两个顶点是否相连的时间复杂度为 O(1)。
缺点：空间复杂度高，为 O(V²)，其中 V 是顶点数量，不适合稀疏图（边很少的图）。

下面是一个用 邻接矩阵C++ 实现无向图的简单示例：

#include <iostream>#include <vector>using namespace std;class Graph {private:    int V; // 顶点数量    vector<vector<int>> adjMatrix;public:    Graph(int vertices) : V(vertices) {        adjMatrix.resize(V, vector<int>(V, 0));    }    // 添加边    void addEdge(int u, int v) {        adjMatrix[u][v] = 1;        adjMatrix[v][u] = 1; // 无向图，对称    }    // 打印邻接矩阵    void print() {        for (int i = 0; i < V; ++i) {            for (int j = 0; j < V; ++j) {                cout << adjMatrix[i][j] << " ";            }            cout << endl;        }    }};int main() {    Graph g(4);    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 2);    g.addEdge(2, 3);    cout << "邻接矩阵表示：\n";    g.print();    return 0;}

2. 邻接表（Adjacency List）

邻接表使用一个数组（或 vector）存储每个顶点的邻接顶点列表。通常用 vector 的 vector 或链表实现。

优点：节省空间，尤其适合稀疏图，空间复杂度为 O(V + E)，E 是边数。
缺点：判断两个顶点是否相连需要遍历邻接表，时间复杂度为 O(degree)，degree 是该顶点的度数。

这是 邻接表C++ 的实现方式：

#include <iostream>#include <vector>using namespace std;class Graph {private:    int V;    vector<vector<int>> adjList;public:    Graph(int vertices) : V(vertices) {        adjList.resize(V);    }    // 添加边    void addEdge(int u, int v) {        adjList[u].push_back(v);        adjList[v].push_back(u); // 无向图    }    // 打印邻接表    void print() {        for (int i = 0; i < V; ++i) {            cout << "顶点 " << i << ": ";            for (int neighbor : adjList[i]) {                cout << neighbor << " ";            }            cout << endl;        }    }};int main() {    Graph g(4);    g.addEdge(0, 1);    g.addEdge(0, 2);    g.addEdge(1, 2);    g.addEdge(2, 3);    cout << "邻接表表示：\n";    g.print();    return 0;}

如何选择表示方法？

- 如果图是稠密图（边很多，接近 V²），使用 邻接矩阵C++ 更高效。
- 如果图是稀疏图（边很少），使用 邻接表C++ 节省内存。

总结

通过本教程，你已经掌握了 C++图数据结构 的基本概念和两种核心表示方法。邻接矩阵适合快速查询，邻接表适合节省空间。理解这些基础，是学习图算法（如 DFS、BFS、Dijkstra 等）的第一步。

建议动手编写代码，尝试添加带权边、有向图等功能，加深理解。祝你在图论的世界里探索愉快！