数据结构与算法（7-3）最小生成树（普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法）
目錄
一、最小生成樹簡介
二、普里姆算法（Prim）?
1、原理??
2、存儲
2-1、圖頂點和權：
2-3、 最小生成樹：
3、Prim()函數
3-1、新頂點入樹
3-2、保留最小權
3-3、 找到最小路徑
3-4、判斷退出或遞歸
?4、代碼
三、克魯斯卡爾算法
1、原理
2、過程
?2-1、存儲結構
2-2、從小到大排邊
2-3、Kruskal算法以及防止連通（防止連通是難點）
3、代碼
參考資料
一、最小生成樹簡介
用途：找到連通圖的最短路徑之和。
注：最小生成樹能夠保證整個拓撲圖的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。
應用：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。
最小生成樹和最短路徑區別：
最小生成樹：連通圖的最短路徑。
最短路徑：兩任意結點之間（可以非鄰接）的最短路徑。
??
二、普里姆算法（Prim）?
1、原理??
把樹視為一個整體（頂點），從根部（自選定）出發，一點一點向周圍搜索，找到周圍權最小的頂點（最小路徑），把它納入Prim樹，把Prim樹的整體視作一個根結點，繼續往下遞歸搜索。
（欣賞下面的三樣圖）
1、
2、?
? 3、
2、存儲
2-1、圖頂點和權：
//圖（頂點和權）
typedef struct
{char vertex[MAXSIZE];int weight[MAXSIZE][MAXSIZE]; //權可以代替邊（自身為0，相連有值，不相連無窮大）
}Graph;
Graph G;不需要再加邊，因為權=0即自身，權=無窮大即斷開，所以不需要再加邊來表示連接關系。
2-3、 最小生成樹：
//最小生成樹
typedef struct
{char vertex[MAXSIZE]; //最小生成樹內部頂點int weight[MAXSIZE]; //最小生成樹權重（內部為0，相連有值，不相連無窮大）int minway[MAXSIZE]; //最小生成樹最短路徑
}MST;
MST M;3、Prim()函數
3-1、新頂點入樹
最小生成樹也是越積越多，頂點vertex納入最小生成樹，則M.vertex[index]=vertex，其對應權M.weight[index]=0。
M.vertex[]：存放最小生成樹內部的頂點。
M.weight[]：存放最小生成樹內部距離外界的最短路徑。
3-2、保留最小權
把新入樹的頂點的權和樹本身的權進行比較，保留更小的一方（因為要生成的是最短路徑和）。
3-3、 找到最小路徑
記錄從最小生成樹內部的頂點連向外界頂點的最短路徑（最小權），保留下來即為本次行走的權。（也是下一次需要納入的權）（先納入頂點，在找下一次納入的權）
3-4、判斷退出或遞歸
如果Prim()函數調用次數達到頂點長度則退出遞歸，否則一直遞歸調用Prim()函數。
//獲取最小生成樹的最小權值下標
int FindMin()
{int i, min = 0;for (i = 0; i < length; i++){if (M.weight[i] != 0) //跳過0（即跳過內部頂點）{if (M.weight[min] == 0 || M.weight[min] > M.weight[i]) //跳過0，取最小min = i;}}return min;
}//普里姆算法
void Prim(char vertex, int index) //放入根
{int i, j, min;//獲取最小生成樹新的頂點M.vertex[index] = vertex; //新頂點//獲取最小生成樹新的權M.weight[index] = 0; //新權（納入最小生成樹內部，為0）for (i = 0; i < length; i++){ if (M.weight[i] > G.weight[index][i]) //獲得最小權{M.weight[i] = G.weight[index][i]; //最小生成樹的權}//標記最小路徑if (M.weight[i] == 0)for (j = 0; j < length; j++){// 行!=列(0) i和j不能都在最小生成樹內（不能連接自己） if (M.minway[index]>G.weight[i][j] && j!=i && ((M.weight[i]!=0)||(M.weight[j]!=0))) //i != jM.minway[index] = G.weight[i][j];}}printf("%c %d ", M.vertex[index], M.minway[index]);count++;//判斷退出if (count >= length)return;//尋找下一個最小生成樹下標（跳過0）min = FindMin();Prim(G.vertex[min], min);
}?4、代碼
//普里姆算法(Prim)————圖的最小生成樹
//把樹視為一個整體（頂點），從根部（自選定）出發，一點一點向周圍搜索，
//找到周圍權最小的頂點（最小路徑），把它納入Prim樹，把Prim樹的整體視作一個根結點，
//繼續往下遞歸搜索。
//自實現，目前有一定的缺點：時間復雜度O(n^3)有些高
/*測試：
ABCDEFGHI
B 10 F 11
C 18 I 12 G 16
B 18 I 8 D 22
C 22 I 21 G 24 H 16 E 20
D 20 H 7 F 26
A 11 G 17 E 26
B 16 D 24 F 17 H 19
D 16 E 7 G 19
B 12 C 8 D 21
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define MAXSIZE 20
#define MAX 65535 //代表無窮大
int length = 0; //頂點個數
int count = 0; //計數Prim最小生成樹元素個數//圖（頂點和權）
typedef struct
{char vertex[MAXSIZE];int weight[MAXSIZE][MAXSIZE]; //權可以代替邊（自身為0，相連有值，不相連無窮大）
}Graph;
Graph G;//最小生成樹
typedef struct
{char vertex[MAXSIZE]; //最小生成樹內部頂點int weight[MAXSIZE]; //最小生成樹權重（內部為0，相連有值，不相連無窮大）int minway[MAXSIZE]; //最小生成樹最短路徑
}MST;
MST M;//輸入頂點
void InputVertex()
{int i;char ch;printf("請輸入圖的頂點：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){G.vertex[i] = ch;scanf("%c", &ch);}length = i;
}//圖權重初始化
void GraphWeightInit()
{int i, j;for (i = 0; i < length; i++){for (j = 0; j < length; j++){if (i == j) //指向自己G.weight[i][j] = 0;elseG.weight[i][j] = MAX; //無窮大}}
}//根據數據查找圖頂點下標
int FindIndex(char ch)
{int i;for (i = 0; i < length; i++){if (G.vertex[i] == ch)return i;}return -1;
}//獲取最小生成樹的最小權值下標
int GetMin()
{int i, min = 0;for (i = 0; i < length; i++){if (M.weight[i] != 0) //跳過0（即跳過內部頂點）{if (M.weight[min] == 0 || M.weight[min] > M.weight[i]) //跳過0，取最小min = i;}}return min;
}//創建圖
void CreateGraph()
{int i, j, index, weight;char ch;for (i = 0; i < length; i++){printf("請輸入%c的鄰接頂點及權重（空格分隔，換行結束）：\n", G.vertex[i]);scanf("%c", &ch);while (ch != '\n'){while (ch == ' ') //為空格{scanf("%c", &ch); //輸入字符continue;}index = FindIndex(ch);scanf("%d", &weight); //輸入權重while (weight == 32) //32為空格的ASCII碼{scanf("%d", &weight);continue;}G.weight[i][index] = weight; //存入權重scanf("%c", &ch); //(下一輪)輸入字符}}
}//最小生成樹初始化
void MST_Init()
{for (int i = 0; i < length; i++){M.weight[i] = MAX; //權初始設置為無窮大（無鄰接結點）M.minway[i] = MAX; //最短路徑值}
}//普里姆算法
void Prim(char vertex, int index) //放入根
{int i, j, min;//獲取最小生成樹新的頂點M.vertex[index] = vertex; //新頂點//獲取最小生成樹新的權M.weight[index] = 0; //新權（納入最小生成樹內部，為0）for (i = 0; i < length; i++){if (M.weight[i] > G.weight[index][i]) //刷新最小權{M.weight[i] = G.weight[index][i]; //覆蓋最小生成樹的權}//找到最小路徑（最小生成樹）if (M.weight[i] == 0) //最小生成樹內部for (j = 0; j < length; j++){// 行!=列(0) i和j不能都在最小生成樹內（不能連接自己）(i在內, j在外) if (M.minway[index] > G.weight[i][j] && j != i && ((M.weight[i] != 0) || (M.weight[j] != 0))) //i != jM.minway[index] = G.weight[i][j];}}printf("%c -> %d -> ", M.vertex[index], M.minway[index]);count++;//判斷退出if (count >= length)return;//尋找下一個最小生成樹下標（跳過0）min = GetMin();Prim(G.vertex[min], min); //遞歸Prim()函數
}//輸出測試
void Print()
{for (int i = 0; i < length; i++){printf("\n%c結點鄰接結點：\t", G.vertex[i]);for (int j = 0; j < length; j++){if (G.weight[i][j] != 0 && G.weight[i][j] != MAX) //有鄰接結點{printf("%c %d\t", G.vertex[j], G.weight[i][j]);}}}
}int main()
{InputVertex(); //輸入頂點GraphWeightInit(); //圖權重初始化CreateGraph(); //創建圖MST_Init(); //最小生成樹初始化printf("\n最小生成樹路徑及權（Prim算法）：\n");Prim(G.vertex[0], 0); //普里姆算法（最小生成樹）//Print(); //測試輸出return 0;
}（這個算法是自實現的，時間復雜度有些高，O(n^3)，先暫時不去優化，繼續往后學吧）
三、克魯斯卡爾算法
1、原理
以邊為基礎，從小到大依次選出最短路徑，產生最小生成樹。
原理圖：
第1步:將邊<E,F>加入R中。
邊<E,F>的權值最小，因此將它加入到最小生成樹結果R中。
第2步:將邊<C,D>加入R中。
上一步操作之后，邊<C,D>的權值最小，因此將它加入到最小生成樹結果R中。
第3步:將邊<D,E>加入R中。
上一 步操作之后，邊<D,E>的權值最小，因此將它加入到最小生成樹結果R中。
第4步:將邊<B,F>加入R中。
上一步操作之后，邊<C,E>的權值最小，但<C,E>會和已有的邊構成回路;因此，跳過邊<C,E>。同理，跳過邊<C,F>.將邊<B,F>加入到最小生成樹結果R中。
第5步:將邊<E,G>加入R中。
上一步操作之后，邊<E,G>的權值最小，因此將它加入到最小生成樹結果R中。
第6步:將邊<A,B>加入R中。
上一步操作之后，邊<F,G>的權值最小，但<F,G>會和已有的邊構成回路;因此，跳過邊<F,G>。同理，跳過邊<B,C>.將邊<A,B>加入到最小生成樹結果R中。
此時，最小生成樹構造完成!它包括的邊依次是: <E,F> <C,D> <D,E><B,F> ?<E,G> <A,B>.
2、過程
?2-1、存儲結構
1、圖的頂點
//圖的頂點
char vertex[MAXSIZE];2、圖的邊、克魯斯卡爾（最小生成樹數組）
//圖的邊（以邊為主體，裝入兩端頂點及權）
typedef struct Edge
{int begin;int end;int weight;
}Edge;
Edge E[MAXSIZE]; //邊數組
Edge K[MAXSIZE]; //Kruskal數組2-2、從小到大排邊
克魯斯卡爾算法按照邊的大小順序，從小到大排列，需要有序的邊
2-3、Kruskal算法以及防止連通（防止連通是難點）
圖不能相互連通，否則那就不叫“生成樹”了。
首先begin和end是兩個頂點，分別在邊weight的左右。
防止連通原理：一個樹上的任何結點，都可以追溯到相連通的尾部，如果追溯到的尾部元素，和新添加的元素一樣，那么則會產生連通，此時這兩個結點不能連接。
這里設置了一個circle[]數組，為了防止連通。
追溯尾部元素的代碼：
//根據頂點查找到尾（下標追溯）
int FindTail(char ch)
{int index = FindIndex(ch);while (circle[index] != -1){index = circle[index]; //追溯到尾（下標追溯）}return index; //返回尾（沒有連接頂點的話返回自身）
}Kruskal算法代碼：
//克魯斯卡爾(Kruskal)算法
//難點：是否連通判斷：需要追溯到尾，如果連通的話它們有共同的尾
void Kruskal()
{int i, now = 0, tail = 0; //檢測連通（頭和尾）for (i = 0; i < length_e; i++) //遍歷每條邊{tail = FindTail(E[i].begin); //獲取下標并追溯到尾（無連通則返回自身）now = FindTail(E[i].end); //獲取下標并追溯到尾//未連通，正常添加if (tail != now){circle[tail] = now; //尾連通（標識連通）K[count_k].begin = E[i].begin; //左頂點K[count_k].end = E[i].end; //右頂點K[count_k].weight = E[i].weight; //中間邊權printf("%c -- %d --%c\t", K[count_k].begin, K[count_k].weight, K[count_k].end);count_k++;}}
}3、代碼
//克魯斯卡爾(Kruskal)算法
//測試案例：
/*ABCDEFG
12
12 AB
14 AG
16 AF
7 BF
9 FG
10 BC
8 EG
6 CF
2 EF
5 CE
3 CD
4 DE*/#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>#define MAXSIZE 20
#define MAX 65535
int length_v = 0; //頂點個數
int length_e = 0; //邊個數
int circle[MAXSIZE] = { -1 }; //判斷是否連通（里面的元素定位vertex[ ]中的元素）
int count_k; //計數克魯斯卡爾頂點//圖的頂點
char vertex[MAXSIZE];//圖的邊（以邊為主體，裝入兩端頂點及權）
typedef struct Edge
{int begin;int end;int weight;
}Edge;
Edge E[MAXSIZE]; //邊數組
Edge K[MAXSIZE]; //Kruskal數組//輸入頂點
void InputVertex()
{int i;char ch;printf("請輸入圖的全部頂點(換行結束)：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){vertex[i] = ch;scanf("%c", &ch);}length_v = i;
}//創建圖
void CreateGraph()
{int weight = 0;char ch;printf("請輸入邊的數量：\n");scanf("%d", &length_e);printf("請分別輸入邊的權重和左右頂點：\n");for (int i = 0; i < length_e; i++) //每一條邊{printf("第%d條邊：\t", i + 1);scanf("%d", &weight); //權重while (weight == 32 && weight == 13) //空格判斷（32為空格的ASCII碼，13為回車的ASCII碼）scanf("%d", &weight);E[i].weight = weight;scanf("%c", &ch); //第一個頂點while (ch == ' ')scanf("%c", &ch);E[i].begin = ch;scanf("%c", &ch); //第一個頂點while (ch == ' ')scanf("%c", &ch);E[i].end = ch;}
}//排序（按照邊的權重，從低到高）
void Sort()
{int i, j, min;Edge temp;for (i = 0; i < length_e; i++){min = i;for (j = i; j < length_e; j++){if (E[min].weight > E[j].weight)min = j;}if (min != i){temp = E[min];E[min] = E[i];E[i] = temp;}}
}//根據頂點查找下標
int FindIndex(char ch)
{for (int i = 0; i < length_v; i++){if (ch == vertex[i])return i;}return -1;
}//根據頂點查找到尾（下標追溯）
int FindTail(char ch)
{int index = FindIndex(ch);while (circle[index] != -1){index = circle[index]; //追溯到尾（下標追溯）}return index; //返回尾（沒有連接頂點的話返回自身）
}//循環數組初始化
void Circle_Init()
{for (int i = 0; i < length_v; i++){circle[i] = -1;}
}//克魯斯卡爾(Kruskal)算法
//難點：是否連通判斷：需要追溯到尾，如果連通的話它們有共同的尾
void Kruskal()
{int i, now = 0, tail = 0; //檢測連通（頭和尾）for (i = 0; i < length_e; i++) //遍歷每條邊{tail = FindTail(E[i].begin); //獲取下標并追溯到尾（無連通則返回自身）now = FindTail(E[i].end); //獲取下標并追溯到尾//未連通，正常添加if (tail != now){circle[tail] = now; //尾連通（標識連通）K[count_k].begin = E[i].begin; //左頂點K[count_k].end = E[i].end; //右頂點K[count_k].weight = E[i].weight; //中間邊權printf("%c -- %d --%c\t", K[count_k].begin, K[count_k].weight, K[count_k].end);count_k++;}}
}//逐邊遍歷（測試輸出）
void Traverse_Edge()
{int i;for (i = 0; i < length_e; i++){printf("\n第%d條邊：\t 權重：%d\t 頂點1：%c\t 頂點2：%c\t ", i + 1, E[i].weight, E[i].begin, E[i].end);}
}int main()
{InputVertex(); //輸入頂點CreateGraph(); //創建圖Sort(); //排序Circle_Init(); //循環數組初始化printf("克魯斯卡爾算法計算最小生成樹：\n");Kruskal(); //克魯斯卡爾(Kruskal)算法//Traverse_Edge(); //逐邊遍歷（測試輸出）return 0;
}參考資料
https://blog.csdn.net/guozhangjie1992/article/details/106821932?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162833230916780261971711%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=162833230916780261971711&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~rank_v29-2-106821932.pc_search_result_control_group&utm_term=%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%E8%BF%9E%E9%80%9A%E5%88%A4%E6%96%AD&spm=1018.2226.3001.4187?
https://www.bilibili.com/video/BV1jW411K7yg?p=64
總結
以上是生活随笔為你收集整理的数据结构与算法（7-3）最小生成树（普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： OpenCV（二）逐像素的图像复制、图像
- 下一篇： OpenCV（五）绘制图形与文本