數(shù)據(jù)結(jié)構(gòu)與算法-最小生成樹Prim算法&Kruskal算法

生成樹

對連通圖進(jìn)行遍歷，過程中所經(jīng)過的邊和頂點的組合可看做是一棵普通樹，通常稱為生成樹。

    1. 圖是連通圖;
    1. 圖中包含了了N個頂點;
    1. 圖中邊的數(shù)量量等于N-1條邊.

最小生成樹

把構(gòu)成連通網(wǎng)的最小代價的生成樹稱為最小生成樹

普里姆(Prim)算法

從所有可選結(jié)中再選擇權(quán)值最小的結(jié)點，并將其加入已選節(jié)點；重復(fù)操作，直到所有節(jié)點被選擇完畢。

算法思路
1\. 定義2個數(shù)組; adjvex 用來保存相關(guān)頂點下標(biāo); lowcost 保存頂點之間的權(quán)值
2\. 初始化2個數(shù)組, 從v0開始尋找最小生成樹, 默認(rèn)v0是最小生成樹上第一個頂點 
3\. 循環(huán)lowcost 數(shù)組,根據(jù)權(quán)值,找到頂點 k;
4\. 更新lowcost 數(shù)組
5\. 循環(huán)所有頂點,找到與頂點k 有關(guān)系的頂點. 并更更新lowcost 數(shù)組與adjvex 數(shù)組;

注意: 更新lowcost 數(shù)組與adjvex 數(shù)組的條件:
    1\. 與頂點k 之間有連接
    2\. 當(dāng)前結(jié)點 j 沒有加入過最?生成樹;
    3\. 頂點 k 與 當(dāng)前頂點 j 之間的權(quán)值 小于 頂點j 與其他頂點 k 之前的權(quán)值. 則更新. 簡單說就是比之前存儲的值小,則更新;
算法實現(xiàn)
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#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ù)和頂點數(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)頂點下標(biāo) */
    int adjvex[MAXVEX];
    /* 保存相關(guān)頂點間邊的權(quán)值 */
    int lowcost[MAXVEX];

    /* 初始化第一個權(quán)值為0，即v0加入生成樹 */
    /* lowcost的值為0，在這里就是此下標(biāo)的頂點已經(jīng)加入生成樹 */
    lowcost[0] = 0;

    /* 初始化第一個頂點下標(biāo)為0 */
    adjvex[0] = 0;

    //1\. 初始化
    for(i = 1; i < G.numVertexes; i++)    /* 循環(huán)除下標(biāo)為0外的全部頂點 */
    {
        lowcost[i] = G.arc[0][i];    /* 將v0頂點與之有邊的權(quán)值存入數(shù)組 */
        adjvex[i] = 0;                    /* 初始化都為v0的下標(biāo) */
    }

    //2\. 循環(huán)除了下標(biāo)為0以外的全部頂點, 找到lowcost數(shù)組中最小的頂點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)全部頂點 */
        {
            /* 如果權(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)前頂點邊中權(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)前頂點的權(quán)值設(shè)置為0,表示此頂點已經(jīng)完成任務(wù) */
        lowcost[k] = 0;

        /* 循環(huán)所有頂點,找到與頂點k 相連接的頂點
         1\. 與頂點k 之間連接;
         2\. 該結(jié)點沒有被加入到生成樹;
         3\. 頂點k 與 頂點j 之間的權(quán)值 < 頂點j 與其他頂點的權(quán)值,則更新lowcost 數(shù)組;

         */
        for(j = 1; j < G.numVertexes; j++)
        {
            /* 如果下標(biāo)為k頂點各邊權(quá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的頂點存入adjvex */
                adjvex[j] = k;
            }
        }
    }
    printf("sum = %d\n",sum);
}

int main(void)
{
    printf("Hello,最小生成樹_Prim算法\n");

    MGraph G;
    CreateMGraph(&G);
    MiniSpanTree_Prim(G);

    return 0;

}

克魯斯卡爾(Kruskal)算法

思路
1\. 將鄰接矩陣 轉(zhuǎn)化成 邊表數(shù)組;
2\. 對邊表數(shù)組根據(jù)權(quán)值按照從小到大的順序排序;
3\. 遍歷所有的邊, 通過parent 數(shù)組找到邊的連接信息; 避免閉環(huán)問題; 
4\. 如果不存在閉環(huán)問題,則加入到最小生成樹中. 并且修改parent 數(shù)組
代碼實現(xiàn)
#include "stdio.h"
#include "stdlib.h"

#include "math.h"
#include "time.h"

#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ù)和頂點數(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);
    }

}

/* 查找連線頂點的尾部下標(biāo) */
//根據(jù)頂點f以及parent 數(shù)組,可以找到當(dāng)前頂點的尾部下標(biāo); 幫助我們判斷2點之間是否存在閉環(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)路
     用來記錄頂點間的連接關(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個頂點;
    // 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é)尾頂點放入下標(biāo)為起點的parent中。 */
            /* 表示此頂點已經(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);
}

int main(int argc, const char * argv[]) {

    printf("Hello,最小生成樹_Kruskal算法\n");
    MGraph G;
    CreateMGraph(&G);
    MiniSpanTree_Kruskal(G);
    return 0;
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容