拓撲排序-Uva10305 給任務排序 題解(第一節 dfs解法）

一、拓撲排序

對一個有向無環圖(Directed Acyclic Graph簡稱DAG)G進行拓撲排序，是将G中所有頂點排成一個線性序列，使得圖中任意一對頂點u和v，若邊<u,v>∈E(G)，則u線上性序列中出現在v之前。通常，這樣的線性序列稱為滿足拓撲次序(Topological Order)的序列，簡稱拓撲序列。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。（來自百度百科）

可以将圖的拓撲排序看作是将圖的所有結點在一條水準線上排開，圖的所有有向邊都從左指向右。（來自《算法導論》）

事實上簡單點說，就是在排序過程中，之前圖上有邊<v,u>的情況下，排序之後v在u前。UVa10305顯然是一道模闆題。

拓撲排序基本思路：每次将入度為0的節點分離出來，再将這個節點所指向的節點的入度減1。重複進行此操作直到所有點分離出來。如果最後不存在入度為0的節點，則說明有環，拓撲排序無解。（是以拓撲排序有些時候被用來進行判環操作）。

二、UVa10305 給任務排序題解（DFS版）

代碼及注釋如下（代碼核心是紫書上的）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1050;
int G[maxn][maxn];
int c[maxn];
int ans[maxn];
int n,m,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[v]都不滿足的話，就直接跳掉了這一句（不用算後面dfs了減少了運算）（!dfs代表通路完所有子孫，無法拓展） 
	}
	c[u]=1;                                      //标記 
	ans[--t]=u;                                  //u此時已經被取出了，應将取出的點放在拓撲序列的首部 
	return true; 
}
bool toposort(){
	t=n;                                         //這裡不能直接修改n 
	for(int i=0;i<n;i++){ if(!c[i])
	  if(!dfs(i)) return false;                  //不管toposort結果如何，都要執行這個函數，隻是執行成功的話，傳回值為true，就可以繼續輸出所運算出的正确答案。如果toposort執行結果為false，則沒有輸出資料的機會，隻是輸出一個No 
	}
	return true;
}
int main(){
    freopen("in.txt","r",stdin);
	  freopen("out.txt","w",stdout);
	  int x,y;
		while(scanf("%d%d",&n,&m)==2 && n){        //多組資料 
			memset(G,0,sizeof(G));
			memset(c,0,sizeof(c));
			for(int i=0;i<m;i++){
				cin>>x>>y;
				x--;                                   //這裡讓下标從0起記 
				y--;
				G[x][y]=1;                             //代表x是y的前置任務 
			}

			if(toposort()){                          //輸出 
			  for(int i=0;i<n-1;i++) cout<<ans[i]+1<<' ';
			  cout<<ans[n-1]+1<<endl;
		  }
		  else cout<<"No"<<endl;
		}
		
    return 0;
}
           

作者

Bowen

本文作者水準有限，如有纰漏，敬請斧正。

未完待續…（第二節BFS解法）