整理自《數(shù)據(jù)結(jié)構(gòu)高分筆記》
1智嚷、普里姆算法
算法思想
普利姆算法的基本思想如下：從圖中任意取出一個(gè)頂點(diǎn)嘱么，把它當(dāng)成一棵樹，然后從與這棵樹相連接的變種選取一條最短（權(quán)值最醒舐）的邊，然后把這條邊及其所連接的頂點(diǎn)也加入這棵樹中珍坊，此時(shí)得到了一棵有兩個(gè)頂點(diǎn)的樹牺勾。然后從與這棵樹相接的邊中選取一條最短的邊，并將這條邊及其所連接的頂點(diǎn)加入這棵樹中垫蛆，得到一棵有三個(gè)頂點(diǎn)的樹禽最。以此類推腺怯，知道圖中所有頂點(diǎn)都被并入樹中為止袱饭。
用普利姆算法構(gòu)造最小生成樹的過程中，需要建立兩個(gè)數(shù)組vset[] 和 lowcost[] 呛占。vset[i]=1 表示頂點(diǎn)i已被并入生成樹中虑乖，如果vset[i]=0則表示頂點(diǎn)i還未被并入生成樹中，lowcost[]數(shù)組中存放當(dāng)前生成樹到剩余各頂點(diǎn)最短邊的權(quán)值晾虑。
算法的執(zhí)行過程如下：
從樹中某一個(gè)頂點(diǎn)v0開始疹味，構(gòu)造生成樹的算法執(zhí)行過程如下：
1）將v0到其他頂點(diǎn)的所有邊當(dāng)作候選邊仅叫。
2）重復(fù)以下步驟n-1次，使得其他n-1個(gè)頂點(diǎn)被并入生成樹中：從候選邊中挑選出權(quán)值最小的邊輸出糙捺，并將與該邊另一端相接的頂點(diǎn)v并入生成樹中诫咱。考查剩余頂點(diǎn)vi洪灯，如果(v,vi)的權(quán)值比lowcost[vi]小坎缭，則用(v,vi)的權(quán)值更新lowcost[vi]。
例子解析
比如下面的圖中签钩，我們首先從v1開始掏呼，與v1相連的頂點(diǎn)有v2，v3铅檩，v4憎夷，對(duì)應(yīng)的邊的權(quán)值分別為6，1昧旨，5拾给，所以選擇v1-v3，將v3并入生成樹中兔沃，在所有與v1或者v3相連的邊中鸣戴，權(quán)值最小的是v3-v6，權(quán)值為4粘拾，所以將v6并入生成樹中窄锅，重復(fù)上面的過程，直到所有的頂點(diǎn)都被并入最小生成樹中缰雇。
時(shí)間復(fù)雜度
普利姆算法的時(shí)間復(fù)雜度只與圖中的頂點(diǎn)數(shù)有關(guān)系入偷，而與邊數(shù)沒有關(guān)系，所以適用于稠密圖械哟。
2疏之、克魯思卡爾算法
基本思想
克魯斯卡爾算法的思想比較簡(jiǎn)單，首先將圖中按邊權(quán)值從小到大排序暇咆，然后從最小邊開始掃描各邊锋爪，并檢測(cè)當(dāng)前邊是否為候選邊，即是否該邊的并入會(huì)構(gòu)成回路爸业，如果不構(gòu)成回路其骄，則將該邊并入生成樹中，直到所有邊都被檢測(cè)完為止扯旷。
例子解析
我們?nèi)匀挥蒙厦嬗玫降膱D來解釋克魯斯卡爾算法的基本思想：
1）所有邊中權(quán)值最小的邊為v1-v3拯爽，所以將該邊加入生成樹中。
2）剩余最小的邊為v4-v6钧忽，不構(gòu)成回路毯炮，將該邊加入生成樹中逼肯。
3）剩余最小的邊為v2-v5，不構(gòu)成回路桃煎，將該邊加入生成樹中篮幢。
4）剩余最小的邊為v3-v6，不構(gòu)成回路为迈，將該邊加入生成樹中洲拇。
5）剩余最小的邊為v2-v3、v3-v4和v1-v4曲尸，v3-v4和v1-v4的加入都會(huì)構(gòu)成回路赋续，v2-v3加入不構(gòu)成回路，將該邊加入生成樹中另患。
此時(shí)所有的點(diǎn)都已聯(lián)通纽乱，最小生成樹生成結(jié)束。
時(shí)間復(fù)雜度
克魯斯卡爾算法的時(shí)間復(fù)雜度與邊數(shù)e相關(guān)昆箕，而與頂點(diǎn)數(shù)基本無關(guān)鸦列，所以適用于稀疏圖。
