算法笔记:拓扑排序

发表于 更新于 分类于 ， ，

拓扑排序

概念

对一个有向无环图(Directed Acyclic Graph 简称 DAG)G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边<u,v>∈E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。

实现

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def topologicalSort()

	"""将所有节点的color[u]设置为WHITE"""
	"""设置所有节点u的入度indeg[u]"""

	for u from 0 to |V| - 1
		if indeg[u] == 0 && color[u] == WHITE
			bfs(u)

def bfs(int s)
	Q.push(s)
	color[s] = GRAY
	while Q isn't empty
		u = Q.dequeue
		out.push_back(u) """将度为0的顶点加入链表"""

		for v is the neighbour of u
			indeg[v]--
			if indeg[v] == 0 && color[v] == WHITE
				color[v] = GRAY
				Q.enqueue(v)

上述算法根据BFS的顺序依次访问入度为0的顶点，并将访问过的顶点添加至链表末尾。

该算法将访问过的顶点u视为“已结束”，同时将下一顶点v（从u出发的边指向的顶点）的入度减1。这一操作相当于删除边。不断地删除边可以是v的入度逐渐降为0，此时我们便可以访问顶点v，然后将v加入链表。

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
def topologicalSort()
	"""将所有节点的color[u]设置为WHITE"""

	for s from 0 to |V| - 1
		if color[s] == WHITE
			dfs(s)
	
def dfs(int u)
	color[u] = GRAY
	for v is the neighbour of u
		if color[v] == WHITE
			dfs(v)
	out.push_fronf(u)	"""将访问计数的顶点逆向添加只链表"""

上述算法通过DFS搜索访问顶点，并把访问完的顶点添加至链表开头。

注意： 由于深度优先搜索时逆向确定各顶点的拓扑排序，因此节点时添加至链表的开头