图论算法详解：BFS、DFS 及最小生成树

遍历算法

BFS（广度优先遍历）

1. 什么是 BFS？

BFS（广度优先搜索）是一种图的遍历算法，用于从一个起始节点出发，逐层访问图中的所有节点。其基本流程如下：

1. 起始节点：选择一个节点作为起点。
2. 队列：使用队列（FIFO）来保存待访问的节点。
3. 访问过程：
   • 将起始节点加入队列并标记为已访问。
   • 当队列不为空时：
     • 从队列中取出一个节点，访问该节点。
     • 将该节点的所有未访问邻居节点加入队列并标记为已访问。
4. 层级遍历：BFS 会先访问距离起始节点最近的节点，然后逐层向外扩展，直到所有可以访问的节点都被访问。

2. 特点和应用

• 最短路径：在无权图中，BFS 可以找到从起始节点到其他节点的最短路径。
• 图的连通性：可以用来判断图的连通性，即判断两个节点是否在同一连通分量中。
• 应用：广泛应用于网络流、社交网络分析、最短路径问题、迷宫求解等领域。

3. BFS 示例

假设我们有一个无向图，节点间的连接如下：

应该如何实现这种算法呢？首先我们应该用一个队列来维护节点，进入 BFS 这个接口的时候，我们应该传入从哪个节点开始进行 BFS。然后用一个队列来维护节点，先将第一个节点 push 进队列中，然后将这个节点输出之后，先将这个节点保存起来然后再把这个节点 pop 掉，然后将与这个节点相连的节点 push 进队列（注意：这里可能会出现重复的节点，比如我们拿上面的例子为例，第一次 push 的时候我们将 C 节点已经 push 进队列了，但是第二层访问完了之后，到第三层的时候，B 和 C 相连还会遍历一次 C，所以这里我们应该用一个 vector 进行标记，标记这个节点被访问过没有），进入循环的条件是队列是否为空。

代码展示：

void BFS(const V& src) {
    size_t srci = GetVertexIndex(src);
    queue<int> q;
    q.push(srci); // 队列
    vector<bool> visited(_vertexs.size(), false); // 标记数组
    visited[srci] = true;
    int levelsize = 1;
    size_t n = _vertexs.size();
    while (!q.empty()) {
        for (int i = 0; i < levelsize; i++) {
            int front = q.front();
            cout << front << ':' << _vertexs[front] << ' ';
            q.pop(); // 把 front 顶点的邻接顶点入队列
            for (size_t i = 0; i < _vertexs.size(); i++) {
                if (_matrix[front][i] != MAX_W && visited[i] == false) {
                    q.push(i);
                    visited[i] = true;
                }
            }
        }
        cout << endl; // levelsize 是下一层的数据个数
        levelsize = q.size();
    }
}

DFS（深度优先搜索）

1. 什么是 DFS？

DFS（深度优先搜索）是一种图的遍历算法，从起始节点开始，尽可能深入探索每个分支，直到无法再继续，然后回溯到上一个节点，继续探索其他分支。它适用于有向图和无向图。

2. DFS 的基本步骤

1. 起始节点：选择一个节点作为起点。
2. 深入探索：访问起始节点，并标记为已访问。
3. 递归访问：对当前节点的每个未访问邻居节点递归进行深度优先搜索。
4. 回溯：如果当前节点的所有邻居都被访问，则回溯到上一个节点，继续深度搜索其他分支。

3. 特点

• 优先深入：DFS 尽可能先访问一个节点的最深分支，再逐步回溯到较浅的分支。
• 非最短路径：与 BFS 不同，DFS 不保证找到最短路径，因为它按深度优先进行搜索。
• 应用广泛：DFS 可用于检测图的连通性、拓扑排序、寻找路径和检测环。

4. DFS 的应用

• 路径搜索：可以用于寻找图中从一个节点到另一个节点的路径。
• 图的连通性：判断图中的连通分量。
• 拓扑排序：用于有向无环图（DAG）的节点排序。
• 检测环：可以检测图中是否存在环。

5. DFS 示例

DFS 和 BFS 一样，还是给定一个起点，从这个起点开始进行，但是 DFS 的方式和 BFS 完全不同，DFS 是一条路走到黑，从当前节点一直走，走到不能走为止，当走到不能走时，进行回溯，回溯到上一个岔口，然后向刚刚没有走过的路口继续走，走到尽头的时候又进行回溯，就一直这样递归，直到把所有节点遍历完为止。

代码展示：

void _DFS(size_t srci, vector<bool>& visited) {
    // 进来直接访问这个点
    cout << srci << ':' << _vertexs[srci] << endl;
    visited[srci] = true;
    // 找到下一个 srci 相邻的没有访问过的点，去往深度遍历
    for (size_t i = 0; i < _vertexs.size(); i++) {
        // 如果下一个节点没有被访问过直接遍历
        if (_matrix[srci][i] != MAX_W && visited[i] == false) {
            _DFS(i, visited);
        }
    }
}

