1. 定义

拓扑排序（Topological Sorting）是针对有向无环图（DAG, Directed Acyclic Graph）的一种排序方法。其目的是将图中的所有顶点排成一个线性序列，使得对于图中的每一条有向边 u->v，顶点 u 在 v 之前。

2. 概述

拓扑排序常用于解决任务调度、编译顺序确定、依赖关系解析等问题。其本质是寻找一种可行的线性排序，使得满足依赖关系的任务得以按顺序执行。

拓扑排序的前提是图必须是 有向无环图（DAG），否则无法进行拓扑排序。常见的拓扑排序方法包括 入度法（Kahn算法） 和 深度优先搜索（DFS）法。

3. 算法思想

3.1 入度法（Kahn算法）

1. 统计所有顶点的入度。

2. 将所有入度为 0 的顶点加入队列。

3. 依次从队列中取出顶点 u，将其加入拓扑序列，并移除 u 指向的所有边。

4. 若某个顶点的入度变为 0，将其加入队列。

5. 重复上述过程，直到队列为空。

6. 若最终拓扑序列中的顶点数等于图中顶点数，则排序成功，否则说明存在环。

3.2 深度优先搜索（DFS）法

1. 维护一个访问标记数组 vis，其中 0 表示未访问，1 表示正在访问，2 表示已访问。

2. 遍历所有未访问的顶点，执行 DFS 过程。

3. 在 DFS 过程中，若访问到正在访问的顶点，则说明存在环。

4. 若 DFS 递归回溯，则将当前顶点加入拓扑序列。

5. 逆序输出拓扑序列。

4. 举个栗子🌰

假设我们有一个更复杂的有向无环图，包含 7 个任务（顶点）和如下的依赖关系：

1 -> 2
1 -> 3
2 -> 4
2 -> 5
3 -> 5
3 -> 6
4 -> 7
5 -> 7
6 -> 7

其对应的图结构如下：

    1
   / \
  2   3
 / \ / \
4   5   6
 \  |  /
    7

4.1模拟（kahn)

初始化 in 数组（入度）：

in: [0,0,1,1,2,1,2,3]

处理步骤：

1. 取出入度为 0 的节点 1，移除其边 1->2 和 1->3。

   • in: [0,0,0,1,2,1,2,3]

   • 队列：[1]

   • 结果：1

2. 取出 2，移除 2->4 和 2->5。

   • in: [0,0,0,0,1,0,2,3]

   • 队列：[1,2]

   • 结果：1 2

3. 取出 3，移除 3->5 和 3->6。

   • in: [0,0,0,0,1,0,1,3]

   • 队列：[1,2,3]

   • 结果：1 2 3

4. 取出 4，移除 4->7。

   • in: [0,0,0,0,0,0,1,2]

   • 队列：[1,2,3,4]

   • 结果：1 2 3 4

5. 取出 5，移除 5->7。

   • in: [0,0,0,0,0,0,1,1]

   • 队列：[1,2,3,4,5]

   • 结果：1 2 3 4 5

6. 取出 6，移除 6->7。

   • in: [0,0,0,0,0,0,0,0]

   • 队列：[1,2,3,4,5,6]

   • 结果：1 2 3 4 5 6

7. 取出 7。

   • 队列：[1,2,3,4,5,6,7]

   • 结果：1 2 3 4 5 6 7

最终拓扑序列：1 2 3 4 5 6 7

 

5. 代码实现

5.1 入度法（Kahn算法）

#include<iostream>
#include<queue>
using namespace std;

int n=7,m=9,in[10],tot,a[10][10];
queue<int>q;

void topo_sort()
{
	for(int i=1;i<=n;i++)if(!in[i])q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		cout<<u<<" ";
		for(int v=1;v<=n;v++)
		{
			if(a[u][v])
			{
				in[v]--;
				if(!in[v])q.push(v);
			}
		}
	}
}

int main()
{
	int edges[9][2]={{1,2},{1,3},{2,4},{2,5},{3,5},{3,6},{4,7},{5,7},{6,7}};
	for(int i=0;i<m;i++)
	{
		int u=edges[i][0],v=edges[i][1];
		a[u][v]=1;
		in[v]++;
	}
	topo_sort();
	return 0;
}

5.2 深度优先搜索（DFS）法

#include<iostream>
using namespace std;

int n=7,m=9,a[10][10],vis[10],order[10],tot;

void dfs(int u)
{
	vis[u]=1;
	for(int v=1;v<=n;v++)
	{
		if(a[u][v]&&!vis[v])dfs(v);
	}
	order[++tot]=u;
}

void topo_sort()
{
	for(int i=1;i<=n;i++)if(!vis[i])dfs(i);
	for(int i=tot;i>=1;i--)cout<<order[i]<<" ";
}

int main()
{
	int edges[9][2]={{1,2},{1,3},{2,4},{2,5},{3,5},{3,6},{4,7},{5,7},{6,7}};
	for(int i=0;i<m;i++)
	{
		int u=edges[i][0],v=edges[i][1];
		a[u][v]=1;
	}
	topo_sort();
	return 0;
}

6. 注意事项

1. DAG 限制：拓扑排序仅适用于 有向无环图（DAG），如果图中存在环，拓扑排序无法进行。

2. 唯一性：若某个图存在多个拓扑序列，则说明拓扑排序结果可能不唯一。

3. 检测环：在 DFS 版本中，若访问到已经在递归栈中的节点，则说明存在环。

4. 入度法 vs DFS：

   • 入度法适合 宽度优先遍历（BFS），较为直观，适用于大多数场景。

   • DFS 方法适合 深度优先遍历（DFS），可用于检测环，但实现较为复杂。

7. 结论

拓扑排序是一种重要的图算法，在解决任务调度、依赖管理等问题中非常有用。掌握 入度法（Kahn算法） 和 深度优先搜索（DFS）法 这两种方式，能更好地应对不同的实际应用场景。