当前位置：首页 > article >正文

拓扑排序的核心算法：BFS应用与实践

article 2025/2/25 14:26:05

一、拓扑排序简介

二、BFS解决拓扑排序的步骤

三、C++实现

四、代码解释

五、总结

一、拓扑排序简介

拓扑排序是对有向无环图（DAG）进行排序的一种方法，使得对于图中的每一条有向边 (u, v)，u 在排序中总是位于 v 的前面。拓扑排序的结果可能不唯一。

二、BFS解决拓扑排序的步骤

初始化：计算每个顶点的入度（即指向该顶点的边的数量），并将所有入度为0的顶点加入队列。
BFS遍历：
- 从队列中取出一个顶点，将其添加到拓扑排序的结果中。
- 移除该顶点的所有出边，即将其邻接顶点的入度减1。
- 如果某个邻接顶点的入度变为0，则将其加入队列。
结束条件：当队列为空时，如果拓扑排序结果中的顶点数量与图中的顶点数量相同，则排序成功；否则，图中存在环，无法进行拓扑排序。

三、C++实现

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> topologicalSort(int V, vector<vector<int>>& adj) {
    vector<int> inDegree(V, 0);
    for (int u = 0; u < V; ++u) {
        for (int v : adj[u]) {
            inDegree[v]++;
        }
    }

    queue<int> q;
    for (int u = 0; u < V; ++u) {
        if (inDegree[u] == 0) {
            q.push(u);
        }
    }

    vector<int> result;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : adj[u]) {
            if (--inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    if (result.size() != V) {
        cout << "图中存在环，无法进行拓扑排序" << endl;
        return {};
    }

    return result;
}

int main() {
    int V = 6;
    vector<vector<int>> adj = {
        {2, 3},
        {3, 4},
        {5},
        {5},
        {5},
        {}
    };

    vector<int> sortedOrder = topologicalSort(V, adj);
    for (int u : sortedOrder) {
        cout << u << " ";
    }
    cout << endl;

    return 0;
}