最小生成樹
列子引入
如圖假設(shè)
v0到v8表示9個(gè)村莊，現(xiàn)在需要在這9個(gè)村莊假設(shè)通信網(wǎng)絡(luò)。村莊之間的數(shù)字代表村莊之間的直線距離痹换，求用最小成本完成這9個(gè)村莊的通信網(wǎng)絡(luò)建設(shè)。
分析
- 這幅圖只一個(gè)帶權(quán)值的圖都弹，即網(wǎng)結(jié)構(gòu)娇豫。
- 所謂最小成本，就是
n個(gè)頂點(diǎn)畅厢，用n-1條邊把一個(gè)連通圖連接起來冯痢，并且使權(quán)值的和最小。
最小生成樹
如果無向連通圖是一個(gè)網(wǎng)圖框杜，那么它的所有生成樹中必有一顆是邊的權(quán)值總和最小的生成樹浦楣，即最小生成樹。
找到連通圖的最小生成樹咪辱，有兩種經(jīng)典的算法：普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法
一振劳、普里姆(Prim)算法
圖的鄰接矩陣
普利姆算法步驟
- 從圖中某一個(gè)頂點(diǎn)出發(fā)(這里選
V0)，尋找它相連的所有結(jié)點(diǎn)油狂，比較這些結(jié)點(diǎn)的權(quán)值大小历恐，然后連接權(quán)值最小的那個(gè)結(jié)點(diǎn)。（這里是V1） - 然后將尋找這兩個(gè)結(jié)點(diǎn)相連的所有結(jié)點(diǎn)专筷，找到權(quán)值最小的連接弱贼。（這里是
V5）. -
重復(fù)上一步，知道所有結(jié)點(diǎn)都連接上仁堪。
最小生成樹
實(shí)現(xiàn)代碼
#include <stdio.h>
#include <stdlib.h>
#define MAXEDGE 20
#define MAXVEX 20
#define INIFINTY 65535
typedef struct {
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/**
* 構(gòu)建圖
*/
void CreateMGraph(MGraph * G){
int i, j;
G->numVertexes = 9; // 9個(gè)頂點(diǎn)
G->numEdges = 15; // 15條邊
for (i = 0; i < G->numVertexes; i++) { // 初始化圖
for (j = 0; j < G->numVertexes; j++) {
if (i == j)
G->arc[i][j] = 0;
else
G->arc[i][j] = G->arc[j][i] = INIFINTY;
}
}
G->arc[0][1] = 10;
G->arc[0][5] = 11;
G->arc[1][2] = 18;
G->arc[1][8] = 12;
G->arc[1][6] = 16;
G->arc[2][3] = 22;
G->arc[2][8] = 8;
G->arc[3][4] = 20;
G->arc[3][7] = 16;
G->arc[3][6] = 24;
G->arc[3][8] = 21;
G->arc[4][5] = 26;
G->arc[4][7] = 7;
G->arc[5][6] = 17;
G->arc[6][7] = 19;
// 利用鄰接矩陣的對(duì)稱性
for (i = 0; i < G->numVertexes; i++)
for (j = 0; j < G->numVertexes; j++)
G->arc[j][i] = G->arc[i][j];
}
/**
* Prime算法生成最小生成樹
*/
void MiniSpanTree_Prim(MGraph G){
int min,i,j,k;
int adjvex[MAXVEX]; // 保存相關(guān)頂點(diǎn)的下標(biāo)
int lowcost[MAXVEX]; // 保存相關(guān)頂點(diǎn)間邊的權(quán)值
lowcost[0] = 0; // 初始化第一個(gè)權(quán)值為0，即v0加入生成樹
adjvex[0] = 0; // 初始化第一個(gè)頂點(diǎn)下標(biāo)為0
for (i = 1; i < G.numVertexes; i++) { // 循環(huán)除下標(biāo)為0外的全部頂點(diǎn)
lowcost[i] = G.arc[0][i]; // 將v0頂點(diǎn)與之右邊的權(quán)值存入數(shù)組
adjvex[i] = 0; // 初始化都為v0的下標(biāo)
}
for (i = 1; i < G.numVertexes; i++) {
min = INIFINTY; //初始化最小權(quán)值
j = 1;
k = 0;
while (j < G.numVertexes) { // 循環(huán)全部頂點(diǎn)
if (lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j]; // 讓當(dāng)前權(quán)值變?yōu)樽钚≈? k = j; // 將當(dāng)前最小值的下標(biāo)存入k
}
j++;
}
printf("(%d, %d)\n", adjvex[k], k); // 打印當(dāng)前頂點(diǎn)中權(quán)值最小的邊
lowcost[k] = 0; // 將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0填渠，表示此頂點(diǎn)已經(jīng)完成任務(wù)
for (j = 1; j < G.numVertexes; j++) { // 循環(huán)所有頂點(diǎn)
if (lowcost[j]!= 0 && G.arc[k][j] < lowcost[j]) { // 如果下標(biāo)為k頂點(diǎn)各邊權(quán)值小于當(dāng)前這些頂點(diǎn)未被加入生成樹權(quán)值
lowcost[j] = G.arc[k][j]; // 將較小的權(quán)值存入lowcost相應(yīng)的位置
adjvex[j] = k; // 將下標(biāo)為k的頂點(diǎn)存入adjvex
}
}
}
}
int main(int argc, const char * argv[]) {
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Prim(G);
return 0;
}
代碼解釋
- 創(chuàng)建了兩個(gè)數(shù)組
adjvex和lowcost弦聂。adjvex[0] = 0意思就是從V0開始鸟辅，lowcost[0] = 0表示V0已經(jīng)被納入到最小生成樹中。之后凡是lowcost數(shù)組中的值被設(shè)置為0就是表示此下標(biāo)的頂點(diǎn)被納入最小生成樹莺葫。 - 普里姆算法的時(shí)間復(fù)雜度為
O(n^2)匪凉，因?yàn)槭莾蓪友h(huán)嵌套。
代碼運(yùn)行結(jié)果
普里姆算法運(yùn)行結(jié)果
二捺檬、克魯斯卡爾(Kruskal)算法
普里姆算法是從某一頂點(diǎn)為起點(diǎn)再层，逐步找各個(gè)頂點(diǎn)最小權(quán)值的邊來構(gòu)成最小生成樹。那我們也可以直接從邊出發(fā)堡纬，尋找權(quán)值最小的邊來構(gòu)建最小生成樹聂受。不過在構(gòu)建的過程中要考慮是否會(huì)形成環(huán)的情況
邊集數(shù)組存儲(chǔ)圖
邊集數(shù)組
在直接用邊來構(gòu)建最小生成樹的時(shí)候，需要用到邊集數(shù)組結(jié)構(gòu)烤镐，代碼為：
typedef struct { // 邊集數(shù)組
int begin;
int end;
int weight;
}Edge;
代碼實(shí)現(xiàn)
#include <stdio.h>
#include <stdlib.h>
#define MAXEDGE 20
#define MAXVEX 20
#define INIFINTY 65535
typedef struct {
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef struct { // 邊集數(shù)組
int begin;
int end;
int weight;
}Edge;
/**
* 構(gòu)建圖
*/
void CreateMGraph(MGraph * G){
int i, j;
G->numVertexes = 9; // 9個(gè)頂點(diǎn)
G->numEdges = 15; // 15條邊
for (i = 0; i < G->numVertexes; i++) { // 初始化圖
for (j = 0; j < G->numVertexes; j++) {
if (i == j)
G->arc[i][j] = 0;
else
G->arc[i][j] = G->arc[j][i] = INIFINTY;
}
}
G->arc[0][1] = 10;
G->arc[0][5] = 11;
G->arc[1][2] = 18;
G->arc[1][8] = 12;
G->arc[1][6] = 16;
G->arc[2][3] = 22;
G->arc[2][8] = 8;
G->arc[3][4] = 20;
G->arc[3][7] = 16;
G->arc[3][6] = 24;
G->arc[3][8] = 21;
G->arc[4][5] = 26;
G->arc[4][7] = 7;
G->arc[5][6] = 17;
G->arc[6][7] = 19;
// 利用鄰接矩陣的對(duì)稱性
for (i = 0; i < G->numVertexes; i++)
for (j = 0; j < G->numVertexes; j++)
G->arc[j][i] = G->arc[i][j];
}
/**
* 交換權(quán)值蛋济、頭、尾
*/
void Swapn(Edge * edges, int i, int j){
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
/**
* 對(duì)權(quán)值進(jìn)行排序
*/
void sort(Edge edges[], MGraph *G){
int i,j;
for (i = 0; i < G->numEdges; i++) {
for (j = i+1; j < G->numEdges; j++) {
if (edges[i].weight > edges[j].weight)
Swapn(edges, i, j);
}
}
printf("權(quán)值排序之后為：\n");
for (i = 0; i < G->numEdges; i++) {
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
/**
* 查找連線頂點(diǎn)的尾部下標(biāo)
*/
int Find(int * parent, int f){
while (parent[f] > 0)
f = parent[f];
return f;
}
void MiniSpanTree_Kruskal(MGraph G){
int i,j,n,m;
int k = 0;
Edge edges[MAXEDGE]; // 定義邊集數(shù)組
int parent[MAXVEX]; // 定義一維數(shù)組來判斷邊與邊是否形成回路
//構(gòu)建邊集數(shù)組并排序
for (i = 0; i < G.numVertexes - 1; i++) {
for (j = i+1; j < G.numVertexes; j++) {
if (G.arc[i][j] < INIFINTY) {
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
k++;
}
}
}
sort(edges, &G);
for (i = 0; i < G.numVertexes; i++) {
parent[i] = 0;
}
printf("打印最小生成樹:\n");
for (i = 0; i < G.numEdges; i++) {
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m) {
parent[n] = m;
printf("(%d, %d) %d\n",edges[i].begin, edges[i].end
, edges[i].weight);
}
}
}
int main(int argc, const char * argv[]) {
MGraph G;
CreateMGraph(&G);
MiniSpanTree_Kruskal(G);
return 0;
}
代碼解釋
- 先構(gòu)建邊集數(shù)組炮叶，并排序碗旅，所以前面有對(duì)權(quán)值進(jìn)行排序的方法
sort。 - 克魯斯卡爾(Kruskal)算法的時(shí)間復(fù)雜度為
O(eloge)镜悉。
運(yùn)行結(jié)果
對(duì)比普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法
- 克魯斯卡爾(Kruskal)算法主要針對(duì)邊來展開祟辟，邊數(shù)較少時(shí)效率非常高，所以對(duì)于稀疏圖有很大的優(yōu)勢(shì)侣肄；
- 普里姆(Prim)算法對(duì)于稠密圖旧困，邊數(shù)非常多的情況更好一些。
