拓扑排序

缘起

我一直认为学习操作系统是一件很酷的事情. 兴致勃勃的准备学习的时候, 却发现了如下的先需课程

  1. C语言
  2. 数据结构和算法
  3. 编译原理
  4. 计算机组成原理

其中, 1->2->3 是不能乱序的. 但是4和1 2 3之间没有绝对的谁先学、谁后学的顺序. 所以这就构成了一个有向图. 而且我采用了如下的学习顺序

​ 1–>2–>3–>4

但其实也可以采用如下的学习顺序

​ 1–>2–>4–>3

甚至有些巨巨

​ 4–>1–>2–>3

这个顺序就是有向图的拓扑序. 所以需求来了——求出有向图的拓扑序.

分析

从上面的例子至少可以看出 一张有向图的拓扑序未必是唯一的. 其次，我想说的是一张有向图未必有拓扑序. 例如学A之前必须学B，学B之前又必须学A（虽然这种实际例子比较反人类, 但只是假设哈）

那么，你不可能给出这张有向（有环）图的拓扑序. 但是有向无环图（即DAG图）是一定有拓扑序的, 因为总有入度为0的顶点, 我们将其去掉, 变成规模严格更小的DAG图（递归），从而就可以导出其拓扑序. 我们的拓扑序算法的核心也正是基于此. 而且 DAG的拓扑排序必然存在；反之亦然 (即如果存在拓扑序, 那该有向图一定是DAG)

所以建立拓扑序的算法还可以用来判定有向图是否存在环. 注意. 之前写过一篇《无向图判定是否存在环》, 那里的算法很简单, 就是跑dfs的时候, 如果遇到了已经访问过的顶点的话, 就一定存在环. 但是对于有向图而言, 是不能这么做的. 原因也很简单. 因为不能因为dfs的过程中遇到了<u,v>(从u到v的边) 而v已经访问过了就认为该有向图中存在环. 因为u和v完全可能不在一棵dfs树上（<u,v>仅仅是横叉边）. 所以才需要使用拓扑序算法.

注意, 这里我们不再自己纯粹的使用链表+数组实现图的邻接链表模型. 而是使用c++的STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include "stdafx.h"
#include <iostream>
#include <stack>
#include <vector>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

#define LOCAL
using namespace std;

#define MAX_VERTEX_NUM 10
typedef vector<int>::iterator it; // 定义迭代器 


struct Graph // 这里使用c++的stl实现了一个非常精巧的邻接链表表示模型, 即原先的链表使用向量替代了.
{
	vector<int> vertex[MAX_VERTEX_NUM]; // 二维数组
	int indeg[MAX_VERTEX_NUM]; // 维护入度域， 这是拓扑序算法的关键
	int vertexnum; // 顶点的个数
	stack<int> s; // 用于装载入度域堕落为0的顶点

	// 判断是否是dag图, 返回true的话, 表示是dag图, 并输出其拓扑序, 否则返回false
	bool dag()
	{
		memset(indeg, 0, sizeof(indeg));
		cout << "输入顶点数" << endl;
		scanf("%d", &vertexnum);
		puts("输入边, 起点在前, 终点在后.");
		int start, end;
		while (~scanf("%d%d",&start, &end))
		{
			vertex[start].push_back(end);
			indeg[end]++; // 入度+1
		}
		// 初始化栈
		for (int i = 0; i< vertexnum;i++)if (!indeg[i])s.push(i);
		while(!s.empty())
		{
			int vtx = s.top();
			s.pop();
			cout << vtx << endl;
			vertexnum--; // 顶点少了一个
			for (it i = vertex[vtx].begin(); i!=vertex[vtx].end();i++)
			{
				if (!(--indeg[*i]))
				{
					s.push(*i);
				}
			}
		}
		return !vertexnum; // 空了 才是dag
	}
};



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Graph g;
	printf("%s\n",g.dag()?"是dag":"不是dag");
	return 0;
}

ps： 其实

有向图是否有环

有向图是否是DAG

有向图是否存在拓扑序

三者等价

后续思考

如果已经知道了一个图是DAG图的话, 则只需使用DFS遍历之，期间打印每个节点, 得到的序列就是其拓扑序. 具体代码参看 https://yfsyfs.github.io/2019/05/21/%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86%E4%B9%8BBFS-DFS/