關(guān)于圖的幾個(gè)概念定義：
連通圖：在無(wú)向圖中，若任意兩個(gè)頂點(diǎn)vivi與vjvj都有路徑相通，則稱該無(wú)向圖為連通圖。
強(qiáng)連通圖：在有向圖中裁蚁，若任意兩個(gè)頂點(diǎn)vivi與vjvj都有路徑相通，則稱該有向圖為強(qiáng)連通圖继准。
連通網(wǎng)：在連通圖中枉证，若圖的邊具有一定的意義，每一條邊都對(duì)應(yīng)著一個(gè)數(shù)移必，稱為權(quán)室谚；權(quán)代表著連接連個(gè)頂點(diǎn)的代價(jià)，稱這種連通圖叫做連通網(wǎng)。
生成樹(shù)：一個(gè)連通圖的生成樹(shù)是指一個(gè)連通子圖舞萄，它含有圖中全部n個(gè)頂點(diǎn)眨补，但只有足以構(gòu)成一棵樹(shù)的n-1條邊。一顆有n個(gè)頂點(diǎn)的生成樹(shù)有且僅有n-1條邊倒脓，如果生成樹(shù)中再添加一條邊撑螺，則必定成環(huán)。
最小生成樹(shù)：在連通網(wǎng)的所有生成樹(shù)中崎弃，所有邊的代價(jià)和最小的生成樹(shù)甘晤，稱為最小生成樹(shù)。
1.png
1.Kruskal算法
此算法可以稱為“加邊法”饲做，初始最小生成樹(shù)邊數(shù)為0线婚，每迭代一次就選擇一條滿足條件的最小代價(jià)邊，加入到最小生成樹(shù)的邊集合里盆均。
- 把圖中的所有邊按代價(jià)從小到大排序塞弊；
- 把圖中的n個(gè)頂點(diǎn)看成獨(dú)立的n棵樹(shù)組成的森林；
- 按權(quán)值從小到大選擇邊泪姨，所選的邊連接的兩個(gè)頂點(diǎn)ui,viui,vi,應(yīng)屬于兩顆不同的樹(shù)游沿，則成為最小生成樹(shù)的一條邊，并將這兩顆樹(shù)合并作為一顆樹(shù)肮砾。
- 重復(fù)(3),直到所有頂點(diǎn)都在一顆樹(shù)內(nèi)或者有n-1條邊為止诀黍。
2.png
關(guān)鍵代碼
typedef int Status;
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/* 對(duì)邊集數(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("請(qǐng)輸入邊數(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;
}
/* 對(duì)權(quán)值進(jìn)行排序 */
void sort(Edge edges[],MGraph *G)
{
//對(duì)權(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)問(wèn)題;
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
/* 生成最小生成樹(shù) */
void MiniSpanTree_Kruskal(MGraph G)
{
int i, j, n, m;
int sum = 0;
int k = 0;
/* 定義一數(shù)組用來(lái)判斷邊與邊是否形成環(huán)路
用來(lái)記錄頂點(diǎn)間的連接關(guān)系. 通過(guò)它來(lái)防止最小生成樹(shù)產(chǎn)生閉環(huán);*/
int parent[MAXVEX];
/* 定義邊集數(shù)組,edge的結(jié)構(gòu)為begin,end,weight,均為整型 */
Edge edges[MAXEDGE];
/*1. 用來(lái)構(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)
{
//將路徑對(duì)應(yīng)的begin,end,weight 存儲(chǔ)到edges 邊集數(shù)組中.
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
//邊集數(shù)組計(jì)算器k++;
k++;
}
}
}
//2. 對(duì)邊集數(shù)組排序
sort(edges, &G);
//3.初始化parent 數(shù)組為0. 9個(gè)頂點(diǎn);
// for (i = 0; i < G.numVertexes; i++)
for (i = 0; i < MAXVEX; i++)
parent[i] = 0;
//4. 計(jì)算最小生成樹(shù)
printf("打印最小生成樹(shù)：\n");
/* 循環(huán)每一條邊 G.numEdges 有15條邊*/
for (i = 0; i < G.numEdges; i++)
{
//獲取begin,end 在parent 數(shù)組中的信息;
//如果n = m ,將begin 和 end 連接,就會(huì)產(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不等，說(shuō)明此邊沒(méi)有與現(xiàn)有的生成樹(shù)形成環(huán)路 */
if (n != m)
{
/* 將此邊的結(jié)尾頂點(diǎn)放入下標(biāo)為起點(diǎn)的parent中仗处。 */
/* 表示此頂點(diǎn)已經(jīng)在生成樹(shù)集合中 */
parent[n] = m;
/*打印最小生成樹(shù)路徑*/
printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
sum += edges[i].weight;
}
}
printf("sum = %d\n",sum);
}
2.Prim算法
此算法可以稱為“加點(diǎn)法”眯勾，每次迭代選擇代價(jià)最小的邊對(duì)應(yīng)的點(diǎn)，加入到最小生成樹(shù)中婆誓。算法從某一個(gè)頂點(diǎn)s開(kāi)始吃环，逐漸長(zhǎng)大覆蓋整個(gè)連通網(wǎng)的所有頂點(diǎn)。
圖的所有頂點(diǎn)集合為VV洋幻；初始令集合u={s},v=V?uu={s},v=V?u;
在兩個(gè)集合u,vu,v能夠組成的邊中郁轻，選擇一條代價(jià)最小的邊(u0,v0)(u0,v0)，加入到最小生成樹(shù)中鞋屈，并把v0v0并入到集合u中。
重復(fù)上述步驟故觅，直到最小生成樹(shù)有n-1條邊或者n個(gè)頂點(diǎn)為止厂庇。
由于不斷向集合u中加點(diǎn)，所以最小代價(jià)邊必須同步更新输吏；需要建立一個(gè)輔助數(shù)組closedge,用來(lái)維護(hù)集合v中每個(gè)頂點(diǎn)與集合u中最小代價(jià)邊信息权旷。
3.png
關(guān)鍵代碼
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
/*9.1 創(chuàng)建鄰接矩陣*/
void CreateMGraph(MGraph *G)/* 構(gòu)件圖 */
{
int i, j;
/* printf("請(qǐng)輸入邊數(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算法生成最小生成樹(shù) */
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];
/* 初始化第一個(gè)權(quán)值為0，即v0加入生成樹(shù) */
/* lowcost的值為0，在這里就是此下標(biāo)的頂點(diǎn)已經(jīng)加入生成樹(shù) */
lowcost[0] = 0;
/* 初始化第一個(gè)頂點(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)沒(méi)有被加入到生成樹(shù);
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)未被加入生成樹(shù)權(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);
}
