拓扑排序

拓扑排序

思想

拓扑排序: 就是按照逻辑上先后发生的顺序进行排序。

所以只有 有向图 才有拓扑序。

根据定义,如果图中有环则不能拓扑排序。

常用的方法有两种,一种是dfs,一种是根据度来bfs(可以字典序)。

这里主要介绍第二种方法。

  1. 把每一个事件都看作一个点。如果a事件在b事件后面发生,则连一条a到b的有向边。

  2. 如果一个点的入度为0,那么说明没有事件早于它发生,则将它入队。所以我们要先将所有入度为0的点入队。

  3. 每次取队头元素记为u, 将所有与u相连的点的入度减一,如果入度为0了,则入队。

  4. 如果原图中存在环,则最后topo数组内元素的数量一定小于n。

优点:

这种方法是以点为重心,dfs是以边为重心。那么如果有删边的操作,最好就用第二种方法 : 直接入度减一即可。

可以保证拓扑序是按照字典序的。

如果想要输出是字典序的话,需要将队列改为优先队列。( 如果用邻接矩阵实现,需要去重边

注意 : 判环的时候,如果是邻接矩阵实现,则要判重边!

模板

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],topo;   //存图; 记录拓扑序。
int deg[maxn];

void addedge(int u,int v){
G[u].push_back(v);
}

bool Topo(int n){
queue<int> Q;
topo.clear();
for(int i=1;i<=n;i++) if(deg[i] == 0) Q.push(i);
while(!Q.empty()){
int u = Q.front();
Q.pop();
topo.push_back(u);
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(deg[v] > 0){
deg[v]--;
if(deg[v] == 0) Q.push(v);
}
}
}
if(topo.size() != n) return false; //存在环
return true;
}
Thank you for your support!