or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
Graph Algorithm 1
Introduction to Competitive Programming
03/01
拓撲排序
Topological Sort
一種對有向圖的排序方式
定義:
有 \(n\) 個節點,編號從 \(1\) 到 \(n\),要制定一種排序使得
如果有一條邊 a \(\rightarrow\) b, 在排序中 a 就會比 b 還前面。
如果圖不是有向無環圖(DAG),不存在拓撲排序。
做法:
DFS/BFS 都可以做,這邊說 BFS 的


可以觀察到入度為 0 的點在拓撲排序中會在最前面,
放完之後,把 4, 8 連出去的邊移除
接著就繼續將入度為 0 的點加入 queue 裡面, queue 是空的就做完了。
實作:
一開始建圖時,可以用一個陣列 deg[MXN] 紀錄每個點入度多少
建完圖之後,開始拔入度為 0 的點,可以用 queue 儲存要拔掉的點,依序拿出來
實作:
每次從 queue 裡面取出一個點,將他連到的點入度都減 1,減的時候順便確認那個點是否入度為 0 了
複雜度:
拔邊的時候每條邊、點都會經過至少一次
\(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
為什麼會這樣呢?
如果有編號大的數字指向編號小的數字,可能讓編號小的數字較晚被分配到數字,導致字典序變大。
反過來想
如果對原圖建反圖,然後由大到小分配數字,這樣就只會造成編號大的數字比較晚分配到數字,字典序就會是最小的。
DP on DAG
可以觀察到平常的 DP 我們會用到之前用過的答案,如果將這個過程轉換成圖的話,就會變成一張 DAG
反之,如果圖是一張 DAG,依據題目也可以嘗試去轉換成 dp。
例題: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]\)
程式碼:
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 了!
程式碼:
找環
Cycle Detection
在一個圖中找環主要有兩種方式
拓撲排序
拓撲排序的做法就跟前面一樣,可以觀察到如果一張圖有環,做完拓撲之後:
可以根據以上性質用拓撲排序去找圖有沒有環
做完拓撲排序後如果有點沒有被推入佇列就代表圖內有環。
dfs
dfs 時,會將圖變成一棵樹,我們利用的是這顆樹與其他邊的性質,可以分成有向圖跟無向圖兩種。

無向圖
dfs 時會將無向圖的邊分成 tree edge 跟 back edge,
可以很直覺的發現,當一張無向圖有 back edge,就會有環,所以我們在 dfs 時,只要走到同一個點兩次,就可以確認這個圖有環
程式碼:
有向圖
跟無向圖一樣,如果有回邊的話也會有環。
不過 dfs 時會把邊分成四種,除了原本的兩種,還多了 cross edge 跟 forward edge,會留到之後再做介紹。
至於要怎麼判斷有向圖的回邊呢?
可以把節點分成三種,還沒走過的、下面節點還沒走完的、下面節點已經走完的,這樣子在 dfs 時遇到下面節點還沒走完的時,就代表走的那條邊是回邊了。
程式碼
路徑
如果是要找環的路徑,可以將 dfs 改一下,由於環就是回邊造成的,因此環的路徑就是回邊的點到現在所在的點的這條路徑,只要記錄 dfs 樹每個節點是從哪條邊走過來的,就可以找到圖上的一個環。
無向圖找環的程式碼:
有向圖留給大家自己練習>.<
下課
七橋問題
在所有橋只能走過一遍的情況下,如何才能將所有橋走遍。

Note:
星報氣流展
現在的七橋:

歐拉路徑/迴路
Euler Path/Circuit
要怎麼找出一條歐拉路徑/迴路呢?
可以先從判斷一張圖有沒有歐拉路徑開始
一樣分成有向圖和無向圖的判斷方式
無向圖
可以從節點的角度來觀察,每個點都有不同的度數,而度數代表的是可以進出這個點幾次,如果一個點的度數是奇數,如果要走完這樣的節點的邊,需要進出 \(\lfloor \frac{n}{2} \rfloor\) 次,且最後會停在這個節點,反之,如果度數是偶數,則是要進出 \(\frac{n}{2}\) 次,且除了起始點以外,會離開這個節點。
無向圖的歐拉迴路
一張無向圖要有歐拉迴路,對點的要求是每個節點進出都不會被卡在裡面,如果有度數為奇數的點,走完邊的結果會是卡在裡面,因此無向圖歐拉迴路需要無向圖節點的度數都是偶數。
無向圖的歐拉路徑
一張無向圖要有歐拉路徑的條件比迴路寬鬆一點,由於你可以從一個點開始,另一個點結束,所以你可以同時有兩個度數為奇數的點,一個點當起點,另一個點當終點
有向圖的歐拉迴路
有向圖跟無向圖不同的是要完整走完一個節點的邊,需要的是入度與出度相同,只要滿足這條件,就有可能會有歐拉路徑。
有向圖的歐拉路徑
與無向圖相同,可以從一個點開始,另一個點結束,因此有向圖有歐拉路徑的條件是一個點的出度等於入度減一,另一個點的入度等於出度減一,這樣就可以從入度等於出度減一的點作為起點,出度等於入度減一的點作為終點。
歐拉證明了只要滿足以上條件,就一定可以構造出一個歐拉路徑/迴路,統整一下歐拉路徑/迴路成立的條件。
或剛好一個點出度-1=入度
另一點入度-1=出度,
其他點入度等於出度
並且圖連通
找出一條歐拉迴路/路徑
從
入度等於出度減一
的點開始作為起點,並開始 dfs,每次選一條新的邊繼續遞迴,dfs 結束後將點加入路徑中,遞迴後將路徑反轉就是答案了。程式碼
單詞接龍
給定一堆英文單字,詢問是否有一種單字的排列,可以讓連續兩個單字頭尾的字母都一樣
可以將題目轉換成圖論問題,將每個單字轉換成字首字母到字尾字母的有向邊,這樣題目就會變成在找歐拉路徑了。
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 的圖的建圖方式
把圖建完跑一遍歐拉路徑就是一組合法解了
漢米爾頓路徑/環
Hamiltonian path
給定一張圖,是否有一條路徑恰好走過所有節點剛好一次。
與歐拉路徑類似,只是要遍歷的變成了點

與歐拉路徑的問題不同,經過證明,漢米爾頓路徑是 NP-C 的問題,沒有多項式時間的解決方式,
最直接的做法就是對點集找全排列 (
next_permutation
),對每種排列花 \(O(n)\) 時間看可不可行,時間複雜度 \(O(n * n!)\)由於每個點只能走過一次,所以可以將點集分成
已經走過的
、還沒走過的
定義
dp[i][{s}]
為當前在點 i,且已經拜訪過 {s} 這些點了實作時由於 n 不會很大, {s} 會用狀態壓縮的方式去實現,用整數的 bit 去記錄 s 的集合內含有哪些數字。
狀態轉移式:當有一條 i 到 j 的邊且 j 不屬於 s 時 \(dp[j][{s} \cup j] = dp[i][{s}]\)
程式碼:
複雜度: \(O(n^22^n)\)
旅行推銷員問題(TSP)
Travelling Salesman Problem
給定一個完全圖,每個邊都有邊權,求每一個點訪問剛好一次且最後要回到初始地的最短距離。
可以看出這個就是帶權的漢米爾頓迴路,所以也是以類似的方式去實作,放在習題讓大家自己去練習看看^^
Homework
deadline: 3/8
link: this