把構(gòu)成連通?的最?代價(jià)的?成樹(shù)稱(chēng)為最??成樹(shù)。
連通圖：在無(wú)向圖中，若任意兩個(gè)頂點(diǎn)vi和vj之間都有路徑想通，則稱(chēng)該無(wú)向圖為連通圖。
連通圖的生成樹(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ú)向圖G=(V,E)中，(u,v)代表連接頂點(diǎn)u與頂點(diǎn)v的邊，而w(u,v)代表邊的權(quán)重，若存在T為E的子集且為無(wú)循環(huán)圖，使得W(T)最小，則此T為G的最小生成樹(shù)。把構(gòu)成連通網(wǎng)的最?代價(jià)的生成樹(shù)稱(chēng)為最?生成樹(shù)Minimum Spanning Tree,MST。

最小生成樹(shù)性質(zhì)：設(shè)G=(V，E)是一個(gè)連通網(wǎng)絡(luò)，T1是頂點(diǎn)集V的一個(gè)非空真子集，T2是頂點(diǎn)集V-T1后剩余的子集。若(u，v)是G中一條一個(gè)端點(diǎn)在T1中（例如：u∈T1)，另一個(gè)端點(diǎn)在T2中的邊（例如：v∈T2），且（u，v)具有最小權(quán)值，則一定存在G的最小生成樹(shù)包括此邊(u，v)。

