网站导航
> 技术文档 > 图论基础：DFS、BFS、并查集与拓扑排序的C++实现_图论基础c++

图论基础：DFS、BFS、并查集与拓扑排序的C++实现_图论基础c++

网友: 技术文档 2025-07-30 14:13:11

图论基础算法：DFS、BFS、并查集与拓扑排序的C++实现

图论是计算机科学中的核心领域，广泛应用于社交网络分析、路径规划、编译器设计等场景。本文将介绍图论中的基础算法及其C++实现，使用函数式编程风格而非面向对象方法。

图的表示方法

邻接表表示法

邻接表是表示稀疏图的高效方式，空间复杂度为O(V+E)：

#include #include // 无向图添加边void addEdge(std::vector<std::list<int>>& graph, int v, int w) { graph[v].push_back(w); graph[w].push_back(v);}// 有向图添加边void addDirectedEdge(std::vector<std::list<int>>& graph, int v, int w) { graph[v].push_back(w);}// 创建图示例std::vector<std::list<int>> createGraph(int V) { return std::vector<std::list<int>>(V);}

邻接矩阵表示法

邻接矩阵适合表示稠密图，空间复杂度为O(V²)：

#include // 添加边void addMatrixEdge(std::vector<std::vector<bool>>& matrix, int v, int w) { matrix[v][w] = true; matrix[w][v] = true; // 无向图}// 创建邻接矩阵std::vector<std::vector<bool>> createAdjMatrix(int V) { return std::vector<std::vector<bool>>(V, std::vector<bool>(V, false));}

深度优先搜索(DFS)

DFS以深度优先方式遍历图，适合解决连通性问题：

#include #include void dfs(const std::vector<std::list<int>>& graph, int start) { std::vector<bool> visited(graph.size(), false); std::stack<int> stack; stack.push(start); visited[start] = true; while (!stack.empty()) { int current = stack.top(); stack.pop(); std::cout << current << \" \"; for (int neighbor : graph[current]) { if (!visited[neighbor]) { stack.push(neighbor); visited[neighbor] = true; } } } std::cout << \"\\n\";}// 递归实现void dfsRecursiveUtil(const std::vector<std::list<int>>& graph,std::vector<bool>& visited, int v) { visited[v] = true; std::cout << v << \" \"; for (int neighbor : graph[v]) { if (!visited[neighbor]) { dfsRecursiveUtil(graph, visited, neighbor); } }}void dfsRecursive(const std::vector<std::list<int>>& graph, int start) { std::vector<bool> visited(graph.size(), false); dfsRecursiveUtil(graph, visited, start); std::cout << \"\\n\";}

时间复杂度：O(V + E)

广度优先搜索(BFS)

BFS按层次遍历图，适合寻找最短路径：

#include #include void bfs(const std::vector<std::list<int>>& graph, int start) { std::vector<bool> visited(graph.size(), false); std::queue<int> queue; queue.push(start); visited[start] = true; while (!queue.empty()) { int current = queue.front(); queue.pop(); std::cout << current << \" \"; for (int neighbor : graph[current]) { if (!visited[neighbor]) { queue.push(neighbor); visited[neighbor] = true; } } } std::cout << \"\\n\";}

应用场景：社交网络中的好友推荐、最短路径查找

并查集(Union-Find)

并查集高效处理不相交集合的合并与查询问题：

#include // 并查集数据结构struct UnionFind { std::vector<int> parent; std::vector<int> rank;};// 初始化并查集UnionFind makeUnionFind(int n) { UnionFind uf; uf.parent.resize(n); uf.rank.resize(n, 0); for (int i = 0; i < n; ++i) { uf.parent[i] = i; } return uf;}// 查找操作（带路径压缩）int find(UnionFind& uf, int u) { if (uf.parent[u] != u) { uf.parent[u] = find(uf, uf.parent[u]); } return uf.parent[u];}// 合并操作（带按秩合并）void unionSets(UnionFind& uf, int u, int v) { int rootU = find(uf, u); int rootV = find(uf, v); if (rootU == rootV) return; if (uf.rank[rootU] > uf.rank[rootV]) { uf.parent[rootV] = rootU; } else { uf.parent[rootU] = rootV; if (uf.rank[rootU] == uf.rank[rootV]) { uf.rank[rootV]++; } }}

