圖的應用：最小生成樹

• 最小生成樹的定義：
• 最小生成樹的性質：
• Prime算法：（貪心算法思想）
• • Prime算法的代碼實現原理：
  • Prime算法的實現代碼：
  • Prime算法的性能：
• Kruskal算法：（貪心算法思想）
• • Kruskal算法的實現原理：
  • Kruskal算法的代碼實現：
  • Kruskal算法的性能：
• 算法性能對比：

最小生成樹的定義：

最小生成樹的性質：

1、不唯一性：

Prime算法：（貪心算法思想）

要點:

1、具有最小權值 2、無回路 3、初始結果集為空

Prime算法的代碼實現原理：

min_weight[n]:表示定點數量的大小，已挑選頂點到未挑選頂點權值最小的邊
adjvex[n]:表示是哪個頂點將這條邊引入的

Prime算法的實現代碼：

void MST_Prime(Graph G){//倆個輔助數組int min_weight[G.vexnum];int adjvex[G.vexnum];//初始化倆個輔助數組for(int i=0;i<G.vexnum;i++){min_weight[i] = G.Edge[0][i];adjvex[i] = 0;}int min_arc; //表示挑選的最小邊int min_vex; //表示挑選邊的另一個頂點(數組下標)for(int i=1;i<G.vexnum;i++){ //循環n-1次，將剩下的n-1個頂點加入結果樹min_arc = MAX; //將最小邊的長度置為無窮大，用于比較for(int j=1;j<G.vexnum;j++) //挑選滿足條件的邊，以及此邊的頂點if(min_weight[j] != 0 && min_weight[j] < min_arc){min_arc = min_weight[j];min_vex = j;}min_weight[min_vex] = 0; //加入后給此邊長度置0for(int j=0;j<G.vexnum;j++){ //加入新節點后修改其他數組的值if(min_weight[j] != 0 && G.Edge[min_arc][j] < min_weight[j]){min_weight[j] = G.Edge[min_arc][j];adjvex[j] = min_arc;}}} }

Prime算法的性能：

時間復雜度：O(|V|2)
適用于稠密圖，因為時間復雜度與邊無關

Kruskal算法：（貪心算法思想）

ps： numS表示連通分量，當其大于1不是一顆最小生成樹

要點：

1、具有最小權值 2、無回路 3、初始結果集為所有節點

Kruskal算法的實現原理：

堆排序sort() + 并查集

Kruskal算法的代碼實現：

typedef struct Edge{int a,b; //邊的倆個頂點下標 int weight; //權重 }; void MST_Kruskal(Graph G,Edge* edges,int* parent){ //圖，邊的集合，輔助變量 heap_sort(edges); //堆排序 Initial(parent); //初始化parent=-1 for(int i=0;i<G.arcnum;i++){ //邊的數量 int a_root = Find(parent,edges[i].a); //求第一個端點的根節點 int b_root = Find(parent,edges[i].b); //求第二個端點的根節點 if(a_root != b_root)Union(parent,a_root,b_root); //不相等加入結果集 } }

ps： 這里未實現的函數在前幾期博客中存在

Kruskal算法的性能：

時間復雜度：O(|E|log|E|)
更適用于稀疏圖，因為時間復雜度只與邊有關

算法性能對比：

總結

以上是生活随笔為你收集整理的数据结构之图的应用：最小生成树MST（prime算法和Kruskal算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。