void DFS(const V& src) {
    // 获取起点下标
    size_t srci = GetVertexIndex(src);
    vector<bool> visited(_vertexs.size(), false);
    _DFS(srci, visited);
}

注意：DFS 中也需要用一个 bool 数组进行标记，当前位置是否被访问过。

最小生成树问题

1. 什么是最小生成树？

最小生成树是一个图的子集，包含图中的所有节点，并且是连通的，同时边的总权重最小。最小生成树的特点是没有回路，并且连接了图中的所有节点。

2. 最小生成树的基本特性

• 包含所有节点：最小生成树包含图中的所有顶点。
• 边的权重总和最小：在所有可能的生成树中，其边权重之和是最小的。
• 无环图：最小生成树是一个无环的连通图。

3. 应用场景

• 网络设计：如计算机网络、交通网络的最优连接。
• 电路设计：用于布线问题，减少电缆长度。
• 聚类分析：在数据科学中，用于分类和分组。

4. 最小生成树的算法

常用的求解最小生成树的算法有：

1. Kruskal 算法：通过选择边的方式逐步构建最小生成树，优先选择权重最小的边，确保不形成回路。
2. Prim 算法：从一个起始节点开始，逐步扩展生成树，选择连接已包含节点和未包含节点的最小权重边。

5. 最小生成树的图示：

下面的图就是上面的图的最小生成树的其中之一。最小生成树是不止一个的。如果我们选择上面那个 8，最小生成树又不一样。

最小生成树算法

Kruskal 算法

1. 什么是 Kruskal 算法？

克鲁斯卡尔算法是一种用于求解最小生成树（MST）的贪心算法。它通过选择边的方式逐步构建最小生成树，优先选择权重最小的边，并确保不形成回路。

2. 算法步骤

克鲁斯卡尔算法的基本步骤如下：

1. 排序边：将图中的所有边按权重从小到大排序。
2. 初始化：创建一个空的生成树，并初始化一个并查集（Union-Find）结构，用于检测图中的环。
3. 选择边：
   • 从权重最小的边开始，依次考虑每条边。
   • 对于每条边 (u, v)，检查 u 和 v 是否在同一连通分量中（使用并查集）。
   • 如果不在同一连通分量中，加入该边到生成树，并将 u 和 v 的连通分量合并。
4. 结束条件：当生成树中的边数等于 V-1（V 为节点数）时，算法结束。

3. 算法复杂度

• 时间复杂度：O(E log E)，其中 E 是边的数量，主要由排序边的时间决定。
• 空间复杂度：O(V)，用于存储并查集。

4. 示例

5. 思路及代码

根据克鲁斯卡尔算法的步骤：

1. 排序边，我们可以用优先级队列来对边进行排序，但是这个边不能只有边，应该还需要边两端的顶点，所以我们需要把这个封装成一个结构体，也就是边集，还有一个问题就是排序，优先级队列的排序默认是从大到小，所以我们还需要写一个比较的逻辑进行比较。
2. 初始化：初始化我们只需要将最小生成树初始化为原图的大小即可。大小和原图一模一样，顶点映射下标的关系也和原图一模一样。
3. 选择边：在选择边时，我们只需要将存在优先级队列中的边取出来即可，但是在选择边时需要检查一下这个边加入之后是否会形成环，这时就可以利用并查集，因为并查集可以高效管理集合，我们开辟一个并查集的大小是顶点个数的并查集，如果这条边选了就将这两个顶点的集合合并，如果会形成环的话，那么对应的两个顶点肯定在一个集合当中。所以我们只需要判断这两个顶点是否在一个集合当中即可，如果没在一个集合当中，就将这条边给最小生成树，并且将这两个顶点的集合合并，还需要一个累加权值的变量记录总的权值大小。
4. 结束条件：用 size 记录边数的大小，当边的条数等于顶点的个数 -1 的时候就是结束的时候。

代码展示：

W Kruskal(Self& minTree) {
    size_t n = _vertexs.size();
    minTree._vertexs = _vertexs;
    minTree._indexMap = _indexMap;
    minTree._matrix.resize(n);
    for (auto& e : minTree._matrix) e.resize(n, MAX_W);

    // 优先级队列，优先级默认是大的优先级高，所以这里要控制
    priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // i<j 保证只访问一次
            if (i < j && _matrix[i][j] != MAX_W) {
                // 将 edge 插入进去，由于无向图会出现重复添加的情况，所以无向图走一半即可
                minq.push(Edge(i, j, _matrix[i][j]));
            }
        }
    }

    // 选出 n-1 条边
    // 开辟一个 n 个顶点的并查集
    size_t size = 0;
    // 总的权值
    W totalW = W();
    UnionFindset ufs(n);

    while (!minq.empty()) {
        // 选择一条边
        Edge eg = minq.top();
        minq.pop();

        // 观察两个顶点是否在同一个集合
        if (!ufs.IsInSet(eg._srci, eg._dsti)) {
            cout << _vertexs[eg._dsti] << "->" << _vertexs[eg._srci] << ':' << eg._w << endl;
            // 将边添加到 mintree 中
            minTree._AddEdge(eg._srci, eg._dsti, eg._w);
            // 将顶点添加到并查集当中
            ufs.Union(eg._srci, eg._dsti);
            totalW += eg._w;
            ++size;
        }
    }

    if (size == n - 1) return totalW;
    else return W();
}

