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

目录

一、拓扑排序简介

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

三、C++实现

四、代码解释

五、总结

---

一、拓扑排序简介

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

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

1. 初始化：计算每个顶点的入度（即指向该顶点的边的数量），并将所有入度为0的顶点加入队列。

2. BFS遍历：

   • 从队列中取出一个顶点，将其添加到拓扑排序的结果中。

   • 移除该顶点的所有出边，即将其邻接顶点的入度减1。

   • 如果某个邻接顶点的入度变为0，则将其加入队列。

3. 结束条件：当队列为空时，如果拓扑排序结果中的顶点数量与图中的顶点数量相同，则排序成功；否则，图中存在环，无法进行拓扑排序。

三、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;
}

四、代码解释

• inDegree 数组用于存储每个顶点的入度。

• adj 是图的邻接表表示。

• topologicalSort 函数实现了拓扑排序的逻辑。

• 如果排序结果中的顶点数量与图中的顶点数量不一致，说明图中存在环。

五、总结

        使用BFS进行拓扑排序是一种高效的方法，时间复杂度为O(V + E)，其中V是顶点数量，E是边数量。这种方法不仅适用于拓扑排序，还可以用于检测图中是否存在环。