拓撲排序
文章目錄
- 拓撲排序
- 1.有向無環圖
- 2.拓撲排序
- 3.CodeUp例題
- 總結
1.有向無環圖
一個無環的有向圖稱做有向無環圖（Directed Acyclic Graph，DAG），它是指一個有向圖的任意頂點都無法通過一些有向邊回到起點，
2.拓撲排序
拓撲排序是將有向無環圖G的所有頂點排成一個線性序列，使得對圖G中的任意兩個頂點u,v,如果存在邊u->v，那么在序列中u一定在v前面，這個序列被稱為拓撲排序，
比如在實驗室的諸葛老師讓啥都不會的你設計一個逆變器！你只能先從C語言，電路開始，一步步向后最終完成設計逆變器的目標，
同時還可以發現，若各種技術之間的先導關系不是直接或間接的，那么學習的順序可任意決定，于是可以把上面的要學習的技識訓者課程排成一個學習的先后序列，使得序列滿足先導順序，
（電力電子，狗都不學🐕）
根據上面的圖，拓撲排序就不難理解了，簡單來說，就是如果有先導的結點，就先訪問先導結點；如果沒有先導結點或已訪問果先導結點，那么這些結點的順序任意，對應到圖中，這個程序可以抽象為以下步驟：
- 定義一個佇列Q，并把所有度為0的結點加入佇列；
- 取隊首結點，輸出，然后刪去所有從它出發的邊，并令這些邊到達的頂點的入度減一，如果某個頂點的入度減為0，則將其加入佇列，
- 反復進行②操作，直到佇列為空為止，如果佇列結束時，入過對的結點數恰好為N，說明拓撲排序成功，圖G為有向無環圖，否則，拓撲排序失敗，圖G中有環，
可以使用鄰接表實作拓撲排序，并增加一個陣列記錄結點的入度，拓撲排序的代碼如下：
vector<int> G[MAXV];
int n, inDegree[MAXV];
//拓撲排序
bool toplogicalSort()
{
int num = 0;//記錄加入排序的頂點數
queue<int> q;
for (size_t i = 0; i <n; i++)
{
if (inDegree[i] == 0)
{
q.push(i);//將度為0的點入隊
}
}
while (!q.empty())
{
int u = q.front();//取出隊首頂點
q.pop();
for (int i = 0; i < G[u].size; i++)
{
int v = G[u][i];//后繼結點v
inDegree[v]--;//度減一
if (inDegree[v] ==0)
{
q.push(v);
}
}
G[u].clear();
num++;
}
if (num == n) return true;
else return false;
}
拓撲排序的重要應用就是判斷一個給定的圖是否是有向無環圖，正如上面的代碼，如果函式回傳真，則說明排序成功，圖是有向無環圖，否則，說明拓撲排序失敗，給定的圖中有環，
值得注意的是，如果要求有多個入度為0的頂點，選擇編號最小的頂點，那么把queue改成priority_queue,并保持隊首元素是優先佇列中最小的元素即可，
3.CodeUp例題
原題 CodeUp新家 Problem B: 確定比賽名次.
Description
有N個比賽隊（1<=N<=500），編號依次為1，2，3，，，，，，N進行比賽，比賽結束后，裁判委員會要將所有參賽隊伍從前往后依次排名，但現在裁判委員會不能直接獲得每個隊的比賽成績，只知道每場比賽的結果，即P1贏P2，用P1，P2表示，排名時P1在P2之前，現在請你編程式確定排名，
Input
輸入有若干組，每組中的第一行為二個數N（1<=N<=500），M；其中N表示隊伍的個數，M表示接著有M行的輸入資料，接下來的M行資料中，每行也有兩個整數P1，P2表示即P1隊贏了P2隊，
Output
給出一個符合要求的排名，輸出時隊伍號之間有空格，最后一名后面沒有空格，
其他說明：符合條件的排名可能不是唯一的，此時要求輸出時編號小的隊伍在前；輸入資料保證是正確的，即輸入資料確保一定能有一個符合要求的排名，
Example
3 2
3 1
3 2
17 16
16 1
13 2
7 3
12 4
12 5
17 6
10 7
11 8
11 9
16 10
13 11
15 12
15 13
17 14
17 15
17 16
0 0
代碼
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn=100005;
int ind[maxn];
vector<int > G[maxn];
void print_Topological_sort(int n)
{
priority_queue<int,vector<int>,greater<int> > q;
for(int i=1;i<=n;i++)
{
if(ind[i]==0){
q.push(i);
}
}
while(!q.empty())
{
int u=q.top();
q.pop();
cout<<u<<" ";
for(int j=0;j<G[u].size();j++)
{
int v=G[u][j];
ind[v]--;
if(ind[v]==0)
{
q.push(v);
}
}
G[u].clear();
}
fill(ind,ind+n+1,0);
for(int i=0;i<=n;i++) G[i].clear();
cout<<endl;
}
int main()
{
int N,M,a,b;
while(cin>>N>>M)
{
if(N==0||M==0) break;
for(int i=0;i<M;i++)
{
cin>>a>>b;
G[a].push_back(b);
ind[b]++;
}
print_Topological_sort(N);
}
return 0;
}
總結
byebye~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/283097.html
標籤：其他