**Chapter 7 (III)**

## 補充教材(\*)

在這一節中，我們挑選一些還算常用也不太困難的圖論演算法當作補充教材，包括：Dijkstra演算法、併查集(Union and Find)，以及最小生成樹(Minimum spanning tree)。這些內容研判超過APCS考試範圍，所以讀者可自行選擇是否略過。

### Dijkstra演算法

我們前面介紹了無加權圖上面以BFS計算最短距離的方法，對於DAG我們也可以沿著拓樸順序來計算距離，但是應用問題中，更常見的是邊上有加權也可能有環路的圖。Dijkstra演算法是用在一個加權圖上計算一點到所有點的最短路徑的演算法，圖可以是有向的或無向的，但是**邊上的權重必須是非負的**。

假設輸入的圖是$G=(V,E,w)$與一個起點$s$，我們要計算$s$到$V$中每一點的一條最短路徑。演算法運作過程中，我們以$d[v]$紀錄目前已知$s$到$v$的最短距離，集合$Q$表示最短距離尚未確定的點，演算法如下：

# Dijkstra演算法，輸入：G=(V,E,w)與一個起點s
初始化：d[s]=0; 對其他v點，d[v]=oo; Q=V;
while 尚有未確定距離的點(Q is not empty) do
    在Q中找出d[]最小的點v;
    將v移出Q中; # d[v]確定為s到v的最短距離
    for each u in adj[v] and in Q do: #與v相鄰尚未確定距離者
        if d[v]+w(v,u) < d[u] then # 從v過來路更近
            d[u] = d[v]+w(v,u);
            parent[u] = v; # 已知到達v之最短路徑的前一點
        end if
    end for
end while

演算法其實不困難，每次在尚未確定距離的點中，找出$d[]$最小的$v$，因為邊長都不是負的，所以$d[v]$的值不可能更短了，我們就將它確定，然後，用$d[v]+w(v,u)$去嘗試更新與$v$相鄰的$u$點的距離。
如果圖中有些點是從$s$走不到的，最後找出來的距離就是初設的無窮大。此外，最後$d[v]$是最短距離，那麼要如何找路徑呢？我們在每次更新距離時，存了$parent[v]$，它記錄著從$s$到$v$的最短路徑的最後一步，所以當計算完成時，由後往前一步一步回推就可以得到路徑經過的點的順序。名字取為parent的原因是：如果將每個點與它的parent連起來，我們會得到一棵以$s$為根的樹狀圖，這個樹稱為shortest-path tree，在此樹上，$s$到任一點的路徑都是在原圖上的最短路徑。

我們把重點擺在如何實作，以下一個例題來當作說明，這個例題是無向圖，對有向圖的做法類似。

---

##### P-7-9. 最短路徑 (\*)
輸入一個無向圖$G=(V,E,w)$，其中點以0 ~ $n-1$編號，而邊的權重是非負整數。計算0號點到其他點的最短路徑長度。兩點之間可能有多個邊。

Time limit: 1秒

輸入格式：第一行是兩個正整數$n$與$m$，代表點數與邊數，接下來有$m$行，每行三個整數$u, v, w$代表一條無向邊$(u,v)$的長度是$w$。$n$不超過1e4，$m$不超過1e5, $w$是不超過1e4的非負整數。
輸出：第一行輸出0到各點之最短路徑長度中的最大值，也就是在可以到達的點中，最短距離最大的是多少，第二行輸出有多少點無法從抵達。

範例一輸入：
7 6
0 2 3
0 1 1
2 3 4
1 4 0
3 4 2
5 4 3

範例一輸出：
4
1

範例二輸入：
3 3
2 1 5
1 0 0
0 1 1

範例二輸出：
5
0

(範例測資中前兩筆的n不超過500。)

---

要做出$O(n^2)$複雜度的Dijkstra演算法一點都不困難，例如在dense graph上以鄰接矩陣儲存時，我們直接依照演算法的步驟來寫，就可以得到以下的範例程式了。

