拓撲排序
從離散數學的角度定義，假設(A,≤)是有限偏序集，對其進行拓撲排序是指将其擴充成一個全序集，使得≤∈<，即對任意的a,b∈A,若a≤b,則a<b。
從圖論的角度定義，對一個有向無環圖G進行拓撲排序，是将G中所有的頂點排成一個線性序列，使得圖中任意一對頂點u和v,如果(u,v)∈E(G),則u線上性序列中應出現在v之前。
思路
從離散數學的角度定義，拓撲排序是針對有限偏序集的，由離散數學的知識知，若(A,≤)是偏序集，則拟序集(A,<)中不存在長度大于1的環（這其實與無環圖對應）,是以有限偏序集可以畫成哈斯(Hasse)圖。Hasse圖非空時總存在極小元，每次輸出極小元，更新Hasse圖，直到Hasse為空。
從圖論的角度，極小元等同于圖中入度為0的頂點，每次輸出入度為0的點，更新與之相連點的入度，直到輸出全部頂點。如果存在頂點沒有輸出，說明存在環。
樣題
給任務排序(UVa10305)
假設有n個任務，還有m個二進制組(u,v)，(u,v)表示u必須在v之前執行。請輸出n個任務按順序執行的一種可能情況。
代碼實作
鄰接矩陣+隊列
1 #include<stdio.h>
2 #include<cstring>
3 #include<queue>
4 #include<vector>
5 using namespace std;
6
7 const int V = 100 + 10; //最大頂點數
8 const int E = 100 * 100 + 10; //最大邊數
9 vector<int>e[V]; //鄰接矩陣存圖
10 int in[V]; //頂點的入度
11
12 int m, n;
13
14 int main()
15 {
16 while (scanf("%d%d", &n, &m) == 2 && n)
17 {
18 for (int i = 0; i < n; i++)
19 {
20 e[i].clear();
21 in[i] = 0;
22 }
23 for (int i = 0; i < m; i++)
24 {
25 int from, to;
26 scanf("%d%d", &from, &to);
27 e[from].push_back(to);
28 in[to]++;
29 }
30 vector<int>ans;
31 queue<int>q;
32 for (int i = 1; i <= n; i++) if (!in[i]) q.push(i); //将入度為0的入隊
33 while (!q.empty())
34 {
35 int u = q.front(); q.pop();
36 ans.push_back(u);
37 for (int i = 0; i < e[u].size(); i++) //周遊與之相連的頂點
38 if ((--in[e[u][i]]) == 0) q.push(e[u][i]); //入度減1，如果為0，入隊
39 }
40 for (int i = 0; i < ans.size(); i++)
41 printf("%d ", ans[i]);
42 printf("\n");
43 }
44 return 0;
45 } dfs
1 #include<stdio.h>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 #include<vector>
6 #include<cstring>
7 using namespace std;
8
9 const int maxn = 100 + 10;
10 vector<int>G[maxn];
11 int c[maxn], topo[maxn], t;
12 int n, m;
13
14 bool dfs(int u)
15 {
15 if(vis[u]==1) return true;
16 c[u] = -1; //正在通路,dfs(u)正在棧幀中，尚未傳回
17 for (int i = 0; i < G[u].size(); i++)
18 {
20 if (c[G[u][i]] < 0) return false;
22 else if (!c[G[u][i]] && !dfs(G[u][i])) return false;
24 }
25 c[u] = 1; //已經通路過，dfs(u)已被調用過，并已通路
26 topo[--t] = u;
27 return true;
28 }
29
30 bool toposort()
31 {
32 t = n;
33 memset(c, 0, sizeof(c));
34 for (int i = 1; i <= n; i++)
35 if (!c[i] && !dfs(i)) //c[i]為0表示從未通路過
36 return false;
37 return true;
38 }
39
40 void slove()
41 {
42 if (toposort())
43 {
44 for (int i = n - 1; i >= 0; i--)
45 printf("%d ", topo[i]);
46 printf("\n");
47 }
48 }
49
50 int main()
51 {
52 int u, v;
53 while (scanf("%d%d", &n, &m) == 2 && n)
54 {
55 for (int i = 0; i <= n; i++) G[i].clear();
56 for (int i = 0; i < m; i++)
57 {
58 scanf("%d%d", &u, &v);
59 G[v].push_back(u);
60 }
61 slove();
62 }
63 return 0;
64 } 參考連結：
https://baike.baidu.com/item/拓撲排序/5223807?fr=aladdin
https://blog.csdn.net/qq_41713256/article/details/80805338
中國大學mooc 劉铎 離散數學
個性簽名：時間會解決一切