我們先把圖轉(zhuǎn)換成鄰接矩陣，(https://juejin.im/post/5eae34e951882560d56d6588)

image

利用兩個(gè)數(shù)組來(lái)輔助我們記錄遍歷頂點(diǎn)過(guò)程中的數(shù)據(jù)，兩個(gè)數(shù)組lowcost和arjvex，

• lowcost用于記錄當(dāng)前頂點(diǎn)與所有與它關(guān)聯(lián)頂點(diǎn)間的權(quán)重值。下標(biāo)：頂點(diǎn)下標(biāo)，值：與當(dāng)前頂點(diǎn)的權(quán)重。
• arjvex用于記錄當(dāng)前頂點(diǎn)與哪個(gè)頂點(diǎn)相連接。下標(biāo)：當(dāng)前頂點(diǎn)下標(biāo)，值：與當(dāng)前頂點(diǎn)相連的前一個(gè)頂點(diǎn)。

1. 第一次執(zhí)行
   image

   <figcaption></figcaption>

2. 第二次執(zhí)行
   image

   <figcaption></figcaption>

3. 第三次執(zhí)行
   image

   <figcaption></figcaption>

4. 第四次執(zhí)行
   image

   <figcaption></figcaption>

5. 第五次執(zhí)行
   image

Prim算法
思路

定義兩個(gè)數(shù)組lowcost和adjvex。其中：

lowcost保存相關(guān)頂點(diǎn)間邊的權(quán)值，lowcost[i]=0代表頂點(diǎn)vi已經(jīng)加入了最小生成子樹(shù)中，lowcost[i]=INFINITYC表示i對(duì)應(yīng)的頂點(diǎn)與當(dāng)前的最小生成樹(shù)中的頂點(diǎn)暫時(shí)不連通，在0<lowcost[i]<INFINITYC的情況中會(huì)生成一個(gè)與當(dāng)前最小生成子樹(shù)的各個(gè)頂點(diǎn)之間權(quán)值最小的頂點(diǎn)加入到最小生成子樹(shù)當(dāng)中。
adjvex保存相關(guān)頂點(diǎn)下標(biāo) adjvex[i]默認(rèn)=-1.表示i對(duì)應(yīng)的結(jié)點(diǎn)和最小生成子樹(shù)暫時(shí)不連通，adjvex[i] >-1 表示i對(duì)應(yīng)的結(jié)點(diǎn)和最小生成樹(shù)相連的頂點(diǎn)為adjvex[i]

初始化上述數(shù)組，默認(rèn)將v0加入到最小子樹(shù)中，并更新數(shù)組中對(duì)應(yīng)的值
以v0為最小子樹(shù)，尋找剩余頂點(diǎn)中與v0路徑最短的頂點(diǎn)加入v0當(dāng)中，組成新的最小子樹(shù)，并更新兩個(gè)數(shù)組的值。
以新的最小子樹(shù)開(kāi)始，重復(fù)步驟3，直到找到最后一個(gè)頂點(diǎn)。

void MiniSpanTree_Prim_1(MGraph G) {
    int lowcost[MAXVEX];
    int adjvex[MAXVEX];
    
    //初始化兩個(gè)數(shù)組，即默認(rèn)將v0放入最小生成子樹(shù)中
    adjvex[0] = 0;
    lowcost[0] = 0;
    int I;
    //將v0對(duì)應(yīng)的連通頂點(diǎn)信息存入adjvex，將連通頂點(diǎn)的權(quán)值存入lowcost
    for(i = 1; i < G.numVertexes; i++) {
        if(G.arc[0][i] < INFINITYC) {
            adjvex[i] = 0;
        }else {
            adjvex[i] = -1;
        }
        lowcost[i] = G.arc[0][I];
    }
    
    int k = 0;
    int j = 0;
    int sum = 0;
    for(i = 1; i < G.numVertexes; i++) {
        int min = INFINITYC;
        //第一次遍歷找到lowcost中除去0以外最小的頂點(diǎn)，作為下一個(gè)頂點(diǎn)加入最小生成樹(shù)
        for(j = 1; j < G.numVertexes; j++) {
            if(lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
//        printf("lowcost為：\n");
//        for(int temp = 0; temp < G.numVertexes; temp++) {
//            printf("%d ",lowcost[temp]);
//        }
//        printf("\n");
//        printf("adjvex為：\n");
//        for(int temp = 0; temp < G.numVertexes; temp++) {
//            printf("%d ",adjvex[temp]);
//        }
//        printf("\n");
        
        /* 打印當(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];
        lowcost[k] = 0;
        //將與新加入頂點(diǎn)連通的其他頂點(diǎn)加入lowcost中并更新對(duì)應(yīng)的lowcost以及adjvex的值
        for(j = 0; j < G.numVertexes; j++) {
            if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n",sum);
}

克魯斯卡爾算法
思路：

T是邊的集合，初始狀態(tài)為空
將圖中的所有邊以權(quán)值從小到大的順序進(jìn)行排序，預(yù)定排序后邊的起點(diǎn)永遠(yuǎn)為比較小的頂點(diǎn)
取出權(quán)值最小的邊，查看它與T中的邊是否造成環(huán)路，
如果未構(gòu)成環(huán)路，則加入T中；否則，拋棄改邊
如果還有剩余邊，則返回3中，否則程序結(jié)束

證明：
分兩步來(lái)證明Kruskal算法得到的是最小生成樹(shù)

Kruskal得到的是一棵生成樹(shù)
Kruskal得到的生成樹(shù)代價(jià)最小

假設(shè)改算法得到的不是生成樹(shù)，那么有兩種情況，第一種是得到的圖是有環(huán)的，第二種情況是得到的圖不連通。由于算法要求，每次加入的邊都不能形成環(huán)，因此第一種情形不存在。第二種情況，首先我們知道原圖是屬于連通圖，根據(jù)算法的要求，取出權(quán)值最小的邊，如果未構(gòu)成環(huán)路，則加入T中，因?yàn)樵瓐D是連通的，必然會(huì)存在可以連接所有頂點(diǎn)又不構(gòu)成環(huán)路的路徑，可以得到Kruskal得到的圖肯定也是連通圖，因此第二種情況也不存在。

接下來(lái)證明Kruskal得到的生成樹(shù)代價(jià)最小。假設(shè)圖有n個(gè)頂點(diǎn)，則生成樹(shù)一定有n-1條邊，最少存在一個(gè)最小生成樹(shù)U。假設(shè)：

Kruskal得到的生成樹(shù)為T(mén)。
U和T中不同的邊數(shù)為k，其他n-1-k條邊相同，相同的邊構(gòu)成集合E
在T中而不在U中的邊按代價(jià)從小到大一次為a1<a2<..<ak
在U中而不在T中的邊按代價(jià)從小到大一次為x1<x2<..<xk

我們通過(guò)把T中的邊依次移動(dòng)到U中來(lái)證明U和T是等價(jià)的。
首先將a1移動(dòng)到U中，由于U是一棵生成樹(shù)，加入一條新邊后會(huì)行程環(huán)路，且這條回路一定會(huì)包括x1,x2...,xk中的邊，否則a1和E中的邊形成環(huán)路，則T不是生成樹(shù)，產(chǎn)生矛盾。
在回路中刪除屬于x1,x2...,xk且代價(jià)最大的邊xi構(gòu)成一棵新的生成樹(shù)V。
假設(shè)a1<xi，則w(V)<w(U)，與最小生成樹(shù)定義矛盾。
假設(shè)a1>xi, 則xi小于a1,a2...,ak，根據(jù)Kruskal算法，在考慮最小邊的時(shí)候會(huì)優(yōu)先考慮xi，而且xi和E也不會(huì)構(gòu)成環(huán)路，但是T中并沒(méi)有xi，說(shuō)明a1也不會(huì)大于xi，即a1 = xi，新得到的w(V)=w(U)。
同理，我們將a2...，ak依次加入到U中，最終得到w(U)=w(T)。證明完畢。
判斷是否生成環(huán)路

171f3fbbb3f1eeb8.png

上圖中，邊(v0,v1)在一條環(huán)路中，我們分別從v0和v1開(kāi)始，因?yàn)槭黔h(huán)路，我們通過(guò)某種規(guī)則，最終會(huì)達(dá)到同樣的終點(diǎn)。
判斷環(huán)路需要一個(gè)輔助數(shù)組parent[]={0}，存儲(chǔ)新加入頂點(diǎn)的路徑關(guān)系，值為0代表沒(méi)有新加入的頂點(diǎn)

新增加一個(gè)邊的結(jié)構(gòu)體來(lái)保存每一條邊的信息
/* 對(duì)邊集數(shù)組Edge結(jié)構(gòu)的定義 */
typedef struct
{
    int begin;
    int end;
    int weight;
}Edge;

/* 查找連線頂點(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;
}

/* 交換權(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);
    }
    
}

/* 生成最小生成樹(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);
}