最小生成樹 １．是一棵樹 ２．無回路 ３．Ｎ個頂點一定有Ｎ－１條邊 ４．包含全部頂點 ５．Ｎ－１條邊都在圖里 ６．邊的權重和最小
生成約束： １．只能用圖里有的邊 ２．只能正好用掉Ｎ－１條邊 ３．不能有回路
主要算法：
PRim算法 －－ 讓樹長大
int prim(int n) { memset(vis,false,sizeof(vis));//標記數組清零 for(int i=1; i<=n; i++) { dis[i] = arr[1][i];//從1號節點開始生成樹 } int ans = 0;//距離權值總和 vis[1] = true;//生成樹的根（起點）標記訪問過 for(int i=2; i<=n; i++)//要生成n-1條邊，所以循環n-1次 { int pos = i;//用來記錄每一次循環找到的節點編號 int Min = INF;//無窮大 for(int j=1; j<=n; j++)//對dis數組進行遍歷找到距離最小的 { if(vis[j]==false && dis[j] < Min)//如果該點未被訪問過，并且距離更小 { Min = dis[j];//更新最小距離 pos = j;//記錄節點編號 } } ans += Min;//加上找到的最小權值 vis[pos] = true;//標記找到的該點被訪問 for(int j=1; j<=n; j++)//更新dis數組 { if(vis[j]==false && dis[j] > arr[pos][j])//如果該點未被訪問過且距離更大 { dis[j] = arr[pos][j];//更新生成樹到該點的距離 } } } return ans;//得出權值總和 }Kruskal算法 ——— 將森林變為樹
新聞熱點
疑難解答
