連通圖的?生成樹定義: 所謂?一個連通圖的?生成樹是?一個極?小的連通?子圖,它含有圖中全部的n個頂點(diǎn),但只?足以構(gòu)成?一顆樹的n-1條邊.
定義解讀: 滿?足以下3個條件則為連通圖的?生成樹:
- 圖是連通圖;
- 圖中包含了了N個頂點(diǎn);
- 圖中邊的數(shù)量量等于N-1條邊.
今天學(xué)習(xí)最小生成樹的兩種算法：普里姆【Prim】算法和克魯斯卡爾【Kruskal】算法
一宦芦、Prim算法
算法思路：
- 定義2個數(shù)組; adjvex ?用來保存相關(guān)頂點(diǎn)下標(biāo); lowcost 保存頂點(diǎn)之間的權(quán)值
- 初始化2個數(shù)組, 從v0開始尋找最?小?生成樹, 默認(rèn)v0是最?小?生成樹上第?一個頂點(diǎn)
- 循環(huán)lowcost 數(shù)組,根據(jù)權(quán)值,找到頂點(diǎn) k;
- 更更新lowcost 數(shù)組
- 循環(huán)所有頂點(diǎn),找到與頂點(diǎn)k 有關(guān)系的頂點(diǎn). 并更更新lowcost 數(shù)組與adjvex 數(shù)組
代碼實(shí)現(xiàn)：
- 循環(huán)所有頂點(diǎn),找到與頂點(diǎn)k 有關(guān)系的頂點(diǎn). 并更更新lowcost 數(shù)組與adjvex 數(shù)組
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status; /* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/*9.1 創(chuàng)建鄰接矩陣*/
void CreateMGraph(MGraph *G)/* 構(gòu)件圖 */
{
int i, j;
/* printf("請輸入邊數(shù)和頂點(diǎn)數(shù):"); */
G->numEdges=15;
G->numVertexes=9;
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] = INFINITYC;
}
}
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][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* Prim算法生成最小生成樹 */
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int sum = 0;
/* 保存相關(guān)頂點(diǎn)下標(biāo) */
int adjvex[MAXVEX];
/* 保存相關(guān)頂點(diǎn)間邊的權(quán)值 */
int lowcost[MAXVEX];
/* 初始化第一個權(quán)值為0轴脐，即v0加入生成樹 */
/* lowcost的值為0抡砂，在這里就是此下標(biāo)的頂點(diǎn)已經(jīng)加入生成樹 */
lowcost[0] = 0;
/* 初始化第一個頂點(diǎn)下標(biāo)為0 */
adjvex[0] = 0;
//1. 初始化
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) */
}
//2. 循環(huán)除了下標(biāo)為0以外的全部頂點(diǎn), 找到lowcost數(shù)組中最小的頂點(diǎn)k
for(i = 1; i < G.numVertexes; i++)
{
/* 初始化最小權(quán)值為∞， */
/* 通常設(shè)置為不可能的大數(shù)字如32767恬涧、65535等 */
min = INFINITYC;
j = 1;k = 0;
while(j < G.numVertexes) /* 循環(huán)全部頂點(diǎn) */
{
/* 如果權(quán)值不為0且權(quán)值小于min */
if(lowcost[j]!=0 && lowcost[j] < min)
{
/* 則讓當(dāng)前權(quán)值成為最小值,更新min */
min = lowcost[j];
/* 將當(dāng)前最小值的下標(biāo)存入k */
k = j;
}
j++;
}
/* 打印當(dāng)前頂點(diǎn)邊中權(quán)值最小的邊 */
printf("(V%d, V%d)=%d\n", adjvex[k], k ,G.arc[adjvex[k]][k]);
sum+=G.arc[adjvex[k]][k];
/* 3.將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0,表示此頂點(diǎn)已經(jīng)完成任務(wù) */
lowcost[k] = 0;
/* 循環(huán)所有頂點(diǎn),找到與頂點(diǎn)k 相連接的頂點(diǎn)
1. 與頂點(diǎn)k 之間連接;
2. 該結(jié)點(diǎn)沒有被加入到生成樹;
3. 頂點(diǎn)k 與 頂點(diǎn)j 之間的權(quán)值 < 頂點(diǎn)j 與其他頂點(diǎn)的權(quán)值,則更新lowcost 數(shù)組;
*/
for(j = 1; j < G.numVertexes; j++)
{
/* 如果下標(biāo)為k頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)未被加入生成樹權(quán)值 */
if(lowcost[j]!=0 && G.arc[k][j] < lowcost[j])
{
/* 將較小的權(quán)值存入lowcost相應(yīng)位置 */
lowcost[j] = G.arc[k][j];
/* 將下標(biāo)為k的頂點(diǎn)存入adjvex */
adjvex[j] = k;
}
}
}
printf("sum = %d\n",sum);
}
二注益、Kruskal算法
算法思路：
- 將鄰接矩陣 轉(zhuǎn)化成 邊表數(shù)組;
- 對邊表數(shù)組根據(jù)權(quán)值按照從?小到?大的順序排序;
- 遍歷所有的邊, 通過parent 數(shù)組找到邊的連接信息; 避免閉環(huán)問題;
- 如果不不存在閉環(huán)問題,則加?入到最?小?生成樹中. 并且修改parent 數(shù)組;
代碼實(shí)現(xiàn)：
- 如果不不存在閉環(huán)問題,則加?入到最?小?生成樹中. 并且修改parent 數(shù)組;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITYC 65535
typedef int Status;
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/* 對邊集數(shù)組Edge結(jié)構(gòu)的定義 */
typedef struct
{
int begin;
int end;
int weight;
}Edge ;
/*9.1 創(chuàng)建鄰接矩陣*/
void CreateMGraph(MGraph *G)
{
int i, j;
/* printf("請輸入邊數(shù)和頂點(diǎn)數(shù):"); */
G->numEdges=15;
G->numVertexes=9;
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] = INFINITYC;
}
}
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][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
/* 交換權(quán)值以及頭和尾 */
void Swapn(Edge *edges,int i, int j)
{
int tempValue;
//交換edges[i].begin 和 edges[j].begin 的值
tempValue = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = tempValue;
//交換edges[i].end 和 edges[j].end 的值
tempValue = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = tempValue;
//交換edges[i].weight 和 edges[j].weight 的值
tempValue = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = tempValue;
}
/* 對權(quán)值進(jìn)行排序 */
void sort(Edge edges[],MGraph *G)
{
//對權(quán)值進(jìn)行排序(從小到大)
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("邊集數(shù)組根據(jù)權(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) */
//根據(jù)頂點(diǎn)f以及parent 數(shù)組,可以找到當(dāng)前頂點(diǎn)的尾部下標(biāo); 幫助我們判斷2點(diǎn)之間是否存在閉環(huán)問題;
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 sum = 0;
int k = 0;
/* 定義一數(shù)組用來判斷邊與邊是否形成環(huán)路
用來記錄頂點(diǎn)間的連接關(guān)系. 通過它來防止最小生成樹產(chǎn)生閉環(huán);*/
int parent[MAXVEX];
/* 定義邊集數(shù)組,edge的結(jié)構(gòu)為begin,end,weight,均為整型 */
Edge edges[MAXEDGE];
/*1. 用來構(gòu)建邊集數(shù)組*/
for ( i = 0; i < G.numVertexes-1; i++)
{
for (j = i + 1; j < G.numVertexes; j++)
{
//如果當(dāng)前路徑權(quán)值 != ∞
if (G.arc[i][j]<INFINITYC)
{
//將路徑對應(yīng)的begin,end,weight 存儲到edges 邊集數(shù)組中.
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
//邊集數(shù)組計算器k++;
k++;
}
}
}
//2. 對邊集數(shù)組排序
sort(edges, &G);
//3.初始化parent 數(shù)組為0. 9個頂點(diǎn);
// for (i = 0; i < G.numVertexes; i++)
for (i = 0; i < MAXVEX; i++)
parent[i] = 0;
//4. 計算最小生成樹
printf("打印最小生成樹：\n");
/* 循環(huán)每一條邊 G.numEdges 有15條邊*/
for (i = 0; i < G.numEdges; i++)
{
//獲取begin,end 在parent 數(shù)組中的信息;
//如果n = m ,將begin 和 end 連接,就會產(chǎn)生閉合的環(huán).
n = Find(parent,edges[i].begin);
m = Find(parent,edges[i].end);
//printf("n = %d,m = %d\n",n,m);
/* 假如n與m不等，說明此邊沒有與現(xiàn)有的生成樹形成環(huán)路 */
if (n != m)
{
/* 將此邊的結(jié)尾頂點(diǎn)放入下標(biāo)為起點(diǎn)的parent中溯捆。 */
/* 表示此頂點(diǎn)已經(jīng)在生成樹集合中 */
parent[n] = m;
/*打印最小生成樹路徑*/
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
sum += edges[i].weight;
}
}
printf("sum = %d\n",sum);
}