# p-7-9 O(n^2) Dijkstra algorithm, using matrix
n,m = [int(x) for x in input().split()]
oo = 10**9
adj = [[oo]*n for i in range(n)] # adj matrix
for i in range(m): # read edge (u,v)
    u,v,w = [int(x) for x in input().split()]
    adj[u][v] = adj[v][u] = min(adj[u][v],w)
    # maybe multiple edges
#
d = [oo]*n
parent = [-1]*n
source = 0
done = [False]*n # whether the distance is converged
d[source] = 0
while True: # converge one vertex each iteration
    # find min d[] of not-done vertex
    mind = oo
    for i in range(n):
        if not done[i] and d[i]<mind:
            v = i
            mind = d[i]
    #
    if mind==oo: break # no more reachable vertex
    done[v] = True
    # update neighbor
    for i in range(n): 
        if d[v]+adj[v][i] < d[i]: # shorter path to i
            d[i] = d[v]+adj[v][i]
            parent[i]=v
    #
# end while
maxd = max(d[v] for v in range(n) if d[v]<oo)
cnt = sum(1 for v in range(n) if d[v]==oo)
print(maxd,cnt,sep='\n')

要把時間複雜度降下來，除了儲存圖要改用鄰接串列之外，最重要的是每一回合如何很快地找到$d[]$最小的點，這就需要借助資料結構的幫忙。因為每次找到一點之後，我們會更新其他點的$d[]$，因此$d[]$是會動態變化的，也就是說無法靠著一開始用排序來處理。因為每次都要找最小值，最直接的想法是啟用一個優先佇列(PQ, priority queue)，但是這裡的困難還不只在於此，最大的問題在於每一回合可能有某些$d[]$值會更動(降低)。基本上PQ是以heap寫的，如果是自己寫的heap，我們可以修改這個資料結構，讓它可以處理decreasing key的狀況，但是一般為了節省時間，我們會採用庫存函數中提供的PQ，可惜Python的PQ (heapq)並不提供此功能，C\++中的庫存函數也不提供此功能，多數競賽選手採取的變通方法是以下”偷懶”的策略，這種策略其實並不罕見：

>我們將$(d[u],u)$的結構放在PQ中，當我們要將$d[u]$修改為$x$的時候，我們並不從PQ中刪除或更新該筆資料，而是直接將$(x,u)$放入PQ中。這樣一來，對於某些點，PQ中可能會有多筆資料，但是無論如何，最小的會先出來，因為我們只做decreasing key，所以最先出來的是最新的資料。需要額外處理的事情是，當我們每一回合找最小值時，需要檢查出來的最小值點是否已經處理完畢了，如果是，則直接丟掉它。

請看以下的範例程式。第5 ~ 9行是輸入的部分，這是一個很制式的鄰接串列的寫法，對於每一個長度$w$的邊$(u,v)$，我們在$adj[u]$中放一個$(v,w)$，意思是$u$有一個鄰居邊長是$w$，由於是無向圖，也要在$adj[v]$中放$(u,w)$。

第16行我們啟用宣告一個list pq，當作min-heap使用，預計將$(d[u],u)$放入，也就是各點目前離起點$s$的距離與該點編號，距離放在前面的原因是讓最小值先出來。重點在第17行的while迴圈，每一回合會確定一點的最短距離，但是在第20行我們會檢查出來的點是否已經出來過了，如果是，則直接不予理會，否則，出來的才是我們要的。第23行的for迴圈，我們檢查該點的鄰居，如果有更好的d[]值就予以更新，如同前面說的，我們將更新後的直接壓入PQ中。

時間複雜度是多少呢？分析的方式類似BFS，因為每個點的鄰居數總和是$O(m)$，而在PQ上的操作都在$O(\log n)$時間內，所以總時間是$O(m\log n)$。
因為要使用到動態資料結構，Dijkstra演算法要在APCS中出現的機會應該是不大，或者給你演算法讓你模擬一個$O(n^2)$的方法。

