導航:首頁 > 源碼編譯 > 普里姆演算法適合構造稠密圖
普里姆演算法適合構造稠密圖
發布時間：2025-09-01 11:42:38❶ 普里姆演算法的普里姆演算法的實現
為了便於在兩個頂點集U和V-U之間選擇權最小的邊，建立了兩個輔助數組closest和lowcost，它們記錄從U到V-U具有最小權值的邊，對於某個j∈V-U，closest[j]存儲該邊依附的在U中的頂點編號，lowcost[j]存儲該邊的權值。
為了方便，假設圖G採用鄰接矩陣g存儲，對應的Prim(g,v)演算法如下：
void Prim(MatGraph g,int v) //輸出求得的最小生樹的所有邊
{ int lowcost[MAXVEX]; //建立數組lowcost
int closest[MAXVEX]; //建立數組closest
int min,i,j,k;
for (i=0;i<g.n;i++) //給lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //構造n-1條邊
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出離U最近的頂點k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k為最近頂點的編號
}
printf( 邊(%d,%d),權值為%d
,closest[k],k,min);
lowcost[k]=0; //標記k已經加入U
for (j=0;j<g.n;j++) //修正數組lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{ lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
普里姆演算法中有兩重for循環，所以時間復雜度為O(n2)，其中n為圖的頂點個數。由於與e無關，所以普里姆演算法特別適合於稠密圖求最小生成樹。
與普里姆演算法適合構造稠密圖相關的資料
- 360加固了什麼反編譯
- 普里姆演算法適合構造稠密圖
- 編譯原理的目標代碼是什麼
- mac編譯慢cpu沒跑滿
- 對數函數變底運演算法則
- 找別人寫程序包括源碼嗎
- 模擬退火演算法matlab代碼
- 演算法工程師年齡大了以後怎麼辦
- ssm看源碼哪本書好
- basic語言演算法
- 你家離學校源碼用英語回答
- js二分搜索演算法
- pandas在哪裡編譯
- 分支定界法演算法
- 電腦安全編譯器
- 累加C語言演算法
- proteus51編譯工具
- 圖像ai演算法工程師創業
- 傅氏演算法和積分演算法
- 小米手機發布源碼
- vs中編譯在哪
- 單片機編譯picc
- 什麼是系統級編譯
- 微信做照片小程序源碼
- 三根陰線選股指標源碼
- PDF編譯base64位文件
- 華為方舟編譯器和miui
- 編譯原理vn集合
- 信源編解碼作用
- 編譯腳本失敗
- 編譯無效對象是什麼意思
- 編譯程序軟體哪個好
- floyd最短路徑演算法c
- 計算機圖形學涉及的演算法
- 數據結構的經典演算法題
- steam源碼
- 關於對數的運演算法則及公式
- 什麼人要懂編譯原理
- 源碼改單
- cdda演算法
- 智能合約編譯部署過程的小白講解
- ios演算法和數據結構