# AP325-Python 第7章 基本圖論演算法
「BFS、DFS、與Dijkstra演算法之間有何差異？」
「BFS像是小寶寶自己找父母，出生第一眼就到的就認做parent；DFS像是幫孩子找爹娘，最後結婚生下的才是你孩子的parent；Dijkstra則是長大後自己找乾爹乾媽，最有利的才是乾爹乾媽。」
「那麼，Prim與Dijkstra演算法的差異呢？」
「認乾爹乾媽的依據稍有不同。Prim只看乾爹乾媽對你有多好，Dijkstra則除了對你多好之外，還有他從祖先繼承了多少會留給你的財產。」
---
這一章介紹圖(graph)，圖是用來表達二元關係的一種方式，有很多重要的應用，也發展出很多特殊的演算法，這些演算法都是過去科學家研究發展出來的，也就是說，我們要了解它的話，需要靠學習與理解，很難只靠基本的演算法原則自己去想出來。
圖在競賽程式中也扮演了很重要的腳色，但基於高中資訊領域的範圍與APCS的考試範圍，這份教材只會包含一些圖的基本演算法。本章內容包含：圖的基本觀念與名詞、儲存圖的資料結構、廣度優先搜尋、深度優先搜尋、以及DAG與拓樸順序。
在本章最後我們則介紹了三個比較進階的技術，包括Dijkstra演算法、併查集、以及最小生成樹。至於在樹狀圖上做計算的相關問題則留在下一章。
## 基本觀念與名詞
資料結構與演算法中稱的圖(graph)與我們日常生活中的圖(地圖，圖形，藍圖)不太一樣，這裡指的是圖論(graph theory)中的圖，而圖論算是離散數學中的一支。
Graph基本上是二元關係的一種表達方式，目的在研究一群事物中兩兩之間的關係。一個圖寫作$G=(V,E)$，表示一個圖名字是$G$，由點的集合$V$與邊的集合$E$組成，其中$V$是點集合，也就是要研究的對象；而$E$是邊的集合，也就是誰與誰之間存在這種關係。
上圖是一個例子，圖中四個圓圈代表我們要研究的四個人，研究的關係是誰喜歡誰，因此，有一條線從1指到2表示1喜歡2，記做(1,2)。同樣的，圖中還有另外4個邊(1,3)、(2,3)、(3,2)與(4,3)，分別代表1喜歡3、2喜歡3、3喜歡2以及4喜歡3。圖中沒出現的邊，就表示該二者之間沒有這種關係，例如1沒有喜歡4，2沒有喜歡1。
圖的術語很多，以下我們介紹一些基本術語，另外有一些在我們碰到的時候再介紹。
* 有向圖與無向圖(directed and undirected graph)：邊有方向性的圖是有向圖，通常以箭頭表示邊。有向圖表示的是非對稱的二元關係，如上圖的例子，1喜歡2但2沒有喜歡1，圖上有(1,2)但沒有(2,1)，有向圖上如果雙向關係都存在則需要用兩個邊表示，例如上圖中的(2,3)與(3,2)。無向圖的邊是沒有指明方向的，其實無向圖就是雙向圖，每一個邊都是雙向關係，無向圖表達的是一種對稱的關係，也就是對任意a與b，(a,b)存在若且惟若(b,a)存在，或者說(a,b)與(b,a)是一樣的。
* 無加權圖與加權圖(unweighted and weighted graph)：圖上的點與邊都可以有權重，例如以點表示城市，邊代表道路的交通網圖，點的權重可能表示城市人口數，邊的權重可能表示路的長度。如果沒有說明，通常以$G=(V,E,w)$表示一個邊上有權重的圖，其中w是一個邊的函數，$w(a,b)$代表邊$(a,b)$的權重。無加權圖就可以看成每個點(邊)的權重都是1的加權圖。
* 路徑與環路：從一個點 $v_0$ 出發，經過某個邊$(v_0,v_1)$到達$v_1$，再經由某個邊$(v_1,v_2)$到達$v_2$，…, 最後到達$v_k$，這樣的一個序列稱為路徑(path)，若任兩點之間最多只有一條邊(稱為simple graph)，則我們可以簡化用點的序列$(v_0,v_1,v_2,…,v_k)$來代表這條路徑。一個路徑上如果沒有經過重複的點，就稱為簡單路徑(simple path)，若沒有特殊指明，通常路徑指的是簡單路徑。頭尾是相同的點的路徑則稱為環路(cycle/circuit)，也就是從某點出發經過若干點之後回到出發點。
在邊無加權的圖上，路徑的長度指的是經過的邊的數量，以上例來說，路徑長度是$k$；在邊有加權的狀況下，路徑的長度是經過邊的權重總和，這時候邊的權重往往也稱為長度。兩點之間可能有多條(或沒有)路徑，長度最短的路徑稱為最短路徑(shortest path)，最短路徑的長度通常稱為距離(distance)或強調稱為最短距離。在無加權圖中，每走一條邊可以比喻為走一步，最短距離就是最少走幾步可以到達目的點。
* 無向連通圖與連通區塊：一個無向圖如果任兩點之間都存在路徑相通，則稱為連通圖(connected graph)，否則稱為非連通圖(disconnected graph)。一個圖中一群彼此互相有路徑相通的點所形成的區塊稱為一個連通區塊(connected component)，但不被包含在其他連通區塊的才能稱為連通區塊。下圖是一個例子，{0,1,2,3}形成一個連通區塊，{4,5,6,7}是另外一個連通區塊。但{0,1,2}不算。從圖形上看，連在一起的就是屬於一個連通區塊，以道路交通圖為例，則離島之間是不連通的，每個離島可能屬於單獨的連通區塊。
* 一個連通而無環路的圖稱為樹(或樹狀圖)，如果是簡單圖，則樹的邊數必然等於點數減一。樹中如有一點被指定為根(root)，則稱為有根樹，否則是無根樹。有根樹通常把根畫在最上方像一個家族圖，如下圖是一個有根樹，其中0是根。除了根以外，每個點的上方(通往根的路徑上的第一個點)一定恰有一點，這個點稱為他的parent，例如4與3的parent是1；5,6與7的parent是2；而1與2的parent是0(根)。若$a$是$b$的parent，則稱$b$是$a$的孩子(child)。只要指出每一個點的parent就可以惟一決定一棵樹。樹的相關問題很多，我們留在下一章介紹，但是這一章裡面也會碰到一些與樹有關的術語。
* 有向圖的強連通：在無向圖上，一個圖只要連在一起就是連通圖，任兩點之間皆有路徑相連。但在有向圖上比較複雜，因為有向圖的路徑必須依照箭頭方向前進，所以連在一塊的不一定有路徑可以到達。若對任意兩點$a$與$b$，圖上皆存在由$a$到$b$的路徑以及由$b$到$a$的路徑，則稱為強連通圖(strongly connected graph)。
* 點的分支度(degree)與鄰居：兩個點如有邊相鄰則稱為鄰居，無向圖上是互為鄰居，有向圖則要區分in-neighbor與out-neighbor。鄰居的個數則為分支度(degree)，也就是該點所接邊的個數(假設是簡單圖)。同樣的，在有向圖上degree要分為in-degree與out-degree。
一個圖$G=(V,E)$，習慣上用$n$代表點數，$m$代表邊數。圖的問題的輸入通常包含點與邊，所以輸入資料的大小是$O(n+m)$，在表達演算法複雜度時，往往也需要表示成$n$與$m$的函數。我們知道邊數與點數是有一定的關係，在大部分狀況下(simple graph)，$m$不會超過$O(n^2)$，所以有的時候也只表示成$n$的函數，但是表示成$n$與$m$的函數會更精準，特別是很多問題所要處理的圖的邊數$m$只在$O(n)$的大小，這時把$m$列為複雜度參數就很重要了。
在分析圖的演算法時，常常涉及點與邊的關係，以下是一個簡單而常用的性質，也被稱為「握手定理」：
> 在無向圖中，各點的degree總和等於$2m$；在有向圖中，各點的in-degree總和與out-degree總和，都等於$m$。
握手定理名稱的由來是這定理的無向圖版本可以描述成：在一場聚會中，每個人握手次數的總和是兩倍的握手發生次數。這定理很容易理解，因為一根邊會貢獻兩個degree，只是不一定貢獻給哪個點。而在有向圖時，一根邊一定貢獻出一個in-degree與一個out-degree。
## 資料結構與基本演算法
在這一節中我們介紹處理圖的基本資料結構與幾個基本演算法。
### 資料結構
要進行圖的資料計算，第一件事就是必須要能夠存取圖，也就是要有儲存圖的資料結構。常用的資料結構有兩種：鄰接矩陣(adjacency matrix)與鄰接串列(adjacency list)。
圖在處理過程中，最基本上的操作就是找出某個點的鄰居，使用不同的資料結構，程式就會不同的寫法。
一個圖$G=(V,E)$，習慣上用$n$代表點數，$m$代表邊數，而將點以0 ~ $n-1$編號(或是1 ~ $n$)。所謂鄰接矩陣就是一個$n\times n$的二維陣列$A[][]$，其中$A[i][j]=1$代表有一個邊$(i,j)$，若$A[i][j]=0$則表示該邊不存在。在無向圖時，此矩陣必然是對稱矩陣，也就是對所有$i$與$j$，$A[i][j]=A[j][i]$；如果是有向圖，則不一定。至於對角線上$A[i][i]$則要看應用而定，在某些問題中，$A[i][i]$代表自迴圈(self loop)的邊，也就是由$i$到$i$的邊。下圖是一個例子。
對於加權圖$G=(V,E,w)$，我們可以將$A[i][j]$存$(i,j)$邊上的權重$w(i,j)$，若邊的權重是正的，可以用0來表示邊不存在，但更常見的時候是以無窮大來表示，至於要以多大數字表示無窮大則看題目需要。
用鄰接矩陣來存圖最大的好處是簡單方便，要找出點v的out-neighbor就直接掃描列，找出那些$A[v][i]=1$的$i$；若是要找in-neighbor就掃描行，找出那些$A[i][v] =1$的$i$。
鄰接矩陣最大的麻煩是空間與時間效率。一個$n$個點的簡單圖，鄰接矩陣所需要的空間是$O(n^2)$。另一方面，邊的個數$m$上限是$O(n^2)$，如果邊數達到$O(n^2)$我們通常稱為dense graph，邊數是$O(n)$的稱為sparse graph。如果要處理的是dense graph，那使用鄰接矩陣也是剛好。但是許多應用要處理的是sparse graph，也就是說，如果用鄰接矩陣來存，矩陣裡面大部分都是0，這顯然很沒有效率，因為資訊的量只有$O(n+m)=O(n)$。這就是另外一種資料結構「鄰接串列」的優勢所在。
鄰接串列的概念很簡單：每個點把它的鄰居當成一個串列來存起來。這樣在有向圖中，鄰居的總數就是邊數$m$，在無向圖中，鄰居的總數就是$2m$(因為每個邊的兩端互為鄰居)。實作上呢？很多資料結構的書都是教用指標來做鏈結串列，將鄰居放進此串列中，但是對Python 而言，我們不需要這麼麻煩，Python 的內建資料結構list就是可變大小的，所以每一個點用一個list來存它的鄰居就行了。
以下是範例的程式，讀入點數$n$與邊數$m$，然後讀取$m$個邊。這個範例程式只是要示範如何儲存圖，我們只把每個點的鄰居輸出並且計算一下degree。第一支程式是示範鄰接矩陣，這裡假設是有向圖：
```python=
# ch7 demo adjacency matrix
n,m = [int(x) for x in input().split()]
adj = [[0]*n for i in range(n)] # adj matrix
for i in range(m): # read edge (u,v)
u,v = [int(x) for x in input().split()]
adj[u][v] = 1
print("adjacency matrix:")
for row in adj:
print(*row)
#
# compute in-degree and out-degree
outdeg = [sum(row) for row in adj]
print("out-deg:")
print(*outdeg)
indeg = [0]*n
for i in range(n):
for j in range(n):
indeg[j] += adj[i][j]
print("in-deg:")
print(*indeg)
```
以資料夾中的digraph.in輸入時，輸出為：
```
adjacency matrix:
0 0 1 0 0 0 1 0 1 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 1 0 0 1
0 1 1 0 0 0 1 0 0 1
1 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
out-deg:
3 1 1 2 2 4 2 1 3 1
in-deg:
1 2 3 3 1 2 4 0 2 2
```
第二支是示範鄰接串列。重點對每一個點$v$，用一個list $adj[v]$存它所有的out-neighbor編號。
```python=
# ch7 demo adjacency list
n,m = [int(x) for x in input().split()]
adj = [[] for i in range(n)] # adj list
# adj[i] is a list of out-neighbors of i
for i in range(m): # read edge (u,v)
u,v = [int(x) for x in input().split()]
adj[u].append(v)
print("adjacency list:")
for i,row in enumerate(adj):
print(i,':',*row)
#
# compute in-degree and out-degree
outdeg = [len(row) for row in adj]
print("out-deg:")
print(*outdeg)
indeg = [0]*n
for i in range(n):
for v in adj[i]:
indeg[v] += 1
print("in-deg:")
print(*indeg)
```
以資料夾中的digraph.in輸入時，輸出為：
```
adjacency list:
0 : 6 8 2
1 : 5
2 : 3
3 : 4 5
4 : 6 9
5 : 6 1 9 2
6 : 0 8
7 : 3
8 : 1 2 3
9 : 6
out-deg:
3 1 1 2 2 4 2 1 3 1
in-deg:
1 2 3 3 1 2 4 0 2 2
```
### BFS演算法
圖的搜尋是圖的基本問題：「輸入一圖$G=(V,E)$以及其中一點$s$，要從$s$作為起點探索此圖，或者簡單的說，請問從$s$出發的話，可以到達哪些點。」基本有兩種常用的演算法，這兩種方法各有它們的特殊應用，在這一小節先介紹廣度優先搜尋(Breadth-First Search, BFS)。
在看BFS的演算法前，我們先以一個例子來說明算法要做的事情，以下是一個無向圖。
假設我們要以$s=2$為起點以BFS探索這個圖。我們會先找出距離$s$一步的點，然後找兩步的點，…，一直到所有$s$能走到的點都找完為止。過程中我們將$s$比喻成一個家族的第0代祖先，與$s$距離1步的點就是第1代，距離2步的就是第2代，…。最後建出一個像類似家族世系圖的結果，如下圖。
這個圖是一個樹狀圖，而且由BFS走出來的，我們稱它是一個BFS tree。BFS tree是一層一層的，每往下一層與起點$s$的距離就增加1步。每一個點會與上一層的某個點相連，這個點稱為它的parent，在BFS tree中，每個點的parent就是第一個發現它的點。
在探訪第$i$代的某個點$u$時，例如$u=4$，我們檢查$u$的所有鄰居{3,5,6,7}，這些鄰居有可能是第$i-1$代(如3)、第$i$代(如5)、或是第$i+1$代(6與7)，所以我們必須加以區分，區分的方法是記錄每個點目前是否被發現過，當我們探訪完所有第$i-1$代的點時，所有第$i$代與更早的點都一定已經被發現過，所以$u$的鄰居中未曾被發現的就是所要的第$i+1$代的點。有了以上的認知，我們可以來說明BFS的演算法了。
因為一個點可能會發現多個點，但我們必須依照發現的順序逐一探訪，所以我們準備一個FIFO(先進先出)的Queue(佇列)$Q$，初始的時候只有起點$s$放入$Q$中，程式執行過程中，被發現的點就會被放入$Q$中，程式會執行到$Q$中沒有點為止。每一回合從$Q$中取出一點$u$來加以探訪，探訪就是檢查它的所有鄰居，其中尚未被發現的，就設定相關資料並放入Q中；如果是已經被發現的，就不予理會。
BFS演算法運作的過程中，我們可以把點分成三類，用顏色予以區分：
* 尚未被發現的點(白色)
* 已經被發現，但它的鄰居尚未檢查的點(灰色)
* 已經被發現且鄰居已經被檢查完畢(黑色)
演算法運作的過程中，點會由白變灰，最後都變成黑色就結束了。以下是Python的BFS的範例程式。對每一個點$v$，我們建立下列資料並保持迴圈不變性：
* $visit$是一個list紀錄所有已經被發現的點(灰色與黑色)。
* $que$中是灰色的點。
* $dist[v]$是起點$s$到已發現點$v$的最短距離。
* $parent[v]$是紀錄$v$的parent，也就是發現它的點。
```python=
# vertex is o..n-1
# adj[i] =list of neighbor of i
visit = [False]*n # set of all visited vertex
parent = [-1]*n # assume vertex label >=0
dist = [0]*n # distance to s
def bfs(s):
que = [s]; head = 0 # a FIFO queue
visit[s] = True
while head < len(que):
v = que[head]; head += 1 # pop
for u in adj[v]:
if visit[u]: continue
que.append(u)
visit[u] = True
parent[u] = v
dist[u] = dist[v] + 1
#end while
# que: list of visited vertex
# visit: if visited
# parent: BFS tree
# dist: distance of each vertex from s
```
在解題的場合，筆者的習慣是以list來做queue，用一個變數$head$紀錄目前的頭端而並不真正的做移除頭端的動作。當然也可以用Python的deque來做，但是不要用list來做而用list.pop(0)去移除頭端，那樣是耗費時間的做法。
BFS通常有下列用途：
* 計算某個點出發可以到達的點。
* 在無加權圖中，計算一個點到其他點的距離，或是找兩點的最短路徑。
* 計算無向圖的connected component。從一個點出發可以拜訪到該點所在的連通區塊的所有點，若對每一個點當起點進行BFS，則可以找到所有連通區塊，但要注意應略過前面的點已經被拜訪過的點。
以下先看一個簡單例題，其他應用放在後面的例題與習題中。
---
##### P-7-1. 探索距離
輸入一個有向圖$G$與一個起點$s$，請計算由$s$出發可以到達的點數(不包含$s$)，並且計算這些可以到達的點與$s$的距離和，假設每個邊的長度均為1。兩點之間可能有多個邊，邊的起點與終點未必不同。
Time limit: 1秒
輸入格式：第一行是兩個正整數$n$與$m$，代表圖的點數與邊數，圖的點是以0 ~ $n-1$編號，第二行是$s$的編號，接下來有$m$行，每一行兩個整數$a$與$b$代表一個邊$(a,b)$。n不超過100，$m$不超過4000。
輸出：第一行輸出可以到達的點數，第二行輸出與s的距離總和。
範例一輸入：
7 6
1
5 1
1 3
1 4
2 3
4 6
6 0
範例一輸出：
4
7
範例二輸入：
3 2
0
1 2
2 1
範例二輸出：
0
0
---
這一題就是要在有向圖中從一點$s$做BFS就可以計算可以到達的點，以及$s$到這些點的距離。因為點數不多，我們同時示範鄰接矩陣與鄰接串列的做法，以下先看矩陣。這個程式就直接照BFS的演算法寫，沒有太多需要進一步說明的，因為適用鄰接矩陣儲存的，所以在找鄰居時，必須跑一個迴圈檢查所有的點。
```python=
# P-7-1, using matrix
n,m = [int(x) for x in input().split()]
s = int(input())
# input adj matrix
adj = [[0]*n for i in range(n)] # adj matrix
for i in range(m): # read edge (u,v)
u,v = [int(x) for x in input().split()]
adj[u][v] = 1
visit = [False]*n # set of all visited vertex
parent = [-1]*n # assume vertex label >=0
dist = [0]*n # distance to s
def bfs(s):
que = [s]; head = 0 # a FIFO queue
visit[s] = True
while head < len(que):
v = que[head]; head += 1 # pop
for u in range(n):
if not adj[v][u] or visit[u]:
continue
que.append(u)
visit[u] = True
parent[u] = v
dist[u] = dist[v] + 1
return len(que) # number of visited vertex
#
cnt = bfs(s)-1 # excluding s
print(cnt)
print(sum(dist))
```
再來看鄰接串列的寫法，惟一的差別只在圖的儲存方式，檢查$v$所有鄰居時，可以簡單的寫
for u in adj[v]:
請注意這一題的輸入雖然兩點之間可能有多個邊而且可能有自己走到自己的邊(自迴圈)，但對BFS完全沒有影響，所以程式中沒有去判別這些狀況。
```python=
# P-7-1, using matrix
n,m = [int(x) for x in input().split()]
s = int(input())
# input adj list
adj = [[] for i in range(n)] # adj list
# adj[i] is a list of out-neighbors of i
for i in range(m): # read edge (u,v)
u,v = [int(x) for x in input().split()]
adj[u].append(v)
visit = [False]*n # set of all visited vertex
parent = [-1]*n # assume vertex label >=0
dist = [0]*n # distance to s
def bfs(s):
que = [s]; head = 0 # a FIFO queue
visit[s] = True
while head < len(que):
v = que[head]; head += 1 # pop
for u in adj[v]:
if visit[u]: continue
que.append(u)
visit[u] = True
parent[u] = v
dist[u] = dist[v] + 1
return len(que) # number of visited vertex
#
cnt = bfs(s)-1 # excluding s
print(cnt)
print(sum(dist))
```
BFS容易寫錯的地方是visit沒有設定好或是忘了檢查，那有可能會造成一個點被重複的放進queue中，而在執行時發生錯誤(例如無窮迴圈)或者執行效率不佳。
### Depth First Search
除了BFS之外，另外一個常用的圖的搜尋演算法是深度優先搜尋(DFS, Depth-First Search)。BFS像水面掀起的水波，從中心點往外一圈一圈的擴散，DFS通常是以遞迴的概念來說明：「先從一個鄰居出發探索所有可以探索的點，如果還有剩下，則在從下一個鄰居出發，重複此步驟，直到所有鄰居嘗試完畢。」遞迴的演算法通常比較簡潔但不易了解，DFS也不例外。
**請注意**，Python的遞迴深度預設是1000，即使可以調整但遞迴深度過深時，仍可能造成記憶體不足的執行錯誤。所以用Python寫遞迴時必須注意遞迴深度，在圖形走訪時，建議寫BFS比較保險。
我們實際看一下DFS在下面這個無向圖上的運作狀況，會比較了解此演算法。假設一樣從2出發。
演算法運作過程如下(假設鄰居的檢查順序依照編號)：
* DFS(2)：2有兩個鄰居{0,3}，而且都未曾被拜訪，先去0，留著3未檢查；
* DFS(0)：0有兩個鄰居{1,2}，先去1；
* DFS(1)：1只有個鄰居{0}，但是0已經被拜訪過，所以return回到0；本來是從0探訪它的鄰居，本來先去1，現在從1回來了，所以檢查下一個鄰居2，但2是已經被拜訪過的，所以也結束，return回到2；本來是從2探訪它的鄰居，本來先去0，現在從0回來了，所以檢查下一個鄰居3，3尚未被拜訪，所以去3；
* DFS(3)：3有3個鄰居{2,4,5}，先檢查2，被拜訪過；再檢查4，沒拜訪過，所以去4(留著5還沒檢查)；
* DFS(4)：4有4個鄰居{3,5,6,7}，先檢查3，被拜訪過；再檢查5，沒拜訪過，所以去5(留著6,7還沒檢查)；
* DFS(5)：5有4個鄰居{3,4,6,7}，先檢查3與4，都被拜訪過；再檢查6，沒拜訪過，所以去6(留著7還沒檢查)；
* DFS(6)：沒被拜訪過的鄰居只有7；
* DFS(7)：沒有沒被拜訪過的鄰居，所以return回到6號點；6沒有剩下沒拜訪過的鄰居，所以return回到5號點；5本來留著7尚未檢查先去6，所以6回來時檢查7，但此時7已經被拜訪過了！！所以也沒有剩下沒拜訪過的鄰居，也return回到4號點；4號點先去5，留著6與7尚未檢查，所以從5號點回來會去檢查6與7，但此時兩點都已經被拜訪過了，所以就return回到3號點；類似地，3號回到2號，然後就結束了整個探訪的過程。
如果我們把每個點被誰呼叫當作它的parent，然後把每點與它的parent連起來，一樣可以得到一棵樹，這棵樹是由DFS走出來的，所以就稱為DFS tree(如下圖)，圖中紅線是走訪順序，它可以讓我們了解DFS運作的過程。
```python=
# assume vertex 0 ~ n-1
def dfs(s, adj, parent, visit):
visit[s] = True
for v in adj[s]:
if not visit[v]:
parent[v] = s
dfs(v, adj, parent, visit)
# end of dfs
# prepare adj
visit = [False]*n
parent = [-1]*n
# start node
dfs(start, adj, parent, visit)
```
以下是一個簡單的例題來示範DFS的寫法。
---
##### P-7-2. 開車蒐集寶物
參加一個蒐集寶物的遊戲，你拿到一個地圖，地圖上有$n$個藏寶點，每個藏寶點有若干價值的寶物，由於你的團隊是最頂尖的，只要能到達藏寶點一定可以取得該藏寶點的寶藏。從地圖上看得到一共有$m$條道路，每條道路連接兩個藏寶點，而且每條道路都是雙向可以通行的。在遊戲的一開始，你可以要求直升機將你的團隊運送到某個藏寶點，而且你可以獲得一部車與充足的油料，但是直升機的載送只有一次，所以你必須決定要從哪裡開始才可以獲得最多的寶藏總價值。
Time limit: 1秒
輸入格式：第一行是兩個正整數$n$與$m$，代表藏寶地點數與道路數，地點是以 0 ~ $n-1$編號，第二行$n$個非負整數，依序是每一個地點的寶藏價值，每個地點的寶藏價值不超過100。接下來有$m$行，每一行兩個整數$a$與$b$代表一個道路連接的兩個地點編號。$n$不超過1000，$m$不超過1000。兩點之間可能有多條道路，有些道路的兩端點可能是同一地點。
輸出：最大可以獲得的寶藏總價值。
範例一輸入：
7 6
5 2 4 2 1 1 8
5 1
1 3
1 4
2 0
2 0
3 3
範例一輸出：
9
範例二輸入：
3 2
2 1 5
1 0
0 1
範例二輸出：
5
範例一說明：降落在0可以獲得0與2的寶藏，價值為5+4=9。
範例二說明：降落在2可獲得價值5。
註：本題在C++版本時的點數較多，某些測資在某些環境用Python跑DFS會導致執行錯誤，這裡的測資已經改小。
---
輸入的是一個無向圖，每個點有個權重，要找出最大權重的連通區塊，所以用DFS或BFS都可以，這一題我們用來示範DFS，所以下面是DFS的寫法。這一題的點數很大，所以必須使用連接串列的方式來存圖，主程式主要在讀取圖的資料，因為是無向圖，所以讀到一個邊$(u,v)$時，必須兩點互相加為鄰居。DFS函式的部分可以看得出遞迴的寫法真的要比BFS簡潔，這裡我們要找的是連通區塊的權重總和，所以，對於每一次DFS，我們讓他回傳可以到達點的權重和就可以了。
主程式中跑一個歷遍所有點的迴圈，對於沒有拜訪過的點就進行一次DFS，因為有判斷visit，所以同一個連通區塊不會被走訪兩次，執行時間就是線性了。
```python=
# P-7-2, max weight component, adjacency list
n,m = [int(x) for x in input().split()]
w = [int(x) for x in input().split()]
# input adj list
adj = [[] for i in range(n)] # adj list
for i in range(m): # read edge (u,v)
u,v = [int(x) for x in input().split()]
adj[u].append(v)
adj[v].append(u) # undirected
# return total weight
def dfs(s, visit):
visit[s] = True
total = w[s]
for v in adj[s]:
if not visit[v]:
total += dfs(v, visit)
return total
#
visit = [False]*n # set of all visited vertex
imax = 0
for v in range(n): # check each unvisited
if not visit[v]:
imax = max(imax,dfs(v,visit))
print(imax)
```
這一題當然也可以用BFS來作，有興趣的人可以自己練習試試，範例程式中有一支BSF的作法，因為只是標準的BFS，這裡就不多說明了。
### DAG and Topological sort
DAG(directed acyclic graph)是指一種沒有環路的有向圖，DAG是應用很多的一個圖的類別，在動態規劃中，也用DAG來描述狀態轉移，其實不只是DP的狀態，在很多前置關係的問題上都有類似的情形，例如一件計畫分成很多工作，某些工作必須在某些工作完成之後才能進行。我們可以將每個工作看成一個點，若$u$是$v$的前置工作，就在圖上加入一個$(u,v)$有向邊，這樣建立出來的圖必須是個DAG，否則就會產生雞生蛋蛋生雞的矛盾而有某些工作無法完成。
對於一個DAG，我們最常須要找的就是一個拓樸順序(topological sort)，所謂拓樸順序是將所有的點排成一個序列，使得所有的有向邊都是從前往後，而沒有從後往前的邊。拓樸順序顯然不惟一，但通常只要找出其中一個就可以了。
以下圖為例來找一個拓樸順序，因為前置關係是有遞移性的，前置的前置也必須是前置，我們可以看得出來，2一定要放在第一個，相同的5一定是最後一個。因為3要放在右邊所有點前，所以最前面的四個點一定是(2,0,1,3)。置於右邊的四個點，因為4必須在6與7之前，所以3後面只能接4，但6與7不一定誰先誰後，所以我們知道(2,0,1,3,4,6,7,5)是一個拓樸順序，而(2,0,1,3,4,7,6,5)也是一個。
我們的重點要放在如何計算一個拓樸順序，常用的方法有兩個。其中一個是利用DFS，假如在DFS時，對每一個點在完成探訪時(return之前)，將該點的編號輸出，那麼將此輸出順序反轉就可以得到一個拓樸順序。證明不是很難，簡單的說，在執行DFS($v$)時，所有$v$可以到達的點都是應該排在$v$之後的，而DFS會把這些點都拜訪完畢後才結束$v$的探訪。
DFS的複雜度是線性時間，所以用DFS來做拓樸順序應該很完美，但是它是遞迴的，很多時候我們不希望使用遞迴，例如DP的過程，因為不想(或是環境不允許)使用遞迴，所以才要找拓樸順序，所以我們需要一個非遞迴的演算法。以下我們介紹一個找出拓樸順序的演算法。
這個方法很簡單，它的原理就是：只要是in-degree=0的點，也就是沒有箭頭指向它的點，都是可以出列的點。
以下是一個使用adjacency list的範例程式，以上面的圖為輸入範例。
一開始先把所有的邊看一遍，用一個list $adj$存每個點的out-neighbors，用一個list $deg$記錄每個點的in-degree。
$que$是一個list逐步將in-degree為0的點納入，最後它就是所要的拓普順序。while迴圈從$que$的頭端每次取出一點$v$，模擬$v$點移除的狀況，也就是將$v$的所有out-neighbor的in-degree均減去一，若減一後降為0，則將其放入佇列中。
如果這是一個DAG，while迴圈跑完時，所有的點一定都處理過，否則便是有迴圈。程式的時間複雜度是$O(n+m)$，因為每個點最多進入佇列一次，離開佇列時所花的時間是他的out-degree，而所有點的out-degree總和就是邊數。
```python=
# assume vertex = 0..n-1
# edge is the list of directed edge u->v
n=8
edge=[[2,0],[2,3],[0,1],[1,3],[3,4],
[3,5],[4,6],[4,7],[6,5],[7,5]]
adj = [[] for i in range(n)] # out neighbor
deg = [0]*n # in-degree
for u,v in edge:
deg[v] += 1
adj[u].append(v)
# initialize a queue with deg=0
que = [v for v in range(n) if deg[v]==0]
head = 0
while head < len(que):
v = que[head]; head += 1
for u in adj[v]:
deg[u] -= 1
if deg[u]==0: que.append(u)
# end while
if len(que)<n:
print("Existing cycle")
else:
print("A topological sort:", que)
```
**End of Chapter 7 (I)**
續接 [AP325-Python 第7章 基本圖論演算法 (II)](/sGnZLC8gS9a2Ii1RAAqGag)
Sign in with Wallet
Connect another wallet