最小生成樹and最短路徑-wenkub
2023-07-08 18:52:43 本頁面
【正文】 做些什么，所以用struct來自定義就合適不過了。然而，圖的存貯結(jié)構(gòu)采用邊集數(shù)組，且權(quán)值相等的邊在數(shù)組中排列次序可以是任意的，該方法對于邊數(shù)相對比較多的圖不是很實用，浪費時間。而現(xiàn)在來到了《數(shù)據(jù)結(jié)構(gòu)》的課程上，我覺得還是有必要寫寫理解與體會，好讓以后用起來沒那么難。最小生成樹and最短路徑無獨有偶，在兩個學(xué)期的期末中兩門不同的科目《離散數(shù)學(xué)》和《數(shù)據(jù)結(jié)構(gòu)》中都談到了圖及其衍生的最小生成樹、最短路徑問題，并給出了相應(yīng)的算法——克魯斯卡爾、普林、迪杰斯特拉、沃舍爾算法。最小生成樹（Minimum Spanning Tree,MST ）一個有 n 個結(jié)點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結(jié)點，并且有保持圖連通的最少的邊?？梢哉f克魯斯卡爾算法是很直觀的算法，適合人的直觀思考方式，但是因為上面論述的緣故，克魯斯卡爾算法比較適用在稀疏圖（邊的數(shù)目不是很多的圖）上。struct edge{ int node_1。 另外，文中提及了最小邊、次小邊，這就暗示了應(yīng)該對所有的邊進(jìn)行排序（sort）。若造成回路，則舍棄這條邊，轉(zhuǎn)而觀察加入次小邊。從指定頂點開始將它加入集合中，然后將集合內(nèi)的頂點與集合外的頂點所構(gòu)成的所有邊中選取權(quán)值最小的一條邊作為生成樹的邊，并將集合外的那個頂點加入到集合中，表示該頂點已連通。邊數(shù)不是制約普林算法的因素，結(jié)點才是。當(dāng)a,b之間沒有邊的時候，應(yīng)當(dāng)使data[a][b] = INF（INF表示無窮）。初始化used狀態(tài)（等于0代表在B中）memset(used,0,sizeof(used))。所以當(dāng)（2）中采用了第一結(jié)點，那么這個數(shù)組應(yīng)當(dāng)被初始化為for(int kn = 1。}當(dāng)進(jìn)行（3）時只需這樣尋找for(int i = 0 。 lowcost[i] min ) {min = lowcost[i] 。 ks++){if (!used[ks] amp。 }}時間復(fù)雜度若n表示圖的結(jié)點數(shù)，那么初始化需要O(n)，找出最小邊O(n
電大資料相關(guān)推薦
鄂ICP備17016276號-1