拓扑序
有向无环图 DAG,对每一个顶点给一个编号,第i号顶点叫做v,那么存在顶点 v~i~ 到顶点v~j~ 的边时,就有i<j 成立,这样的编号方式叫做拓扑序 。
拓扑排序
如果把图(a)中的顶点按照拓扑序从右到左排列,那么所有的边都是从左指向右的。求解拓扑序的算法叫做拓扑排序 。
DFS算法
使用栈以使结果为正向排序,由于每个顶点和每条边都只访问了一次,因此复杂度时O(|V|+|E|).
已知为DAG的情况
对每一个节点设置属性visited为0或1,未访问过为0,访问过为1.
dfs(u)
其中n为节点,不断深入递归,当其所有子节点都已被访问过之后才会退出。
所以可以知道最先被访问的必定是拓扑序最大的,则先将其push
至栈中,最后从栈中取出时即为正序。
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 41 42 43 44 45 46 47 48 #include <iostream> #include <stack> using namespace std ;struct Edge { int to, next; }; const int maxn = 10010 ;int head[maxn] = {};int n, m, cnt = 1 ;bool vis[maxn] = {};Edge edge[maxn]; stack <int > S;void add (int u, int v) { edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++; } void dfs (int u) { vis[u] = true ; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (!vis[v]) dfs(v); } S.push(u); } int main () { cin >> n >> m; for (int i = 1 ; i <= m; ++i) { int u, v; cin >> u >> v; add(u, v); } for (int i = 1 ; i <= n; ++i) { if (vis[i] == 0 ) dfs(i); } while (!S.empty()) { cout << S.top() << ' ' ; S.pop(); } }
判环
那么,如何判环呢?判环只是在dfs
函数上稍做些修改,其中最主要的是vis
数组的含义有所扩展,以及对下一结点进行dfs
的条件判断。
不判环的拓扑排序,vis
只代表某一结点有没有被放问过,而现在,vis
有三个值,-1,0,1。
-1 代表已访问过,但不是从当前系列dfs
访问来的,0 代表未访问过,1 代表访问过,且是当前系列访问过的(意味着有环,如u->v
, v->t
, t->u
)
1 2 3 4 5 6 7 8 9 10 11 12 bool dfs (int u) { vis[u] = 1 ; for (int i = head[u]; i; i = edge[i].next) { int v = edge[i].to; if (vis[v] == 1 ) return false ; if (vis[v] == 0 && !dfs (v)) return false ; } vis[u] = -1 ; S.push (u); return true ; }
Kahn算法
其实就是不断的寻找有向图中没有前驱(入度为0)的顶点,将之输出。然后从有向图中删除所有以此顶点为尾的弧。重复操作,直至图空,或者找不到没有前驱的顶点为止。
该算法还可以判断有向图是否存在环(存在环的有向图肯定没有拓扑序列),通过一个count记录找出的顶点个数,如果少于N则说明存在环使剩余的顶点的入度不为0。(degree数组记录每个点的入度数)
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 #include <bits/stdc++.h> using namespace std;const int maxn = 505 ;struct node { int v, next; }edge[maxn*maxn]; int degree[maxn], head[maxn];queue<int > q; list<int > ans; int n, m, no;inline void init () { no = 0 ; while (!q.empty ()) q.pop (); memset (degree, 0 , sizeof degree); memset (head, -1 , sizeof head); } inline void add (int u, int v) { edge[no].v = v; edge[no].next = head[u]; head[u] = no++; } int Kahn () { int count = 0 ; while (!q.empty ()) { int tp = q.front (); q.pop (); ++count; ans.push_back (tp); int k = head[tp]; while (k != -1 ) { --degree[edge[k].v]; if (!degree[edge[k].v]) q.push (edge[k].v); k = edge[k].next; } } if (count == n) return 1 ; return 0 ; } int main () { int u, v; scanf ("%d %d" , &n, &m); init (); for (int i = 1 ; i <= m; ++i) { scanf ("%d %d" , &u, &v); add (u, v); ++degree[v]; } for (int i = 1 ; i <= n; ++i) { if (!degree[i]) q.push (i); } Kahn (); list<int >::iterator it; for (it = ans.begin (); it != ans.end (); ++it) { cout << *it << " " ; } cout << endl; return 0 ; }