【數(shù)據(jù)結(jié)構(gòu)】最小生成樹之普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法

最小生成樹

列子引入


如圖假設(shè)v0到v8表示9個村莊，現(xiàn)在需要在這9個村莊假設(shè)通信網(wǎng)絡(luò)。村莊之間的數(shù)字代表村莊之間的直線距離，求用最小成本完成這9個村莊的通信網(wǎng)絡(luò)建設(shè)。

分析

  • 這幅圖只一個帶權(quán)值的圖，即網(wǎng)結(jié)構(gòu)。
  • 所謂最小成本，就是n個頂點，用n-1條邊把一個連通圖連接起來，并且使權(quán)值的和最小。

最小生成樹

如果無向連通圖是一個網(wǎng)圖，那么它的所有生成樹中必有一顆是邊的權(quán)值總和最小的生成樹，即最小生成樹。
找到連通圖的最小生成樹，有兩種經(jīng)典的算法：普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法

一、普里姆(Prim)算法

圖的鄰接矩陣

普利姆算法步驟

  • 從圖中某一個頂點出發(fā)(這里選V0)，尋找它相連的所有結(jié)點，比較這些結(jié)點的權(quán)值大小，然后連接權(quán)值最小的那個結(jié)點。（這里是V1）
  • 然后將尋找這兩個結(jié)點相連的所有結(jié)點，找到權(quán)值最小的連接。（這里是V5）.

  • 重復(fù)上一步，知道所有結(jié)點都連接上。


    最小生成樹

實現(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->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;
    
    // 利用鄰接矩陣的對稱性
    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)頂點的下標(biāo)
    int lowcost[MAXVEX]; // 保存相關(guān)頂點間邊的權(quán)值
    
    lowcost[0] = 0;  // 初始化第一個權(quán)值為0，即v0加入生成樹
    adjvex[0] = 0; // 初始化第一個頂點下標(biāo)為0
    
    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)
    }
    
    for (i = 1; i < G.numVertexes; i++) {
        
        min = INIFINTY; //初始化最小權(quán)值
        j = 1;
        k = 0;
        
        while (j < G.numVertexes) { // 循環(huá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)前頂點中權(quán)值最小的邊
        lowcost[k] = 0;             // 將當(dāng)前頂點的權(quán)值設(shè)置為0，表示此頂點已經(jīng)完成任務(wù)
        
        for (j = 1; j < G.numVertexes; j++) {  // 循環(huán)所有頂點
            if (lowcost[j]!= 0 && G.arc[k][j] < lowcost[j]) {  // 如果下標(biāo)為k頂點各邊權(quán)值小于當(dāng)前這些頂點未被加入生成樹權(quán)值
                lowcost[j] = G.arc[k][j]; // 將較小的權(quán)值存入lowcost相應(yīng)的位置
                adjvex[j] = k;   // 將下標(biāo)為k的頂點存入adjvex
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    
    MGraph G;
    CreateMGraph(&G);
    MiniSpanTree_Prim(G);
    
    return 0;
}

代碼解釋

  • 創(chuàng)建了兩個數(shù)組adjvex和lowcost。adjvex[0] = 0意思就是從V0開始，lowcost[0] = 0表示V0已經(jīng)被納入到最小生成樹中。之后凡是lowcost數(shù)組中的值被設(shè)置為0就是表示此下標(biāo)的頂點被納入最小生成樹。
  • 普里姆算法的時間復(fù)雜度為O(n^2)，因為是兩層循環(huán)嵌套。

代碼運行結(jié)果

普里姆算法運行結(jié)果

二、克魯斯卡爾(Kruskal)算法

普里姆算法是從某一頂點為起點，逐步找各個頂點最小權(quán)值的邊來構(gòu)成最小生成樹。那我們也可以直接從邊出發(fā)，尋找權(quán)值最小的邊來構(gòu)建最小生成樹。不過在構(gòu)建的過程中要考慮是否會形成環(huán)的情況

邊集數(shù)組存儲圖

邊集數(shù)組

在直接用邊來構(gòu)建最小生成樹的時候，需要用到邊集數(shù)組結(jié)構(gòu)，代碼為：

typedef struct {  // 邊集數(shù)組
    int begin;
    int end;
    int weight;
}Edge;

代碼實現(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->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;
    
    // 利用鄰接矩陣的對稱性
    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;
}

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

/**
 * 查找連線頂點的尾部下標(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ù)組，并排序，所以前面有對權(quán)值進(jìn)行排序的方法sort。
  • 克魯斯卡爾(Kruskal)算法的時間復(fù)雜度為O(eloge)。

運行結(jié)果

對比普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法

  • 克魯斯卡爾(Kruskal)算法主要針對邊來展開，邊數(shù)較少時效率非常高，所以對于稀疏圖有很大的優(yōu)勢；
  • 普里姆(Prim)算法對于稠密圖，邊數(shù)非常多的情況更好一些。
最后編輯于 ：
?著作權(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ù)。

相關(guān)閱讀更多精彩內(nèi)容

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