日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

最小生成樹

太白ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應用場景，ssl證書未來市場廣闊！成為成都創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

最小生成樹（minimum spanning tree）是由n個頂點，n-1條邊，將一個連通圖連接起來，且使權值最小的結構。
最小生成樹可以用Prim（普里姆）算法或kruskal（克魯斯卡爾）算法求出。

我們將以下面的帶權連通圖為例講解這兩種算法的實現(xiàn)：

注：由于測試輸入數(shù)據(jù)較多，程序可以采用文件輸入

Prim（普里姆）算法

時間復雜度：O（N^2）（N為頂點數(shù)）
prim算法又稱“加點法”，用于邊數(shù)較多的帶權無向連通圖
方法：每次找與之連線權值最小的頂點，將該點加入最小生成樹集合中
注意：相同權值任選其中一個即可，但是不允許出現(xiàn)閉合回路的情況。

代碼部分通過以下步驟可以得到最小生成樹：

1.初始化：

lowcost[i]:表示以i為終點的邊的最小權值,當lowcost[i]=0表示i點加入了MST。
mst[i]:表示對應lowcost[i]的起點，當mst[i]=0表示起點i加入MST。
由于我們規(guī)定最開始的頂點是1，所以lowcost[1]=0，MST[1]=0。即只需要對2~n進行初始化即可。

#define MAX 100 
#define MAXCOST 0x7fffffff 

int graph[MAX][MAX]; 

void prim(int graph[][MAX], int n) 
{ 
 int lowcost[MAX]; 
 int mst[MAX]; 
 int i, j, min, minid, sum = 0; 
 for (i = 2; i <= n; i++) 
 { 
 lowcost[i] = graph[1][i];//lowcost存放頂點1可達點的路徑長度 
 mst[i] = 1;//初始化以1位起始點 
 } 
 mst[1] = 0;

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網(wǎng)頁題目：C語言實現(xiàn)最小生成樹構造算法-創(chuàng)新互聯(lián)
網(wǎng)站地址：http://www.dlmjj.cn/article/dojjjs.html