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