# p-7-9 O(mlogn) Dijkstra algorithm, using list
import heapq
n,m = [int(x) for x in input().split()]
oo = 10**9
adj = [[] for i in range(n)] # adj list
for i in range(m): # read edge (u,v)
    u,v,w = [int(x) for x in input().split()]
    adj[u].append((v,w))
    adj[v].append((u,w)) # maybe multiple edges, fine
#
d = [oo]*n
parent = [-1]*n
source = 0
done = [False]*n # whether the distance is converged
d[source] = 0
pq = [(0,source)] # (d[v],v)
while pq: # converge one vertex each iteration
    # find min d[] of not-done vertex
    dv,v = heapq.heappop(pq)
    if done[v]: continue # useless
    done[v] = True
    # update neighbor
    for u,w in adj[v]: 
        if d[v]+w < d[u]: # shorter path to u
            d[u] = d[v]+w
            heapq.heappush(pq,(d[u],u))
            parent[u]=v
    #
# end while
maxd = max(d[v] for v in range(n) if d[v]<oo)
cnt = sum(1 for v in range(n) if d[v]==oo)
print(maxd,cnt,sep='\n')

### 併查集(Union and Find)
併查集是一種資料結構，用來處理一群不相交的集合(disjoint set)，說是一種資料結構，應該是一套資料儲存方式與操作的演算法。併查集處理的資料是不相交的集合，如同它的名字，提供的主要操作有兩個：合併兩集合以及查詢某個元素在哪個集合中。

併查集是一種樹狀圖的觀念，但是實作時完全以陣列來做就可以，也就是心中有樹但程式中無樹，寫起來非常容易，不容易寫錯，效率又高。為了方便說明，我們以人與社團來比喻元素與集合。假設元素的編號是0 ~ $n-1$，我們只要一個陣列就可以，依循樹狀圖的概念，陣列就叫做 $parent[]$。每一個人都會屬於某個社團，但不會屬於兩個社團。除了社長，每個人 $i$ 都有一個直接領導，就是他的衣食父母$parent[i]$，社長就是社團的代表人，為了方便，若 $i$ 是社長，我們令$parent[i] = -x$，其中而 $x$ 是該社團中的總人數。我們可以用下列方式來操作合併與查詢：

# 最簡單的union and Find
find(x): # 給一個人的編號，回傳x所在社團的社長編號
    while (parent[x] >= 0) do 
        x = parent[x]; # 一路往上找，直到社長
    end while
    return x;

union(x,y): # 合併x與y所在的集合
    r1 = find(x); # 找到x的社長老大
    r2 = find(y); # 找到y的社長老大
    if (r1 != r2) then # 不同社長才要合併
        parent[r2] = r1; # 一個社長拜另外一個社長當社長老大
    end if

這個演算法很簡單，查找時就一路沿$parent[]$往上走，直到走到社長(代表元素)為止。合併的時候，先檢查兩者是否是同一社團，如果是就不需要做任何事，如果不是，就把其中一個社團社長的衣食父母改為另外一個社長，這就為成了合併的動作。
這個方法雖然簡單，但是有個缺點，在一連串合併之後，可能有些人離社長關係非常遠，想像每次把一個社團都併入一個一人社團，這就如同社團每次都來一個空降的新人當新的社長，每併一次，最底下的那個人離社長的層級就增加一，這樣在查找的時候可能會很浪費時間。

改進的方法是這樣：每次合併時，把人數少的社團併入人數多的社團，也就是人多的社團社長當合併後的新社長。事實上，如果依照這個規定，社團的層級就不會超過$\log(n)$。證明：如果合併造成你離社長的層級增加1的話，表示你併入一個比原來更大的社團，也就是你的社團人數至少增加一倍，如果你離社團的層級為 $k$ 表示社團至少有 $2^k$ 個人，在總人數只有 $n$ 的前提下，層級不會超過$\log(n)$。
其實做到這個方法，我們的併查集效率就會很不錯了，但還有另外一招來提高效率，這招數稱為**路徑壓縮**，做法是這樣：每當我們要做 find() 的時候，除了找到社長之外，我們”順便”把尋找過程中碰到的那些人的parent直接改設成社團社長。這樣做似乎看不出直接的效果，事實上它是個前人種樹後人乘涼的概念，這次多花一點時間，但後續再做查找時，因為路徑都縮短了，就會比較快。這個效率的分析很不容易，基本上有人分析出，如果有一連串的合併與查詢，在以上這樣的方法之下，每一個操作所需要的均攤時間幾乎是$O(1)$。詳細的分析超過我們的範圍，這裡不多解釋了，以下是修改後的演算法，請留意社長的$parent[]$是存社團人數的負值，所以大小關係是顛倒的。