优化技术：

  • 路径压缩：使树更平坦，加速后续查找
  • 按秩合并：防止树过高，保持平衡

拓扑排序

拓扑排序对有向无环图(DAG)进行线性排序：

#include #include void topologicalSort(const std::vector<std::list<int>>& graph) { int n = graph.size(); std::vector<int> inDegree(n, 0); std::queue<int> queue; std::vector<int> result; // 计算入度 for (int i = 0; i < n; ++i) { for (int neighbor : graph[i]) { inDegree[neighbor]++; } } // 将入度为0的节点加入队列 for (int i = 0; i < n; ++i) { if (inDegree[i] == 0) { queue.push(i); } } // 处理队列 while (!queue.empty()) { int current = queue.front(); queue.pop(); result.push_back(current); for (int neighbor : graph[current]) { if (--inDegree[neighbor] == 0) { queue.push(neighbor); } } } // 检测环 if (result.size() != n) { std::cout << \"Graph contains cycle!\\n\"; } else { for (int node : result) { std::cout << node << \" \"; } std::cout << \"\\n\"; }}

应用场景：

  1. 任务调度：确定任务执行顺序
  2. 课程安排：解决课程依赖关系
  3. 编译顺序：确定源代码编译顺序

完整示例与测试

#include int main() { // 创建无向图 auto graph = createGraph(6); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 3); addEdge(graph, 1, 4); addEdge(graph, 2, 4); addEdge(graph, 3, 5); addEdge(graph, 4, 5); std::cout << \"DFS traversal (iterative): \"; dfs(graph, 0); std::cout << \"DFS traversal (recursive): \"; dfsRecursive(graph, 0); std::cout << \"BFS traversal: \"; bfs(graph, 0); // 并查集测试 UnionFind uf = makeUnionFind(5); unionSets(uf, 0, 1); unionSets(uf, 2, 3); unionSets(uf, 1, 4); unionSets(uf, 3, 4); std::cout << \"Union-Find sets: \"; for (int i = 0; i < 5; ++i) { std::cout << find(uf, i) << \" \"; } std::cout << \"\\n\"; // 创建有向无环图 auto dag = createGraph(6); addDirectedEdge(dag, 2, 3); addDirectedEdge(dag, 3, 1); addDirectedEdge(dag, 4, 0); addDirectedEdge(dag, 4, 1); addDirectedEdge(dag, 5, 0); addDirectedEdge(dag, 5, 2); std::cout << \"Topological sort: \"; topologicalSort(dag); // 测试有环图 auto cyclicGraph = createGraph(3); addDirectedEdge(cyclicGraph, 0, 1); addDirectedEdge(cyclicGraph, 1, 2); addDirectedEdge(cyclicGraph, 2, 0); std::cout << \"Cyclic graph test: \"; topologicalSort(cyclicGraph); return 0;}

输出示例：

DFS traversal (iterative): 0 2 4 5 3 1 DFS traversal (recursive): 0 1 3 5 4 2 BFS traversal: 0 1 2 3 4 5 Union-Find sets: 1 1 3 1 1 Topological sort: 5 4 2 3 1 0 Cyclic graph test: Graph contains cycle!

算法比较与选择指南

算法 时间复杂度 空间复杂度 最佳适用场景 DFS O(V+E) O(V) 连通性检测、拓扑排序(递归) BFS O(V+E) O(V) 最短路径、层级遍历 并查集 接近O(1) O(V) 动态连通性问题 拓扑排序 O(V+E) O(V) 任务调度、依赖分析

使用建议：

  1. 需要最短路径时优先选择BFS
  2. 处理动态连通性问题使用并查集
  3. 任务调度和依赖分析使用拓扑排序
  4. 一般遍历和连通性检测DFS和BFS均可

总结

本文介绍了图论中四种基础算法的C++实现：

  1. DFS：深度优先遍历，使用栈实现迭代版本
  2. BFS：广度优先遍历，使用队列实现
  3. 并查集：高效处理集合合并与查询
  4. 拓扑排序：Kahn算法实现，自动检测环

所有实现均避免使用类封装，直接使用C++标准库中的容器和函数，代码简洁高效。这些算法构成了图论的基础，掌握它们对于解决更复杂的图论问题至关重要。

网络标签：

相关问题