拓撲排序-兩種實現
拓撲排序-兩種實現
來自專欄程序員的成長之路
拓撲排序的應用在演算法中還是比較多的，比如任務調度，順序性訪問圖（比如上一篇文章中我們講的有向圖求最長路），今天我們講解兩種方法來實現拓撲排序
拓撲排序
對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是將G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊(u,v)∈E(G)，則u在線性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序
方法一：
演算法描述：
演算法主導：深度優先搜索
訪問一個未訪問過的節點，將他標記為訪問狀態
訪問它的所有出邊
如果訪問到的子代節點的狀態是訪問狀態，結束，存在有向環，不存在拓撲排序
如果訪問到的子代節點雖然還未訪問，但是它的子代節點存在有向環，結束，不存在
訪問出邊結束後，將節點標記為結束狀態
訪問所有節點後結束
實現例題：
Ordering Tasks - UVA 10305 - Virtual Judge
代碼實現：
#include<bits/stdc++.h>#define maxn 101using namespace std;int n,m;int cur[maxn];//狀態數組 int topo[maxn];//答案數組 int head[maxn];//鄰接表的實現，不喜歡這種實現的小夥伴可以用vector數組 int last[maxn*maxn];struct node{ int s; int t; node(int x,int y) { s = x; t = y; }};vector<node> v;int t;bool dfs(int u){ cur[u] = -1;//標記為訪問狀態 for(int i=head[u];i!=-1;i = last[i]) { if(cur[v[i].t]<0) return false;//節點處於訪問狀態，存在有向環，返回錯誤 if(!cur[v[i].t]&&!dfs(v[i].t)) return false ;//雖然該節點沒有訪問，但是他的子節點出現有向環，返回錯誤 } cur[u] = 1;//標記為結束狀態 topo[--t] = u; return true;}void init()//初始化 { memset(head,-1,sizeof(head)); memset(last,-1,sizeof(last)); memset(cur,0,sizeof(cur)); t = n; int x,y; v.clear(); for(int i=0;i<m;i++) { cin>>x>>y; v.push_back(node(x,y)); last[i] = head[x]; head[x] = i; }}bool topo_sort(){ for(int i=1;i<=n;i++) { if(!cur[i]) if(!dfs(i)) return false; } return true;}void AC(){ while(cin>>n>>m&&(m||n)) { init(); if(topo_sort()) for(int i=0;i<n;i++) cout<<topo[i]<<" "; cout<<endl; }}int main(){ AC(); return 0;}
方法二：
演算法描述：
演算法基礎：
入度：有向圖中有多少條邊指向該節點
實現過程：
找到所有入度為零的點，入隊
訪問隊首，隊首出隊，所有隊首的出邊的另一個節點的出度減一
重複第一步
實現代碼
#include<bits/stdc++.h>#define maxn 101using namespace std;struct node{ int s; int t; node(int x,int y) { s = x; t = y; }};vector<int> ans;//答案 vector<node> v;queue<int> q;//隊列 bool book[maxn];//標記數組，不能重複訪問 int head[maxn];int last[maxn*maxn];int de[maxn];//度 int n,m;void init(){ memset(head,-1,sizeof(head)); memset(last,-1,sizeof(last)); memset(book,0,sizeof(book)); memset(de,0,sizeof(de)); v.clear(); int x,y; for(int i=0; i<m; i++) { cin>>x>>y; v.push_back(node(x,y)); de[y]++; last[i] = head[x]; head[x] = i; }}void find_point()//找到入度為0的點，入隊 { for(int i=1; i<=n; i++) { if(!book[i]&&!de[i]) { q.push(i); book[i] = true; } }}void topo_sort(){ ans.clear(); find_point(); while(!q.empty()) { int t = q.front(); q.pop(); ans.push_back(t); for(int i = head[t]; i!=-1; i = last[i]) { de[v[i].t]--; } find_point(); } if(ans.size()<n) cout<<"false"<<endl; else for(int i=0; i<n; i++) cout<<ans[i]<<" "; cout<<endl;}void AC(){ while(cin>>n>>m&&(n||m)) { init(); topo_sort(); }}int main(){ AC(); return 0;}
希望大家在看懂之後自己去實現一下例題，注意輸入，AC的感覺還是不錯的，加油啊
我們下篇文章再見了
推薦閱讀：