# 優化後的union and Find
find(x): # 回傳x所在集合的代表元素並且做路徑壓縮 (遞迴版)
    if (parent[x]<0) then
        return x;
    end if
    parent[x] = find(parent[x]); # 遞迴, top-down DP
    return parent[x];

union(x,y): # 合併x與y所在的集合
    r1 = find(x);
    r2 = find(y);
    sum = parent[r1] + parent[r2]; # -總人數
    if (parent[r1] < parent[r2]) then 
        parent[r2] = r1;
        parent[r1] = sum;
    else if (parent[r1] > parent[r2]) then 
        parent[r1] = r2;
        parent[r2] = sum;
    end if

前面的例題P-7-2中，我們要找權重總和最大的連通區塊，當時是用BFS或DFS來做，事實上也可以用併查集來做，每讀到一個邊就把兩端點所在的連通區塊聯集起來，以下是這樣寫的範例程式。

# P-7-2, max weight component, disjoint set, union find
n,m = [int(x) for x in input().split()]
w = [int(x) for x in input().split()]
parent = [-1]*n
# find root
def rfind(u): 
    if parent[u] < 0: return u
    parent[u] = rfind(parent[u])
    return parent[u]
#
for i in range(m): # read an edge and union
    u,v = [int(x) for x in input().split()]
    r1 = rfind(u) # root of u
    r2 = rfind(v) # root of v
    if r1 == r2: continue # same set
    if parent[r1] < parent[r2]:
        parent[r1] += parent[r2]
        parent[r2] = r1
        w[r1] += w[r2]
    else:
        parent[r2] += parent[r1]
        parent[r1] = r2
        w[r2] += w[r1]
#
ans = max(w)
print(ans)

如同前面走訪的問題，連通區塊的概念也用在二維陣列。

---

##### P-7-10. 挖坑跳 (@@)(\*) (TOI入營考)
小雨喜歡在土堆上挖坑，在坑裡注入水之後，然後玩跳水坑的遊戲。一個庭院被畫分成$m\times n$個相同大小的矩陣方格，每一個格子可能是土堆或水坑，一個水坑格子與其上下左右四個方向的水坑格子被視為連通的同一個水坑。我們需要計算有多少個水坑以及最大的水坑佔多少個格子。除了一開始的土堆與水坑，小雨每次會指定將某個格子變成水坑，如果這個方格是新挖出來的水坑，有可能把附近的水坑連在一起。小雨一共挖了 $k$ 次，請你計算出每一次挖了之後的水坑數與最大水坑面積。
土堆與水坑的資訊可以看成一個二維矩陣，以0表示土堆，而1表示水坑，位置的標示方式以左上角為$(1,1)$，右下角是$(m,n)$。以下是一個$m=3$, $n=5$的例子。一開始的水坑資料如下：

|1 |0 |0 |1 |1|
|-|-|-|-|-|
|0| 1| 1| <font color=red>0</font>| 1|
|1| 1| 0| 0| 1|

我們可以看出來有3個水坑：左上角只佔1格的水坑，左下有一個4格的水坑，以及右方有一個4格的水坑。假設現在小雨把(2,4)的土堆改成水坑(紅色位置)，左下與右方的水坑便會連接成一個面積為9的水坑。

Time limit: 1秒

