Graph Algorithm 1

定義：

有 \(n\) 個節點，編號從 \(1\) 到 \(n\)，要制定一種排序使得

如果有一條邊 a \(\rightarrow\) b, 在排序中 a 就會比 b 還前面。

如果圖不是有向無環圖（DAG），不存在拓撲排序。

做法：

DFS/BFS 都可以做，這邊說 BFS 的
可以觀察到入度為 0 的點在拓撲排序中會在最前面，

放完之後，把 4, 8 連出去的邊移除

接著就繼續將入度為 0 的點加入 queue 裡面， queue 是空的就做完了。

實作：

一開始建圖時，可以用一個陣列 deg[MXN] 紀錄每個點入度多少

for(int i=0;i<m;i++){
    cin >> u >> v;    //點 u 連到點 v
    edge[u].push_back(v);
    ++deg[v];
}

建完圖之後，開始拔入度為 0 的點，可以用 queue 儲存要拔掉的點，依序拿出來

for(int i=0;i<n;i++){
    if(!deg[i])    que.push(i); // 度數為 0 時推入佇列中
}

實作：

每次從 queue 裡面取出一個點，將他連到的點入度都減 1，減的時候順便確認那個點是否入度為 0 了

for(int i:edge[u]){
    --deg[i];
    if(deg[i] == 0){ // 當度數為 0 時，將節點推入佇列
        que.push(i);
    }
}

複雜度：

拔邊的時候每條邊、點都會經過至少一次
\(O(N+M)\)

其實也不一定要用 queue 來實作，也可以用其他可以 push 跟 pop 的資料結構，只要是入度為 0 的點，都可以被拿來進行拓撲排序，順序不會影響正確性。

例題： UVA: 10305 - Ordering Tasks

題意：給 n 個工作跟 m 組 pair
每組 pair 代表的是兩個工作的先後順序，前面的會比後面的早做
詢問任意一組合理的工作順序。

可以發現每組 pair 代表的是有向圖的一條邊，我們再圖上求出拓撲排序就可以找到合理的工作順序了。

例題： CF 825E Minimal Labels

題意：給一張有 n 個點 m 條邊的有向圖 (不一定連通)，給編號 1 ~ n 的點都貼上帶有數字的標籤，邊 u \(\rightarrow\) v 的標籤 \(label_u\) 要小於 \(label_v\)。

最後依照編號順序輸出標籤的數字，且字典序要最小。

直接拓撲加上優先佇列（由編號小的先拿）？

如果用正向拓撲加上優先佇列的話，下圖的答案會是
6 5 2 1 4 3?
但答案應該要是
6 3 5 4 2 1

為什麼會這樣呢？

如果有編號大的數字指向編號小的數字，可能讓編號小的數字較晚被分配到數字，導致字典序變大。

反過來想

如果對原圖建反圖，然後由大到小分配數字，這樣就只會造成編號大的數字比較晚分配到數字，字典序就會是最小的。

例題：Game Route

題意：

一個遊戲有 \(n\) 個關卡，有 \(m\) 個傳送器連結。
第 \(i\) 個傳送器會從關卡 \(u_i\) 傳送到關卡 \(v_i\)
詢問從第 1 個關卡到第 n 個關卡有幾種方式？

保證關卡不會經由傳送器回到自己(也就是沒有環)

傳送器只能從關卡 u 到關卡 v，其實就是在說這張圖是一張有向圖，而題目有說沒有環，所以這就會是一張有向無環圖(DAG)。

dp[i] 代表的是走到第 \(i\) 個關卡有幾種方式

而他的 dp 式也可以推成 \(dp[i] = \sum\limits_{edge(i, j)} dp[j]\)

程式碼：

