简介
有向无环图:若一个有向图中不存在环,则称为有向无环图,简称DAG图(Directed Acyclic Graph)
AOV网(Activity On Vertex Network,用顶点表示活动的网):用DAG表示一个工程,顶点表示活动,有向边< V i , V j > <V_i,V_j> < V i , V j > 表示活动V i V_i V i 必须先于V j V_j V j 进行。
拓扑排序是一个有向无环图(DAG)的所有顶点的线性序列,且该序列必须满足下面两个条件:
每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。
实现 :
从AOV网中选择一个没有前驱(入度为0)的顶点并输出;
从网中删除该顶点和所有以它为起点的有向边;
重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止(说明有回路)。
逆拓扑序 :
从AOV网中选择一个没有后继(出度为0)的顶点并输出;
从网中删除该顶点和所有以它为终点的有向边;
重复1和2直到当前的AOV网为空。
思路 :
用一种容器(比如栈,队列,集合)维护当前所有入度为0的点。
每次从容器中取出一个点,删掉他和他的出边,这可能导致一些点入度为0,将新的入度为0的点加入容器。
代码
邻接表:时间复杂度 O ( n + m ) O(n+m) O ( n + m ) , n n n 表示点数,m m m 表示边数
邻接矩阵:时间复杂度 O ( n 2 ) O(n^2) O ( n 2 )
也可以使用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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 const int maxn = 1e5 + 5 ;const int maxe = 2e5 + 5 ;int n; int h[maxn], e[maxe], ne[maxe], idx; int d[maxn];int print [maxn];void add (int x, int y) { e[idx] = y; ne[idx] = h[x]; h[x] = idx++; d[y]++; } bool topsort () { stack <int > s; for (int i = 1 ; i <= n; i ++ ) if (!d[i]) s.push(i); int cnt = 0 ; while (!s.empty()) { int t = s.top(); s.pop(); print [cnt++] = t; for (int i = h[t]; i != -1 ; i = ne[i]) { int j = e[i]; if (-- d[j] == 0 ) s.push(j); } } return cnt == n; }
练习
Life is painting a picture, not doing a sum.