輸入格式：第一行是三個整數，依序是$m$, $n$ 與$k$，接下來m行是土堆與水坑資料，每一行有$n$ 個0或1的數字，順序為由上而下，從左至右。最後一行有 $2k$個數字，依序每兩個代表一個被挖成水坑的位置$(i,j)$，如果該位置本來就是水坑，就代表沒有動作。$m$與$n$不會超過500，$k$不超過20000。
輸出：輸出兩行，第一行是每次最大水坑面積的總和，第二行是每次水坑數量的總和。計算總和時包含一開始的狀態，所以最多有$k+1$次，但如果該次所挖位置本來就是水坑，代表沒有動作，該次的結果不列入總和計算。

範例一：輸入
3 5 1
1 0 0 1 1
0 1 1 0 1
1 1 0 0 1
2 4

範例一：正確輸出
13
5

範例一說明：這是題目敘述中的例子，一開始有3個水坑，大小是(1,4,4)，操作一次後變2個水坑，大小是(1,9)。最大水坑面積總和是4+9=13，水坑數樣總和是3+2=5。

範例二：輸入
2 6 2
0 1 1 0 1 1
0 1 0 0 0 1
2 4 1 4

範例二：正確輸出
14
6

範例二說明：一開始有2個水坑，面積是(3,3)，第一次操作後有3個水坑，面積是(3,3,1)，第二次操作後變成一個面積8的水坑。

---

給一個二維的0/1矩陣，本題要找出連通的1區塊，連通的定義是上下左右四方位。初始找出各個連通區塊可以使用BFS或DFS，但是題目還有後半部：有 $k$ 次操作，每次會將某個位置設為1，如果該位置原來就1，當然沒事發生，但如果是0變成1，區塊就會變動。這時候如果做DFS或BFS可能會太花時間，因為可能有2萬次操作，每次的區塊可能達到25萬點。因為每個點只會屬於某個區塊，使用併查集來維護區塊是好的選擇。

題目本來是二維矩陣，每一個格子需要一對$(i,j)$來表示，在以下的範例程式中，我們把所有的點(i,j)以row-major的方式轉成一維陣列的位置$i\times(n+2)+j$。行數$n$加2的原因是我們把外圍多留了一圈當四個邊界，邊界在初值都設成0(土堆)。在一維轉換後，每個點的四個鄰居的位移就是$(+1, -1, +n, -n)$，其中n已經過加2的修正。
範例程式中的副程式rfind()與union()就是併查集使用的，其中union稍加修改讓它回傳合併後的大小，如果沒有合併則回傳0，這改變是為了方便計算本題所需答案。
主程式第25 ~ 28行先做輸入，並放在一維陣列中。第32 ~ 46行建立一開始的連通區塊與最大區塊面積，作法是一開始每一個1都是一個區塊，然後歷遍所有1的位置，將它與右邊與下方的1合併，如果有合併，就修改區塊數與最大區塊。
最後第50行之後是處理每一次的操作，每次挖水坑的位置都轉成一維的index，然後跟上下左右的1進行合併，如果有合併發生，就和前面一樣的方式修改區塊數與最大區塊。
程式碼雖然有點長，但是如果了解併查集，應該不難了解。

# P-7-10 components in matrix, union and find
# (r,c) transform to row-major index
# find root
def rfind(u): 
    if p[u] < 0: return u
    p[u] = rfind(p[u])
    return p[u]
# return merged size or 0 if no merge
def union(u,v):
    r1 = rfind(u) # root of u
    r2 = rfind(v) # root of v
    if r1 == r2: return 0 # same set
    # union two sets
    if p[r1] < p[r2]:
        p[r1] += p[r2]
        p[r2] = r1
        return -p[r1]
    else:
        p[r2] += p[r1]
        p[r1] = r2
        return -p[r2]
#
m,n,k = [int(x) for x in input().split()]
# boundary 0 
grid = [0]*(n+2)
for i in range(m):
    grid += [0]+[int(x) for x in input().split()]+[0]
