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

什么是图？

图由顶点（Vertex）和边（Edge）组成。如果边有方向，则称为有向图；否则为无向图。根据边是否带有权重，又可分为带权图和无权图。

1. 邻接矩阵（Adjacency Matrix）

邻接矩阵使用一个二维数组来表示图。假设图有 n 个顶点，则创建一个 n × n 的矩阵 adj[n][n]。如果顶点 i 和顶点 j 之间有边，则 adj[i][j] = 1（无权图）或 adj[i][j] = weight（带权图）；否则为 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 printGraph() {        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.printGraph();    return 0;}

2. 邻接表（Adjacency List）

邻接表使用一个数组（或向量）存储所有顶点，每个顶点对应一个链表（或动态数组），用于存储与其相邻的所有顶点。这是处理稀疏图更高效的方式。

优点：

• 空间复杂度低，为 O(V + E)，其中 E 是边数
• 适合稀疏图

缺点：

• 判断两个顶点是否相连需要遍历链表，时间复杂度为 O(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 printGraph() {        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.printGraph();    return 0;}

如何选择？

- 如果图是稠密图（边数接近 V²），使用邻接矩阵更合适。
- 如果图是稀疏图（边数远小于 V²），推荐使用C++邻接表以节省内存。

总结

本文详细介绍了图数据结构实现的两种核心方法：邻接矩阵和邻接表，并提供了完整的 C++ 代码示例。无论你是算法竞赛选手还是软件开发初学者，掌握这两种表示方法都是迈向高级图算法（如 DFS、BFS、Dijkstra 等）的重要基础。

记住：C++图的表示方法没有绝对的好坏，关键在于根据实际问题选择合适的结构。希望这篇教程能帮助你轻松入门图论编程！