今天搞了一天拓扑排序,在学习的过程中发现大多数博客不是看不懂就是只针对一种情况,于是这里小总结一下。
一、定义
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若<u,v> ∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
注意:
1)只有有向无环图才存在拓扑序列;
2)对于一个DAG,可能存在多个拓扑序列;
二、拓扑序列算法思想
(1)从有向图中选取一个没有前驱(即入度为0)的顶点,并输出之;
(2)从有向图中删去此顶点以及所有以它为尾的弧;
重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。
用排课程表讲解拓扑排序很容易理解:
有许多课程是需要在学习了其它课程做基础才学习其它课程,例如:必须学完计算机基础才能学数据机构。如果这门课是最基础的那它的入度(即:需要学习完几门课之后在学习它,它的入度就是几)为零。
模版(矩阵):
int topo[2003],n; char g[2002][2003]; memset(topo,0,sizeof(topo)); int toposort() { int f=0; for(int i=0;i<n;i++) { f=0; for(int j=0;j<n;j++) if(topo[j]==0) { f=1; topo[j]=-1; for(int k=0;k<n;k++) if(g[j][k]==1) { topo[k]--; } break; } if(f==0) return 0; } return 1; }
f标记是否存在环。
模版(深搜):
int c[MAXN],G[MAXN][MAXN]; int topo[MAXN],t; bool dfs(int u) { c[u]=-1; for(int v=0;v<n;v++) if(G[u][v]) { if(c[v]<0) return false ; else if(!c[v]&&!dfs(v)) return false ; } c[u]=1;topo[--t]=u; return true ; } bool toposort() { t=n; memset(c,0,sizeof(c)); for(int u=0;u<n;u++) if(!c[u]) if(!dfs(u)) return false ; return true ; }