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