【圖論】信手拈來的Prim，Kruskal和Dijkstra

關于三個簡單的圖論算法

prim，dijkstra和kruskal三個圖論的算法，初學者容易将他們搞混，是以放在一起了。

prim和kruskal是最小生成樹（MST）的算法，dijkstra是單源最短路徑的算法。

prim

最小生成樹prim算法采用了貪心政策：把點分成兩個集合，A為已被處理（已經在最小生成樹中）的頂點，B為待處理的頂點，(A,B)也就是一個割。若邊(u,v)滿足u∈A，v∈B，那麼(u,v)就是通過割(A,B)的一條邊。

很自然的，會有一定數量的邊會通過該割，其中權重最小的邊就是輕邊。

什麼是輕邊？左邊集合和右邊集合就組成一個割，其中邊(a,b)是跨越兩個集合最小的邊（途中标記為紅色），它就是要找的輕邊。

每次操作都是選擇min{w(u,v)|u∈A,v∈B}，進而将v加入到A中，即将v标記為已處理頂點，直到将所有點都處理完為止。

上述過程可以産生最小生成樹，即證明：A，B通過輕邊（權重最小的邊）(u,v)連接配接，現假設不選擇(u,v)，而選擇(u’,v’)得到了更優的最小生成樹，注意w(u,v)<w(u’,v’)。證明推翻這個假設即可。

把(u’,v’)去掉，補上(u,v)，這不影響A，B的連通，這樣就得到了比上述假設更優的最小生成樹，進而推翻假設，同時也證明了這個算法具有最優子結構。

prim的僞代碼：

Code Sample

<code>visit[0] =</code><code>true</code>

<code> </code><code>min = MAX_VALUE</code>

<code> </code><code>if</code> <code>!visit[j] && min>dist[j]</code>

<code> </code><code>if</code> <code>!visit[k] && dist[j]>tab[i][j]</code>

kruskal

最小生成樹kruskal算法也具有貪心政策：将所有點邊按權值大小從小到大排列，每次都從中選取最小權值的邊(u,v)，并把它添加到正在生長的森林中。是以開始的時候圖中n個頂點構成森林中的n棵樹（通俗的講就是n個集合），而且這些樹（集合）隻有一個頂點。

重複上述過程，就可以将森林中的樹不斷的合并（通俗的講就是合并兩個不相交集合），直到将所有點同屬于一棵樹為止（通俗的講就是隻剩下一個集合）。

如上圖，有了四個獨立的集合，先不管上面的邊上從這個集合中哪個點連到那個集合的哪個點，我們隻要找到最小權值的邊（對于上面的圖中是11），合并集合即可。是以上面的例子進行合并後：

kruskal證明過程可以參照prim算法的證明過程。

kruskal實作過程涉及了不相交子集的合并，可以開辟一個簡單的數組，然後通過标記每個點的父節點來簡化合并過程。舉例：圖中有10個頂點

一開始：

parent

假設一段時間後：0 1 2 0 0 0 6 7 1 1

從上面的表可以判斷頂點1，頂點8和頂點9同屬于同一個集合；頂點0，頂點3，頂點4和頂點5同屬于一個集合；凡是parent[i]=i都是單個點的集合，比如頂點2等。

是以程式中設計了兩個函數，find和makeset，find用于找到一個集合的root，比如find(9)=1，find(5)=0；而makeset用于合并兩個不相交的子集，它的作用就是修改其中一個集合的root就可以了。需要注意的是，kruskal算法要防止出現環，是以，當發現最小的邊(u,v)同屬于一棵樹的時候，不能将其makeset。

kruskal的僞代碼：

<code> </code><code>parent[i] = i</code>

<code>// 根據權值升序排序</code>

<code>while</code> <code>set_count>1</code>

<code> </code><code>minprice+=w(u,v)</code>

<code> </code><code>makeset(u,v)</code>

<code> </code><code>// update u and v;</code>

prim和kruskal的實作差別