grid += [0]*(n+2)
m += 2; n += 2
mn = m*n
p = [-1]*mn
cnt = sum(grid) # num of 1, num of component
imax = 1 if cnt else 0 # max size component
# build initial component
for i in range(mn):
    if grid[i] ==0: continue
    if grid[i+1]:
        s=union(i,i+1)
        if s > 0:
            cnt -= 1
            imax = max(imax,s)
    if grid[i+n]:
        s=union(i,i+n)
        if s > 0:
            cnt -= 1
            imax = max(imax,s)
#print(imax,cnt)
total_max = imax
total_cnt = cnt
pos = [int(x) for x in input().split()]
for idx in [pos[i]*n+pos[i+1] for i in range(0,len(pos),2)]:
    if grid[idx] == 1: continue # already 1, do nothing
    grid[idx] = 1 # set to 1
    #p[idx] = -1
    cnt += 1
    imax = max(imax, 1)
    # try to combine 4 neighbors
    for nrc in (idx+1,idx-1,idx+n,idx-n):
        if grid[nrc] == 0: continue
        s = union(idx,nrc)
        if s > 0: # merged
            imax = max(imax,s)
            cnt -= 1
    #
    total_cnt += cnt
    total_max += imax
#
print(total_max, total_cnt, sep='\n')

本題如果不轉一維陣列也可以用字典來當parent，資料夾中有一支這樣寫法的程式，有興趣的讀者請自行參考。

下一個一維陣列的類似題，我們留做習題，因為測資設定的範圍小，這一題不使用併查集也可以通過。

---

##### Q-7-11. 紅白彩帶 (APCS201902)
一條彩帶被分成 $n$個相同大小的格子，有的格子是紅色，有些則是白色。小軒拿到彩帶後開始塗顏色，每次會將一個白色格子塗滿紅色，然後小軒會算一算目前最長與最短紅色區域的長度佔了幾格，相鄰的紅色格子就屬於同一個紅色區域。小軒一共塗了 $k$ 次，請你計算出每一次紅色區域的最大與最小長度，並輸出個別的總和。
彩帶可以看成一維陣列，以0表示白色，而1表示紅色。彩帶的格子從1開始由左而右依序編號，小軒每次將某個格子塗上紅色。以下是一個例子。

初始彩帶顏色：
011001010
一開始紅色區域最大的長度是2，最小的長度是1。
第1次塗在第5格後：
011011010
第1次塗完後最長的紅色區域有2塊，長度都是2，最小的長度是1。
第2次塗在第1格後：
111011010
第2次塗完後紅色區域的最大長度是3，最小長度是1。
第3次塗在第7格後：
011011110
第3次塗完後紅色區域的最大長度是4，最小長度是3。

以這個例子而言，每一次(包含剛開始) 紅色區域的最大長度總和是2+2+3+4=11；而紅色區域的最小長度總和是1+1+1+3=6。

Time limit: 1秒

輸入格式：輸入有三行，第一行是兩個整數，依序是$n$ 與$k$，代表彩帶長度以及小軒塗色的次數，$n \le 1e5$、$k\le 2e4$。第二行有$n$ 個0或1的數字，依序代表彩帶第1 格至第 $n$ 格的顏色，0 代表白色，1代表紅色。第三行有 $k$個數字，依序代表每一次塗紅色的格子編號，若 $k = 0$，則第三行為空行。同一行數字之間都是以空白間隔。小軒每次一定都塗在白色格子，而且紅色區域的長度不會超過10100。
輸出：輸出兩行，第一行是每次紅色區域最大長度的總和，第二行是每次紅色區域最小長度的總和。

範例一：輸入
5 1
1 0 1 0 1
2

範例一：正確輸出
4
2

範例一說明：一開始最大長度是1而最小長度也是1，塗在第二格之後最大長度是3而最小長度還是1。最大長度總和為1+3=4；最小長度總和為1+1=2。

範例二：輸入
9 3
0 1 1 0 0 1 0 1 0
5 1 7

範例二：正確輸出
11
6

範例二說明：此為題目中所舉的例子。

---

