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

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

图的表示方法

邻接表表示法

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

#include <vector>
#include <list>

// 无向图添加边
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 <vector>

// 添加边
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 <stack>
#include <vector>

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 <queue>
#include <vector>

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 <vector>

// 并查集数据结构
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 <queue>
#include <vector>

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 <iostream>

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++标准库中的容器和函数，代码简洁高效。这些算法构成了图论的基础，掌握它们对于解决更复杂的图论问题至关重要。