概念

連通圖的生成樹是一個(gè)極小的連通子圖，它含有圖中全部的n個(gè)頂點(diǎn)，但只有足以構(gòu)成一顆樹的n-1條邊。

構(gòu)造連通網(wǎng)的最小代價(jià)生成樹簡(jiǎn)稱為最小生成樹。

Prim 算法

算法思路

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

注意更新lowcost 數(shù)組與adjvex 數(shù)組的條件:

1. 與頂點(diǎn)k 之間有連接
2. 當(dāng)前結(jié)點(diǎn) j 沒有加入過最小生成樹;
3. 頂點(diǎn) k 與 當(dāng)前頂點(diǎn) j 之間的權(quán)值 小于 頂點(diǎn)j 與其他頂點(diǎn) k 之前的權(quán)值. 則更新. 簡(jiǎn)單說就是要比較之前存儲(chǔ)的值要小,則更新;

代碼實(shí)現(xiàn)

/*
 Prim算法生成最小生成樹
 */

void MiniSpanTree_Prim(MGraph G) {
    int min, i, j, k;
    int sum = 0;
    
    int adjvex[MAXVEX];
    int lowcost[MAXVEX];
    
    lowcost[0] = 0;
    adjvex[0] = 0;
    
    for (i = 1; i < G.numVertexes; i++) {
        lowcost[i] = G.arc[0][i];
        adjvex[i] = 0;
    }
    
    for (i = 1; i < G.numVertexes; i++) {
        min = INFINITYC;
        
        j = 1;
        k = 0;
        for (j = 1; j < G.numVertexes; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        
        printf("(V%d, V%d) = %d\n", adjvex[k], k , G.arc[adjvex[k]][k]);
        sum += G.arc[adjvex[k]][k];
        lowcost[k] = 0;
        
        for (j = 1; 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);
}

Kruskal 算法

算法思路

1. 將鄰接矩陣轉(zhuǎn)化成邊表數(shù)組；
2. 對(duì)邊表數(shù)組根據(jù)權(quán)值按照從小到大的順序排序；
3. 遍歷所有的邊， 通過parent 數(shù)組找到邊的連接信息，避免閉環(huán)問題；
4. 如果不存在閉環(huán)問題,則加入到最小生成樹中，并且修改parent 數(shù)組；

代碼實(shí)現(xiàn)

typedef struct Edge {
    int begin;
    int end;
    int weight;
} Edge;

/*
 Prim算法生成最小生成樹
 */

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;
}

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);
            }
        }
    }
}

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;
    
    Edge edges[MAXVEX];
    
    for (i = 0; i < G.numVertexes; i++) {
        for (j = i + 1; j < G.numVertexes; j++) {
            if (G.arc[i][j] < INFINITYC) {
                edges[k].begin = i;
                edges[k].end = j;
                edges[k].weight = G.arc[i][j];
                k++;
            }
        }
    }
    
    Sort(edges, &G);
    
    int parent[MAXVEX] = {0};
    for (i = 0; i < G.numEdges; i++) {
        m = Find(parent, edges[i].begin);
        n = Find(parent, edges[i].end);
        
        if (m != n) {
            parent[m] = n;
            sum += edges[i].weight;
            printf("(%d, %d) %d\n", edges[i].begin, edges[i].end, edges[i].weight);
        }
    }
    printf("sum = %d\n", sum);
}