一個非常明顯的差別就是prim在任何時刻都隻有兩個集合，一個是已處理頂點集合，一個是待處理集合；而kruskal則有多個集合，是以kruskal涉及不相交子集合并的比較複雜的操作問題。

簡單的MST應用：某省調查鄉村交通狀況，得到的統計表中列出了任意兩村莊間的距離。省政府“暢通工程”的目标是使全省任何兩個村莊間都可以實作公路交通（但不一定有直接的公路相連，隻要能間接通過公路可達即可），并要求鋪設的公路總長度為最小。請計算最小的公路總長度。或者省政府“暢通工程”的目标是使全省任何兩個村莊間都可以實作公路交通（但不一定有直接的公路相連，隻要能間接通過公路可達即可）。經過調查評估，得到的統計表中列出了有可能建設公路的若幹條道路的成本。現請你編寫程式，計算出全省暢通需要的最低成本。

dijkstra

dijkstra要求所有點邊的權值都是非負的，主要是如果出現負權邊，可能會出現負權環，dijkstra就無法應付了。

關于dijkstra的小故事這個人名真不好記，是以我一直把它讀作disco，對不住迪科斯徹爹爹。

dijkstra算法中設定了一個頂點集合S，從源點到集合中的頂點的最終最短路徑的權值均已經确定。dijkstra過程反複從V-S（V即圖的頂點集）中選擇一個頂點v，使得d(s,v)為最短，并将v加入到集合S中，接着對v的所有邊進行松弛。

什麼是松弛？就是可能會出現這樣的情況，假設源點為s，tab(u,v)為頂點u到頂點v的權值，dist(u)為迄今為止找到的s到u最短路徑。在松弛(u,v)的過程中，要測試是否可以通過u，對迄今為止找到的v的最短路徑進行改進。也就是可能會出現dist(v)>dist(u)+tab(u,v)的情況。上面的圖因為dist(v)>dist(u)+tab(u,v)即6>2+3，故要對邊(u,v)進行松弛的時候會将dist(v)從 6更正為5。但對于下面的情況，在松弛過後，dist(v)沒有改變因為dist(v)<=dist(u)+tab(u,v)即4& lt;=2+3。松弛技術在Bellman-Ford負權回路探測算法中也有應用。不禁想起還小的一個作為題：兩點之間曲線更短…

dijkstra的過程

初始将頂點s加入到S中，并更新s到其他頂點的路徑權值。

選擇最短路徑dist(s,t)，并将t加入到S中。

在第一步中得到t，對于u∈V-S，松弛邊(t,v)。

重複上述過程，直到所有的頂點都被加入到集合S中為止。

可以給出僞代碼：

<code>visit[0] =</code><code>true</code><code>;</code>

<code> </code><code>// 尋找最短路徑(s,t)，同時把t加入S集合</code>

<code> </code><code>if</code> <code>!visit[j] && dist[j]<min</code>

<code> </code><code>visit[j] =</code><code>true</code>

<code> </code><code>// 松弛邊(t,v)，其中v為頂點</code>

<code> </code><code>if</code> <code>!visit[k] && dist[k]>dist[j]+tab[j][k]</code>

簡單的dijkstra應用：某省自從實行了很多年的暢通工程計劃後，終于修建了很多路。不過路多了也不好，每次要從一個城鎮到另一個城鎮時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。現在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離。

總結

prim，kruskal和dijkstra算法有貪心政策，他們貪在哪啊？

prim：每次執行都選擇輕邊

kruskal：每次執行都選擇權值最小的邊，同時合并兩個不相交的子集

dijkstra：每次執行都選擇路徑最短d(s,t)，并将頂點t加入到集合S中，同時對邊進行松弛

附Dijkstra和Prim算法的源代碼，他們都的基于鄰接矩陣的，注意不是基于鄰接表的

【圖論】信手拈來的Prim，Kruskal和Dijkstra附件.rar

轉載 http://daoluan.net/blog/prim-kruskal-dijkstra/