最小生成樹and最短路徑(編輯修改稿)
2025-07-20 18:52 本頁面
【文章內容簡介】 儲圖是直觀的，那么普林算法采用自定義的點集數(shù)組也是合適的？如果以某一點作為單獨的數(shù)據(jù)結構，那么這一數(shù)據(jù)結構應當包含有與這個點有關的邊的所有信息——權值和對應點。但事前我們并不知道這個圖的點的最大度數(shù)為多少，帶著這種未知來定義struct是危險的，所以我們應當采用鄰接矩陣——一個存放頂點間關系（邊或?。┑臄?shù)據(jù)的二維矩陣，即有一個二維矩陣data，data[a][b]=c表示a結點和b結點有一條長為c的邊，相應地，data[b][a]=c。當a,b之間沒有邊的時候，應當使data[a][b] = INF（INF表示無窮）。集合由演算步驟中得知我們需要抽象出一個集合的概念，用以分開集合A和集合B。對于這種簡單的區(qū)分，大可不必抽象出對象出來。運用克魯斯卡爾中used數(shù)組的概念也可模擬出這種集合，當used[i]等于特定值代表結點i在哪個集合中即可。初始化used狀態(tài)（等于0代表在B中）memset(used,0,sizeof(used))。然后選取第一結點來實現(xiàn)（2）操作used[0] = 1 。優(yōu)化（3）（3） 選擇A中所有的點中能到達B的最小權值邊，將這條邊的另一個點加入到A中并從B中剔除；如何尋找最小權值邊？如果直觀地去做，從A中各點遍歷，那么每加入一個點到A所費的時間也是驚人的，所以也引入兩個數(shù)組來作優(yōu)化。lowcost數(shù)組：lowcost[i]表示A集合中到結點i(I必然在集合B中)的權值；closest數(shù)組：對應與lowcost，表示結點i到集合A的用最小權值邊連通的點。所以當（2）中采用了第一結點，那么這個數(shù)組應當被初始化為for(int kn = 1。 kn n 。 ++kn ){lowcost[kn] = data[0][kn]。closest[kn] = 0 。}當進行（3）時只需這樣尋找for(int i = 0 。 i n 。++i ){if( !used[i] amp。amp。 lowcost[i] min ) {min = lowcost[i]
電大資料相關推薦
鄂ICP備17016276號-1