### 最小生成樹
樹是沒有環路的連通圖，對於一個圖$G$，它的一個生成樹(spanning tree)是指挑選$G$的一些邊，將所有點連成一個連通區塊，而挑選的邊形成的是一個樹。因為$n$個點至少要$n-1$個邊才能形成一個連通區塊，而超過$n-1$個邊必然會造成有環路，所以spanning tree一定恰好是$n-1$個邊。$G$的最小生成樹(minimum spanning tree)是指邊的權重總和最小的生成樹。

假設我們有$n$個城市，要建設一個交通網路將$n$個城市連起來，如果圖$G$的每一個邊代表一條可以建設的道路，而邊上有一個非負的權重代表該道路的建設成本，那麼最小生成樹就是最低的建設總成本。下圖是一個例子，其中實線代表最小生成樹的邊，虛線代表沒有挑選的邊，圖中有8個點，一定剛好有7個邊。

如果是無加權圖，也就是圖的每個邊的權重皆相同，那麼最小生成樹的成本一定剛好是$n-1$，BFS與DFS都可以建構出一個最小生成樹。在一般狀況下，我們要處理的是加權圖。計算最小生成樹有多個演算法，目前比較常用的有兩個：Prim演算法與Kruskal演算法。

先介紹Prim的演算法，這個演算法與Dijkstra演算法幾乎一模一樣，我們從任選一個點$s$開始，逐步建構我們要的樹$T$，每一回合會從尚未連進$T$的點中挑選一個點$v$以及一個已經在$T$中的點$u$，將$v$與邊$(u,v)$加入$T$中，而挑選的點與邊是滿足上面做法中成本最小的邊，也就是一點在$T$中一點不在$T$中的所有邊中，成本最小的邊。重複這個步驟直到全部的點都加入$T$中為止。以下演算法中我們計算成本，如果要建構出樹，就把每個點$v$與$parent[v]$這個邊輸出即可。

# Prim演算法，輸入：G=(V,E,w)與一個任選一個起點s
初始化：T為空，d[s]=0; 對其他v點，d[v]=oo; Q=V; cost=0;
# Q是尚未加入T的點, d[v]表示將v加入T的最小成本
while (Q is not empty) do
    在Q中找出d[]最小的點v;
    cost += d[v];  
    將v移出Q中; # v加入T中
    for each u in adj[v] and in Q do: #與v相鄰尚未進入T者
        if w(v,u) < d[u] then # 從v連過來的成本更小
            d[u] = w(v,u);
            parent[u] = v; # u加入T的最小成本是w(v,u)
        end if
    end for
end while

Prim演算法與最短路徑的Dijkstra演算法只有比大小的key值不同，Dijkstra是起點走過來的總距離，而Prim則只看最後與parent相連的邊長。實作時需要與Dijkstra一樣使用PQ的技巧，因為太相像了，我們就不多做說明，在後面的例題中，我們會給一個範例程式。
另外一個常用的是Kruskal演算法。這個做法也很簡單直覺，需要搭配的資料結構是併查集。演算法兩三句話就可以講完：
> 將邊從小到大逐一考慮，如果一個邊加入不會形成環路就把它挑進來；否則將它捨棄。重複挑選邊直到沒有邊或者已經挑到$n-1$個邊為止。

如果輸入的是連通圖，最小生成樹一定存在，否則全部的邊都挑完了仍無法形成生成樹。以下是演算法。

# Kruskal演算法，輸入：G=(V,E,w)
初始化：設T為空; 初始化一個併查集，每個點自成一個連通區塊;
將所有邊依照權重由小到大排序;
for each edge (u,v) do # 依權重由小到大的順序
    if u與v不屬於同一個連通區塊 then # find()
        將(u,v)加入T中; 
        將u與v所屬的連通區塊聯集; # union()
        # 如果T中已經有n-1個邊，可以提早結束
    end if
end for

下面一個簡單的例題用來介紹範例程式。

---

