97°

拓扑排序

在有向无环图(DAG,即 Directed Acyclic Graph)中,拓扑排序(Topological Sorting)是其顶点的线性排序,使得对于从顶点 \(u\) 到顶点 \(v\) 的每个有向边,在排序中 \(u\) 都在 \(v\) 之前。

有向无环图(DAG)才有拓扑排序,非 DAG 图是没有拓扑排序这个概念的。

例如,下面这个图,是一个 DAG,

算法实现

拓扑排序的实现非常之简单,下面介绍一个常用的实现算法 - 卡恩算法(Kahn's algorithm),

  1. 从 DAG 中选择一个没有前驱(即入度为 0)的顶点并输出;
  2. 从图中删除该顶点和所有以它为起点的有向边;
  3. 重复 1 和 2 直到当前的 DAG 为空或当前图中不存在无前驱的顶点为止。后一种情况说明该图中必然存在环,可以以此判断该图是否能生成拓扑排序序列。

代码如下:

#include <iostream>
#include <queue>

using namespace std;

int n; /* 顶点数(<=100) / int m; / 边数 / int matrix[105][105]; / 邻接矩阵 / int inDegree[105]; / 入度 */

void TopologicalSort() { int num = 0; /* 已被拓扑排序的顶点的个数 */ queue<int> q;

/* 找到所有入度为 0 的顶点,并入队列 */
for (int i = 1; i &lt;= n; ++i)
{
	if (inDegree[i] == 0)
	{
		num++;
		inDegree[i]--;
		q.push(i);
		cout &lt;&lt; i &lt;&lt; " ";
	}
}

while (!q.empty())
{
	int u = q.front();
	q.pop();

	for (int v = 1; v &lt;= n; ++v)
	{
		if (matrix[u][v])
		{
			inDegree[v]--;
			if (inDegree[v] == 0)
			{
				num++;
				q.push(v);
				cout &lt;&lt; v &lt;&lt; " ";
			}
		}
	}
}

/* 说明有环 */
if (num != n)
	cout &lt;&lt; "有环,无法生成拓扑序列";

cout &lt;&lt; endl &lt;&lt; endl;

}

int main() { while (1) { memset(matrix, 0, sizeof(matrix)); memset(inDegree, 0, sizeof(inDegree));

	cout &lt;&lt; "请输入顶点数(&lt;=100):";
	cin &gt;&gt; n;
	cout &lt;&lt; "请输入边数:";
	cin &gt;&gt; m;

	cout &lt;&lt; "请输入 " &lt;&lt; m &lt;&lt; " 条有向边:" &lt;&lt; endl;
	int u, v;
	for (int i = 0; i &lt; m; ++i)
	{
		cin &gt;&gt; u &gt;&gt; v;
		matrix[u][v] = 1;
		inDegree[v]++;
	}

	cout &lt;&lt; "拓扑序列为:";
	TopologicalSort();
}
return 0;

}

输出如下:

请输入顶点数(<=100):5
请输入边数:7
请输入 7 条有向边:
1 2
1 4
2 4
2 3
4 3
3 5
4 5
拓扑序列为:1 2 4 3 5

请输入顶点数(<=100):3 请输入边数:3 请输入 3 条有向边: 1 2 2 3 3 1 拓扑序列为:有环,无法生成拓扑序列

参考

本文转载自博客园,原文链接:https://www.cnblogs.com/RioTian/p/13056589.html

全部评论: 0

    我有话说: