拓扑排序 Topo

定义

拓扑排序（Topological sorting）是在 DAG（有向无环图）中对其顶点的一种线性排序，使得对于从顶点

u

到顶点

v

的每个有向边

u\to v

，

u

在排序中都在

v

之前。

这就像是在给一系列有 依赖关系 的任务进行排序。比如“穿裙子”这个任务，依赖于“先穿内衣”。那么拓扑排序的结果中，“穿内衣”必然在“穿裙子”之前。

Kahn

非常直观的算法。模拟了一个“不断移除没有前置依赖的节点”的过程。

算法步骤：

初始化：
- 计算图中每个节点的入度（即有多少条边指向它）；
- 创建一个队列，将所有入度为 $0$ 的节点加入其中。这些节点是“起点”，它们不依赖于任何其他任务；
- 初始化一个空列表，用于存放拓扑排序的结果。
循环处理：
- 从队列中取出一个节点 $u$ ，并将其加入结果列表；
- 遍历 $u$ 的所有指向的节点 $v$ ；
- 将 $v$ 的入度减 $1$ ；
- 如果此时 $v$ 的入度变为 $0$ ，说明 $v$ 的所有前置依赖都已被满足，则将 $v$ 加入队列；
- 重复此过程，直到队列为空。
结束检查：
- 如果结果列表中的节点个数与图中总节点数相同，说明排序成功，返回该列表。
- 如果结果列表中的节点个数少于总节点数，说明图中存在环，无法进行拓扑排序。

B3644 【模板】拓扑排序 / 家谱树

代码实现

CPP

#include<bits/stdc++.h>
using namespace std;

const int MAX = 105;
queue<int> q;
vector<int> g[MAX], ans;
int rd[MAX], n;

void kahn()
{
	for(int i=1; i<=n; i++)
		if(rd[i] == 0) q.push(i);
	while(!q.empty())
	{
		int t = q.front(); q.pop();
		ans.push_back(t);
		for(auto v : g[t])
		{
			rd[v]--;
			if(rd[v] == 0) q.push(v);
		}
	}
	if(ans.size() != n) cout << "有环" << endl;
	else for(auto v : ans) cout << v << ' ';
}

int main()
{
	cin >> n;
	for(int i=1; i<=n; i++)
	{
		int a; cin >> a;
		while(a) {g[i].push_back(a), rd[a]++; cin >> a;}
	}
	kahn();
	return 0;
}

DFS

利用深度优先搜索，在回溯时记录节点，本质上是一种后序遍历。

算法步骤：

对图中的每个未访问节点执行DFS。
在DFS过程中：
- 递归地访问它所有指向的节点。
- 当某个节点的所有邻居都处理完毕后，将该节点压入一个栈。
最终，栈顶到栈底（或列表从头到尾）的顺序就是一个拓扑排序。

代码实现（未检测环）

CPP

#include<bits/stdc++.h>
using namespace std;
const int MAX = 105;
vector<int> e[MAX];
int n, vis[MAX];

stack<int> ans;
void dfs(int u)
{
    for(auto v : e[u]) {if(vis[v]) continue; dfs(v);}
    vis[u] = 1; ans.push(u);
}

signed main()
{
    int n, a; cin >> n;
    for(int i=1; i<=n; i++)
        while(cin >> a && a)
            e[i].push_back(a);
    for(int i=1; i<=n; i++) if(!vis[i]) dfs(i);
    while(!ans.empty()) cout << ans.top() << ' ', ans.pop(); 
    return 0;
}

解析：

先递归处理所有后继节点（依赖当前节点的节点）
当所有后继节点都处理完后，再处理当前节点
使用栈来保证"依赖关系"的正确性

总结

特性	Kahn	DFS
思想	BFS，基于入度	DFS，基于递归栈
环检测	简单直观	需要额外状态标记
空间	队列+入度数组	递归栈+状态数组
适用场景	拓扑排序	dfs强强的人使用

文章操作

定义

Kahn

DFS

总结

相关推荐

评论

拓扑排序 Topo