那我們到底該如何找出graph中的MST(Minimum Spanning Tree)呢？

有個最經典的Prim’s algorithm可以用來找出MST，其概念是從任意一個點開始，找出與其相連的鏈結中weight最小的，它就會是構成MST的鏈結；之後我們要考慮的鏈結會是當前MST節點所有的鏈結：

下一步：

下一步：

以此類推，直到讓所有節點都相連在一起，即找到MST。

這個概念就是利用了上一章介紹的cut property，以下圖為例當我們進行Prim’s algorithm到節點7時，並已知要把7-5的連結加入MST中，在這裡先暫停一下，來分析為什麼這樣加就會是MST的結果。

我們把與點7連結的點視為一群，而沒有與點7連結的視為另一群，此時就會有crossing edge產生，而cut property告訴我們，最小的crossing edge就會是MST的結構。不覺得這個過程就跟剛剛的Prim’s algorithm一樣嗎？

但是每次都考慮所有與當前MST節點相連的鏈結實在太沒效率了，既然MST就是考慮weight最小的情境，我們其實可以用類似Dijkstra的概念，只是從紀錄起點到各點的距離變成紀錄與之相連的edge最小的可能：

從點0開始：

就像Dijkstra一樣去relax相鄰的節點，只是relax的依據是看edge weight，在這邊還沒感覺，因為剛好relax的值就是起點的距離

進行到點2，此時有個特點說明一下，就是從PQ(Priority Queue)取出的點，就是最終MST的結構了：

這時從點2的relax就可以知道，我們relax的是當前節點到各點的edge weight，而不是起點的距離：

就這樣不斷進行下去，直到找到MST，這就是Prim’s algorithm。

來分析看看Prim’s algorithm的runtime，假設我們的PQ是min-heap的實作，各種操作的效能是O(log V)，如同先前的Graph API定義，V是graph的節點數，E是總鏈結數：

效能是O(E logV)。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License