Prim 算法

1. 什么是 Prim 算法？

普利姆算法是一种用于求解最小生成树（MST）的贪心算法。它从一个节点开始，通过逐步选择连接已访问节点和未访问节点的最小权重边来扩展生成树，直到所有节点都被包含。

2. 算法步骤

普利姆算法的基本步骤如下：

1. 选择起始节点：从图中的任意一个节点开始（通常是第一个节点）。
2. 初始化：将起始节点加入生成树，并将它的所有邻边放入一个优先队列（最小堆），按边的权重排序。
3. 选择最小权重边：从优先队列中取出权重最小的边，并检查其连接的节点是否已在生成树中。
   • 如果该节点已在生成树中，忽略这条边。
   • 如果该节点不在生成树中，将该节点和边加入生成树，并将新节点的所有邻边加入优先队列。
4. 重复：不断从优先队列中选取最小权重边，直到生成树包含所有节点。

3. 算法复杂度

• 时间复杂度：O(E log V)，其中 E 是边的数量，V 是节点数量，主要由最小堆操作决定。
• 空间复杂度：O(V^2)

4. 示例

5. 思想及代码

普林姆算法和克里姆林算法还是有很大的差别的，普林姆算法需要起始点，然后将起始点相连最小的边入到边集当中。

假设这个图我们以 a 点为例，和 a 相连的边是 b 和 h 点，ab 边明显小于 ah 边，所以我们选择 ab 边

这里引入了 b 点，所以我们的选择是 bc 边，bh 边还有 ah 边，很明显这里我们选择 bc 边也可以，ah 边也可以，所以我们就选择 ah 边吧。

这里我们可以选择的边种最小的是 hg 边。

接下来我们肯定选择 gf，因为 gf 最小

最后可以推出最小生成树

Prim 算法的思路很简单，实现过程我们还是用优先级队列，但是在选择的时候我们需要判断一下是否形成环。

代码展示：

W Prim(Self& minTree, const V& src) {
    // 初始化
    size_t srci = GetVertexIndex(src);
    size_t n = _vertexs.size();
    minTree._vertexs = _vertexs;
    minTree._indexMap = _indexMap;
    minTree._matrix.resize(n);
    for (auto& e : minTree._matrix) e.resize(n, MAX_W);

    // 选过的顶点
    vector<bool> X(n, false);
    vector<bool> Y(n, true);
    X[srci] = true, Y[srci] = false;

    // 从 X->Y 集合中连接的边里面选出最小的边
    priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
    for (size_t i = 0; i < _vertexs.size(); i++) {
        // 把 srci 连接的边添加到队列中
        if (_matrix[srci][i] != MAX_W) minq.push(Edge(srci, i, _matrix[srci][i]));
    }
    cout << "Prim 开始选边" << endl;

    size_t size = 0;
    W totalW = W();
    while (!minq.empty()) {
        Edge min = minq.top();
        minq.pop();

        // 如果最小边的目标点也在起点集合
        if (X[min._dsti]) {
            cout << "构成环：";
            cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
        } else {
            minTree._AddEdge(min._srci, min._dsti, min._w);
            cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
            size++;
            totalW += min._w;
            if (size == n - 1) break;

            // 将 dsti 添加到 X 集合
            X[min._dsti] = true;
            Y[min._dsti] = false;
            for (size_t i = 0; i < _vertexs.size(); i++) {
                // 将目标点连接的边添加到集合当中并且需要判断目标点是否已经在集合当中
                if (_matrix[min._dsti][i] != MAX_W && X[i] == false) minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
            }
        }
    }

    if (size == n - 1) return totalW;
    else return W();
}

结尾总结

通过本文的讲解，我们深入了解了图论中的三种经典算法：广度优先搜索（BFS）、深度优先搜索（DFS）和最小生成树（Kruskal 算法和 Prim 算法）。这些算法在计算机科学、数据分析、人工智能等领域有着广泛的应用。

从简单的图遍历到复杂的网络优化问题，这些算法都展现了其强大的解决问题能力。然而，图论是一个庞大的领域，还有许多更深入、更复杂的算法等待我们去探索。例如，拓扑排序、强连通分量、最短路径问题等。

希望本文能为你打开图论算法的大门，激发你对算法学习的兴趣。在未来的学习中，我们可以继续深入研究图论算法，并将其应用到实际的项目中。