最小生成樹and最短路徑-文庫吧
2025-06-08 18:52 本頁面
【正文】 及了最小邊、次小邊，這就暗示了應(yīng)該對(duì)所有的邊進(jìn)行排序（sort）。比較函數(shù)應(yīng)以value作衡量。bool cmp(edge a , edge b){ return 。}現(xiàn)在剩余最后的問題——回路的避免。其實(shí)這個(gè)也很容易避免，我們可以定義一個(gè)數(shù)組used[max]，它記錄了每一個(gè)結(jié)點(diǎn)是否被應(yīng)用的情況，當(dāng)要加入的一條邊中used[]和used[]都已被應(yīng)用，那么加入的這條邊必然造成回路，否則不會(huì)。若造成回路，則舍棄這條邊，轉(zhuǎn)而觀察加入次小邊。排序后的情況edge數(shù)組node_1node_2value01211242224333444235用紅線將舍棄的邊刪除后，剩余的就成為了最小生成樹了。時(shí)間復(fù)雜度若e表示圖的邊數(shù)，那么，排序過程將有O(eloge)，生成過程則是O(e)，故總的來說，時(shí)間復(fù)雜度為O(eloge)。普林（Prim）算法克魯斯卡爾算法以邊為出發(fā)點(diǎn)，相應(yīng)地，普林算法則以點(diǎn)為出發(fā)點(diǎn)。從指定頂點(diǎn)開始將它加入集合中，然后將集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)所構(gòu)成的所有邊中選取權(quán)值最小的一條邊作為生成樹的邊，并將集合外的那個(gè)頂點(diǎn)加入到集合中，表示該頂點(diǎn)已連通。再用集合內(nèi)的頂點(diǎn)與集合外的頂點(diǎn)構(gòu)成的邊中找最小的邊，并將相應(yīng)的頂點(diǎn)加入集合中。如此下去直到全部頂點(diǎn)都加入到集合中，即得最小生成樹。以點(diǎn)作為出發(fā)點(diǎn)很好地解決了克魯斯卡爾算法解決邊數(shù)很多的圖的可怕時(shí)間復(fù)雜度的問題。邊數(shù)不是制約普林算法的因素，結(jié)點(diǎn)才是。普林算法的簡單演算步驟：（1）初始化集合A()，表示沒有點(diǎn)以加入到生成結(jié)點(diǎn)中，初始化集合B，使B包含所有結(jié)點(diǎn)；（2）從B中選擇一個(gè)點(diǎn)作為始加入到A中并從B中剔除；（3）選擇A中所有的點(diǎn)中能到達(dá)B的最小權(quán)值邊，將這條邊的另一個(gè)點(diǎn)加入到A中并從B中剔除；（4）重復(fù)（3）操作直至B為NULL，則為最小生成樹。鄰接矩陣如果說克魯斯卡爾算法使用自定義的邊集數(shù)組存
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1