C++语言图算法入门教程（从零开始掌握图的表示与遍历）

图的表示方法

在 C++ 中，常用的图表示方法有两种：邻接矩阵和邻接表。

1. 邻接矩阵（Adjacency Matrix）

使用一个二维数组 graph[i][j] 表示顶点 i 和 j 是否相连。若相连，值为 1（或边的权重）；否则为 0。

// 无向图的邻接矩阵表示（5个顶点）const int V = 5;int graph[V][V] = {    {0, 1, 1, 0, 0},    {1, 0, 1, 1, 0},    {1, 1, 0, 1, 1},    {0, 1, 1, 0, 1},    {0, 0, 1, 1, 0}};

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

2. 邻接表（Adjacency List）

使用一个数组（或 vector）存储每个顶点的邻居列表。这是更常用的方法，尤其适合稀疏图。

#include <vector>using namespace std;// 使用 vector 实现邻接表vector<vector<int>> adjList(5);// 添加边（无向图）adjList[0].push_back(1);adjList[1].push_back(0);adjList[0].push_back(2);adjList[2].push_back(0);// ... 其他边类似添加

优点：节省空间，空间复杂度为 O(V + E)，其中 E 是边数。
缺点：判断两顶点是否相连需遍历邻居列表，时间复杂度为 O(degree)。

图的遍历算法

遍历图是图算法的基础。最常用的两种方法是：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索（DFS）

DFS 从一个起点出发，沿着一条路径尽可能深入，直到无法继续为止，然后回溯。

#include <iostream>#include <vector>using namespace std;void DFS(vector<vector<int>>& adj, vector<bool>& visited, int node) {    visited[node] = true;    cout << node << " ";        for (int neighbor : adj[node]) {        if (!visited[neighbor]) {            DFS(adj, visited, neighbor);        }    }}int main() {    vector<vector<int>> adj(5);    // 构建图（略）    vector<bool> visited(5, false);    DFS(adj, visited, 0); // 从顶点0开始遍历    return 0;}

广度优先搜索（BFS）

BFS 从起点开始，逐层向外扩展，先访问所有距离为1的顶点，再访问距离为2的，依此类推。通常使用队列实现。

#include <iostream>#include <vector>#include <queue>using namespace std;void BFS(vector<vector<int>>& adj, int start) {    vector<bool> visited(adj.size(), false);    queue<int> q;        q.push(start);    visited[start] = true;        while (!q.empty()) {        int node = q.front();        q.pop();        cout << node << " ";                for (int neighbor : adj[node]) {            if (!visited[neighbor]) {                visited[neighbor] = true;                q.push(neighbor);            }        }    }}

总结

通过本教程，你已经掌握了 C++ 中图的基本概念、两种主要表示方法（邻接矩阵与邻接表），以及两种核心遍历算法：深度优先搜索和广度优先搜索。这些是学习更高级图算法（如最短路径、最小生成树等）的基础。

建议你动手编写代码，尝试构建自己的图并运行 DFS/BFS，加深理解。记住，实践是掌握C++图算法的关键！