int dfs(int x) {
	if(ans[x] != 0) return ans[x]; // 點已經被走過就回傳答案
	int res = 0;
	for(int i = 0; i < a[x].size(); i++) {
	  res =  (res + dfs(a[x][i]) % 1000000007;
	}
	return ans[x] = res;
}

CSES Reachable Nodes

題意： 給一張 N 個點 M 條邊的 DAG，詢問從每個點作為起點，可以走到的節點數量
\(1 \le n \le 5 * 10^4\)
\(1 \le m \le 10^5\)

跟上一題不一樣的是，上一題要求的是到某個節點的方式有幾種，而這題要求的是可以走到幾個節點，因為沒有直接的結合律，好像沒容易簡單用 dp 去記錄答案。

做法

dp 改成記錄每一個點可以走到哪些點，
dp[1] = dp[2] \(\cup\) dp[3] \(\cup\) 1

做法

所以可以對每個節點都開一個大小為 n 的陣列，記錄這個節點可以走到哪些節點
轉移式
\(dp[i] = dp[i] \cup dp[j]\ \forall \ (i \rightarrow j)\)

不過這樣做的時間複雜度會是 \(O(n (\)陣列大小\() * m (\)更新次數\())\) = \(O(5 * 10^9)\) 還是會超過一秒。

優化

可以用 bitset 去優化轉移的時間，可以發現兩個 dp 取交集時，等價於用 bitset 做位元 or，我們就可以用 bitset 壓一下常數。

在 bitset 優化後，對陣列取交集變成 \(O(\frac{n}{32})\)

最後的複雜度變成 \(O(\frac{5 * 10^9}{32}) \approx O(10^8)\)，就會 AC 了！

程式碼：

bitset<MXN> dp[MXN];
void dfs(int x) {
	v[x] = 1;
	dp[x][x] = 1;
	for(int i : edge[x]) {
		if(!v[i]) dfs(i);
		dp[x] |= dp[i]; // 取兩個集合的交集
	}
};

拓撲排序

拓撲排序的做法就跟前面一樣，可以觀察到如果一張圖有環，做完拓撲之後：

• 有向圖：環上的節點的入度至少為一
• 無向圖：環上的節點的度數至少為二

可以根據以上性質用拓撲排序去找圖有沒有環

• 有向圖：節點度數為 0 時，將節點推入佇列內
• 無向圖：節點度數為 1 時，將節點推入佇列內

做完拓撲排序後如果有點沒有被推入佇列就代表圖內有環。

dfs

dfs 時，會將圖變成一棵樹，我們利用的是這顆樹與其他邊的性質，可以分成有向圖跟無向圖兩種。

無向圖

dfs 時會將無向圖的邊分成 tree edge 跟 back edge，

• tree edge：dfs 時遇到新的點時走的邊
• back edge：dfs 時遇到自己祖先的點時走的邊

可以很直覺的發現，當一張無向圖有 back edge，就會有環，所以我們在 dfs 時，只要走到同一個點兩次，就可以確認這個圖有環

程式碼：

int vis[N];
bool dfs(int x, int v) {
	if(vis[x]) return true; // 遇到祖先就代表有環，回傳 true
	vis[x] = 1;
	for(auto i:g[x]) {
		if(i == v) continue;
		if(dfs(i, x)) {
			return true;
		}
	}
	return false;
}

有向圖

跟無向圖一樣，如果有回邊的話也會有環。
不過 dfs 時會把邊分成四種，除了原本的兩種，還多了 cross edge 跟 forward edge，會留到之後再做介紹。

至於要怎麼判斷有向圖的回邊呢？

可以把節點分成三種，還沒走過的、下面節點還沒走完的、下面節點已經走完的，這樣子在 dfs 時遇到下面節點還沒走完的時，就代表走的那條邊是回邊了。

程式碼

bool dfs(int x, int v) {
	if(vis[x] == 1) return true; // 當走到還沒走完的點，就代表有環
	if(vis[x] == 2) return false; // 走到已經走完的節點，當沒事發生
	vis[x] = 1; // 標記這個點還沒被走完
	for(auto i:g[x]) {
		if(dfs(i, x)) {
			return true;
		}
	}
	vis[x] = 2; // 標記這個點已經被走完
	return false;
}

路徑

如果是要找環的路徑，可以將 dfs 改一下，由於環就是回邊造成的，因此環的路徑就是回邊的點到現在所在的點的這條路徑，只要記錄 dfs 樹每個節點是從哪條邊走過來的，就可以找到圖上的一個環。

無向圖找環的程式碼：

int vis[], suc[];
int dfs(int x, int v) {
	if(vis[x]) return x;
	suc[x] = v;
	vis[x] = 1;
	for(auto i:g[x]) {
		int tmp = dfs(i, x); // x 的祖先，
		if(tmp) {
			int now = x;
			while(now != tmp) { // 找從 x 到 tmp 的路徑
				cout << now << ' ';
				now = suc[now];
			}
			cout << tmp << ' ' << x << '\n';exit(0);
		}
	}
	return 0;
}

有向圖留給大家自己練習>.<

現在的七橋：

歐拉路徑/迴路

Euler Path/Circuit

• 歐拉路徑: 選一個節點當起點，可以走過所有的邊剛好一次
• 歐拉迴路: 選一個節點當起點，可以走過所有的邊剛好一次，且最後回到原本的起點

要怎麼找出一條歐拉路徑/迴路呢？
可以先從判斷一張圖有沒有歐拉路徑開始
一樣分成有向圖和無向圖的判斷方式

無向圖

可以從節點的角度來觀察，每個點都有不同的度數，而度數代表的是可以進出這個點幾次，如果一個點的度數是奇數，如果要走完這樣的節點的邊，需要進出 \(\lfloor \frac{n}{2} \rfloor\) 次，且最後會停在這個節點，反之，如果度數是偶數，則是要進出 \(\frac{n}{2}\) 次，且除了起始點以外，會離開這個節點。

無向圖的歐拉迴路

一張無向圖要有歐拉迴路，對點的要求是每個節點進出都不會被卡在裡面，如果有度數為奇數的點，走完邊的結果會是卡在裡面，因此無向圖歐拉迴路需要無向圖節點的度數都是偶數。

無向圖的歐拉路徑

一張無向圖要有歐拉路徑的條件比迴路寬鬆一點，由於你可以從一個點開始，另一個點結束，所以你可以同時有兩個度數為奇數的點，一個點當起點，另一個點當終點

有向圖的歐拉迴路

有向圖跟無向圖不同的是要完整走完一個節點的邊，需要的是入度與出度相同，只要滿足這條件，就有可能會有歐拉路徑。

有向圖的歐拉路徑

與無向圖相同，可以從一個點開始，另一個點結束，因此有向圖有歐拉路徑的條件是一個點的出度等於入度減一，另一個點的入度等於出度減一，這樣就可以從入度等於出度減一的點作為起點，出度等於入度減一的點作為終點。

歐拉證明了只要滿足以上條件，就一定可以構造出一個歐拉路徑/迴路，統整一下歐拉路徑/迴路成立的條件。

並且圖連通

找出一條歐拉迴路/路徑

從 入度等於出度減一 的點開始作為起點，並開始 dfs，每次選一條新的邊繼續遞迴，dfs 結束後將點加入路徑中，遞迴後將路徑反轉就是答案了。

程式碼

vector<int> path;
void dfs(int x){
    while(!edge[x].empty()){
        int u = edge[x].back();
        edge[x].pop_back();
        dfs(u);
    }
    path.push_back(x);
}
 
int main(){
    build_graph();
    dfs(st);
    reverse(path.begin(),path.end());
    for(int i:path)    cout<<i<<' ';
    cout<<endl;
}
vector<int> path;
void dfs(int x){
    while(!edge[x].empty()){
        int u = edge[x].back();
        edge[x].pop_back();
        dfs(u);
    }
    path.push_back(x);
}
 
int main(){
    build_graph();
    dfs(st);
    reverse(path.begin(),path.end());
    for(int i:path)    cout<<i<<' ';
    cout<<endl;
}
vector<int> path;
void dfs(int x){
    while(!edge[x].empty()){
        int u = edge[x].back();
        edge[x].pop_back();
        dfs(u);
    }
    path.push_back(x);
}
 
int main(){
    build_graph();
    dfs(st);
    reverse(path.begin(),path.end());
    for(int i:path)    cout<<i<<' ';
    cout<<endl;
}
vector<int> path;
void dfs(int x){
    while(!edge[x].empty()){
        int u = edge[x].back();
        edge[x].pop_back();
        dfs(u);
    }
    path.push_back(x);
}
 
int main(){
    build_graph();
    dfs(st);
    reverse(path.begin(),path.end());
    for(int i:path)    cout<<i<<' ';
    cout<<endl;
}
vector<int> path;
void dfs(int x){
    while(!edge[x].empty()){
        int u = edge[x].back();
        edge[x].pop_back();
        dfs(u);
    }
    path.push_back(x);
}
 
int main(){
    build_graph();
    dfs(st);
    reverse(path.begin(),path.end());
    for(int i:path)    cout<<i<<' ';
    cout<<endl;
}

單詞接龍

給定一堆英文單字，詢問是否有一種單字的排列，可以讓連續兩個單字頭尾的字母都一樣

可以將題目轉換成圖論問題，將每個單字轉換成字首字母到字尾字母的有向邊，這樣題目就會變成在找歐拉路徑了。

de Bruijn 序列

de Bruijn 序列是一個字串，這個字串包含了長度為 n 且每個字母有 k 種可能的字串

例如，當 n = 3, k = 2 時，de Bruijn 序列的其中一種可能性是 0001011100，他有 000, 001, 010, 011, 100, 101, 110和111 的子字串

通過一些證明，de Bruijn 序列的長度固定會是 \(k^n + n - 1\)

首先，我們對所有長度為 n - 1 的子字串作為節點建立一張圖
一樣以 n = 3, k = 2 為例：

每個節點連出連出的邊會有 k 種，而連到的節點則是將本來所在節點的第一個 bit 刪掉，並在後面將邊上代表的 bit 放在最後面。

得到 de Bruijn 序列的方式就是，從任意一個點開始，找到圖的歐拉迴路， de Bruijn 序列就會是起始節點的字串加上邊上所有的bit。

為什麼這樣會是好的呢，可以觀察到，序列 abc 可以通過 ab 節點的前面兩個節點連接的邊構成，而 c 就會是連出去的邊，我們只要找到任意的歐拉路徑，代表就可以構出所有長度為 n 且有 k 種可能性的子字串

建圖程式碼：

n = n, k = 2 的圖的建圖方式

for (int i = 0; i < (1<<(n-1)); i++){
	v[i].push_back(((i<<1))&((1<<(n-1))-1));
	v[i].push_back(((i<<1)+1)&((1<<(n-1))-1));
}

把圖建完跑一遍歐拉路徑就是一組合法解了

與歐拉路徑的問題不同，經過證明，漢米爾頓路徑是 NP-C 的問題，沒有多項式時間的解決方式，
最直接的做法就是對點集找全排列 (next_permutation)，對每種排列花 \(O(n)\) 時間看可不可行，時間複雜度 \(O(n * n!)\)

由於每個點只能走過一次，所以可以將點集分成 已經走過的、還沒走過的

定義 dp[i][{s}] 為當前在點 i，且已經拜訪過 {s} 這些點了

實作時由於 n 不會很大， {s} 會用狀態壓縮的方式去實現，用整數的 bit 去記錄 s 的集合內含有哪些數字。

i = 3，{s} = 11001 代表的就是已經走過 0、3、4 三點，且目前在 3 的位置

狀態轉移式：當有一條 i 到 j 的邊且 j 不屬於 s 時 \(dp[j][{s} \cup j] = dp[i][{s}]\)

if(((1 << i) & s) && !((1 << j) & s)) {
	dp[j][s | (1 << j)] = dp[i][s];
}

程式碼：

for(int i = 1; i < (1 << n); i++) {
	for(int j = 0; j < n; ++j) {
		if(!((1 << j) & i)) {
			for(int k = 0; k < n; k++) {
				if(j == k) continue;
				if((1 << k) & i) {
					dp[j][i | (1 << j)] = dp[k][i];
				}
			}
		}
	}
}

複雜度: \(O(n^22^n)\)

旅行推銷員問題(TSP)

Travelling Salesman Problem

給定一個完全圖，每個邊都有邊權，求每一個點訪問剛好一次且最後要回到初始地的最短距離。

可以看出這個就是帶權的漢米爾頓迴路，所以也是以類似的方式去實作，放在習題讓大家自己去練習看看^^