如何用淺顯的語言解釋Kruskal演算法和Prim演算法?
02-05
圖論書上的解釋看的很暈。。
Kruskal是對邊做操作，每次選出一條最短邊，如果它和當前最小生成樹（森林）不構成迴路就將其加入最小生成樹，否則將其刪除，直到所有邊都處理完畢Prim是對點做操作，維護一個在最小生成樹中的點的頂點集A，以及一個待處理點的頂點集B，每次找出連接這兩個集合的最短邊，並將其兩個頂點都加入集合A，直到所有頂點都處理完畢
不嚴謹的說：將全集分為遍歷集合未遍歷集。兩種演算法都是遍歷集慢慢擴大為全集的過程。Kruskal：集合中元素是邊，每次從未遍歷集中找一個最短邊，如果遍歷集包含它後不會構成迴路，就包含，重複過程直到所有點都連通。Prim：集合中元素是點，每次從未遍歷集中找一個距離遍歷集距離最近的點，將其包含，重複過程直到包含所有點。當然對於Kruskal，遍歷集並沒有擴展為全集，把全部邊都包含了也沒有意義了。
普里姆演算法的思想是隨便選一個點，然後看他周圍的點，找一個最小的路徑連接的另一個點，再將這個點吃進去，然後現在你的集合有兩個點，將你擁有的兩個點看做一個大結點（類似與電路中大平面的KCL推廣形式），再找周圍的點，選一個最短路徑連接的另一個點，再吃進去，最後，將所有點吃完你的演算法就完成了。
而克魯斯卡爾的演算法是將所有路徑進行一次排序，然後選取n-1條路徑，具體的選法就是先選擇最小邊，然後現在你擁有兩個結點，選取下一條的原則：第一原則是最小，第二原則是選取的結點與已擁有的結點之間，不能通過選取的邊形成迴路（先滿足第一原則再滿足第二原則，不滿足第一或第二原則都不行），這樣的重複n-1次就選好了所需要邊了；
都是自己看書聽老師講的（逃。。。。）
推薦閱讀：