拓扑排序

有向无环图

· 如果有一个有向图的任意顶点都无法通过一些有向边回到自身,那么称这个有向图为有向无环图(Directed Acyclic Graph,DAG)

拓扑排序

· 拓扑排序是将有向无环图G的所有顶点排成一个线性序列,使得图G中的任意两个顶点u、v,如果存在边u->v,那么在序列中u一定在v前面,这个序列又被称为拓扑序列

步骤

1.定义一个队列Q,把所有入度为0的结点加入队列
2.取队首结点,输出,然后删去所有从它出发的边,并令这些边到达的顶点的入度减1.如果某个顶点的入度减为0,则将其加入队列。
3.反复进行2操作知道队列为空。如果队列为空时入过队的结点数目恰好为N,说明拓扑排序成功,图G为有向无环图,否则,拓扑排序失败,图G中有环

邻接表实现

由于需记录每个节点的入度,故需增设数组inDegree[maxn]

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
vector<int> G[maxn];
int n,m,inDegree[maxn];
//拓扑排序
bool topologicalSort(){
int num=0;
queue<int> q;
for(int i=0;i<n;i++){
if(inDegree[i]==0)
q.push(i);
}
while(!q.empty()){
int u=q.front();
//printf("%d ",u); 此处可输出顶点u,以输出拓扑排序
q.pop();
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
inDegree[v]--;
if(inDegree[v]==0)
q.push(v);
}
G[u].clear(); //清空u的出边,无必要可不写
num++;
}
if(num==n) return true;
else return false;
}