##### P-7-12. 最小生成樹 (\*)
輸入一個無向圖$G=(V,E,w)$，其中點以0 ~ $n-1$編號，而邊的權重是非負整數。計算$G$的最小生成樹的成本。兩點之間可能有多個邊。

Time limit: 2 秒

輸入格式：第一行是兩個正整數$n$與$m$，代表點數與邊數，接下來有$m$行，每行三個整數$u$, $v$, $w$代表一條無向邊$(u,v)$的長度是$w$。$n$不超過1e4，$m$不超過1e5, $w$是不超過1e4的非負整數。
輸出：輸出最小生成樹的成本，如果不存在則輸出 -1。

範例一輸入：
8 10
0 1 6
0 2 4
1 2 5
2 3 9
1 4 1
1 5 1
2 6 2
4 5 3
5 6 8
7 6 1

範例一輸出：
23

範例二輸入：
4 3
2 1 5
1 0 0
0 2 1

範例二輸出：
-1

範例一是本小節說明所用的例子。
(範例測資中前兩筆的n不超過500。)

---

Prim演算法幾乎與Dijkstra一模一樣，就不多做說明。

# p-7-12 O(mlogn) Prim algorithm
import heapq
n,m = [int(x) for x in input().split()]
oo = 10**9
adj = [[] for i in range(n)] # adj list
for i in range(m): # read edge (u,v)
    u,v,w = [int(x) for x in input().split()]
    adj[u].append((v,w))
    adj[v].append((u,w)) # maybe multiple edges, fine
#
d = [oo]*n
parent = [-1]*n
source = 0
done = [False]*n # whether the distance is converged
d[source] = 0
pq = [(0,source)] # (d[v],v)
while pq: # converge one vertex each iteration
    # find min d[] of not-done vertex
    dv,v = heapq.heappop(pq)
    if done[v]: continue # useless
    done[v] = True
    # update neighbor
    for u,w in adj[v]: 
        if not done[u] and w < d[u]: # shorter path to u
            d[u] = w
            heapq.heappush(pq,(d[u],u))
            parent[u]=v
    #
# end while
if max(d) == oo:
    print(-1)
else:
    print(sum(d))

以下是Kruskal演算法的範例程式。第4 ~ 6行讀入邊的資料後。就進行排序，排序依據第2欄位，也就是邊的長度。第10 ~ 23行是併查集的函數，這裡的union我們假設進來的兩點都已經確定是不相同的root，所以只是將比較小的集合併入大的集合。其他的部分就是根據演算法，對每一根邊檢查兩端是否是同一個區塊，若否，則加入該邊。最後根據是否加入了$n-1$個邊來判斷是否存在最小生成樹。

# p-7-12 O(mlogn) Kruskal algorithm
n,m = [int(x) for x in input().split()]
oo = 10**9
edge = [] 
for i in range(m): # read edge (u,v)
    edge.append([int(x) for x in input().split()])
edge.sort(key=lambda x: x[2]) # sort by weight
p = [-1]*n # parent
# find root
def rfind(p,u): 
    if p[u] < 0: return u
    p[u] = rfind(p,p[u])
    return p[u]
# union ru and rv, both are roots
def union(p,ru,rv):
    size = p[ru]+p[rv]
    if p[ru] < p[rv]:
        p[rv] = ru
        p[ru] = size
    else:
        p[ru] = rv
        p[rv] = size
    return 
#
total = 0 # total weight of edges
cnt = 0 # num of edges
for u,v,w in edge: 
    ru,rv = rfind(p,u),rfind(p,v)
    if ru != rv:
        cnt += 1
        total += w
        union(p,ru,rv)
    # else do nothing
# for
if cnt != n-1:
    print(-1)
else:
    print(total)

補充說明：不管邊是正的或是負的，最小生成樹的找法都是一樣，此外，邊的總和最大的最大生成樹以及最大的邊最小的生成樹都可以用類似的方法計算。
Minimum spanning tree的兩個演算法都需要用到特別的資料結構(prioroty queue or union-and-find)，所以應該不在APCS考試的範圍。

**End of Chapter 7**