1. 最小生成樹（又名：最小權(quán)重生成樹）

概念：將給出的所有點連接起來（即從一個點可到任意一個點），且連接路徑之和最小的圖叫最小生成樹。最小生成樹屬于一種樹形結(jié)構(gòu)（樹形結(jié)構(gòu)是一種特殊的圖），或者說是直鏈型結(jié)構(gòu)，因為當(dāng)n個點相連，且路徑和最短，那么將它們相連的路一定是n-1條。

可以利用參考一個問題理解最小生成樹，有n個村莊，每個村莊之間距離不同，要求村莊之間修路，每一個村莊必須與任意一個村莊聯(lián)通，如何修路最省錢（修的最短）

2. 普利姆算法介紹

利姆(Prim)算法求最小生成樹，也就是在包含n個頂點的連通圖中，找出只有(n-1)條邊包含所有n個頂點的連通子圖，也就是所謂的極小連通子圖

具體過程如下：

(1)設(shè)G=(V,E)是連通網(wǎng)，T=(U,D)是最小生成樹，V,U是頂點集合，E,D是邊的集合 

(2)若從頂點u開始構(gòu)造最小生成樹，則從集合V中取出頂點u放入集合U中，標(biāo)記頂點v的visited[u]=1

(3)若集合U中頂點ui與集合V-U中的頂點vj之間存在邊，則尋找這些邊中權(quán)值最小的邊，但不能構(gòu)成回路，將頂點vj加入集合U中，將邊（ui,vj）加入集合D中，標(biāo)記visited[vj]=1

(4)重復(fù)步驟②，直到U與V相等，即所有頂點都被標(biāo)記為訪問過，此時D中有n-1條邊

3. 代碼實現(xiàn)

不同的題目有不同的細(xì)節(jié)實現(xiàn)方式，因此本代碼僅供參考

#include <stdio.h>
#include <stdlib.h>
#define n 20
#define MaxNum 10000  /*定義一個最大整數(shù)*/
 
/*定義鄰接矩陣類型*/
typedef int adjmatrix[n + 1][n + 1];   
typedef struct {
    int fromvex, tovex;                 //生成樹的起點和終點
    int weight;                         //邊的權(quán)重
} Edge;
typedef Edge *EdgeNode;                 //定義生成樹的別名
int arcnum;     /*邊的個數(shù)*/
 
/*建立圖的鄰接矩陣*/
void CreatMatrix(adjmatrix GA) {
    int i, j, k, e;
    printf("=============================\n");
    printf("圖中有%d個頂點\n", n);
    for(i=1; i<=n; i++) {
        for(j=1; j<=n; j++) {
            if(i==j) {
                GA[i][j]=0;         /*對角線的值置為0*/
            } else {
                GA[i][j]=MaxNum;    /*其他位置的值置初始化為一個最大整數(shù)*/
            }
        }
    }
    printf("請輸入邊的個數(shù)：\n");
    scanf("%d", &arcnum);
    printf("請輸入邊的信息，依照起點，終點，權(quán)值的形式輸入：\n");
    for(k=1; k<=arcnum; k++) {
        scanf("%d,%d,%d",&i,&j,&e);  /*讀入邊的信息*/
        GA[i][j]=e;
        GA[j][i]=e;
    }
}
 
/*初始化圖的邊集數(shù)組*/
void InitEdge(EdgeNode GE,int m) {
    int i;
    for(i=1; i<=m; i++) {
        GE[i].weight=0;
    }
}
 
/*依據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組*/
void GetEdgeSet(adjmatrix GA,EdgeNode GE) {
    int i, j, k = 1;
    for(i=1; i<=n; i++) {
        for(j=i+1; j<=n; j++) {
            if(GA[i][j] !=0 && GA[i][j] != MaxNum) {
                GE[k].fromvex = i;
                GE[k].tovex = j;
                GE[k].weight = GA[i][j];
                k++;
            }
        }
    }
}
 
/*按升序排列圖的邊集數(shù)組*/
void SortEdge(EdgeNode GE,int m) {
    int i,j,k;
    Edge temp;
    for(i=1; i<m; i++) {
        k=i;
        for(j=i+1; j<=m; j++) {
            if(GE[k].weight > GE[j].weight) {
                k=j;
            }
        }
        if(k!=i) {
            temp = GE[i];
            GE[i]=GE[k];
            GE[k]=temp;
        }
    }
}
 
/*利用普里姆算法從初始點v出發(fā)求鄰接矩陣表示的圖的最小生成樹*/
void Prim(adjmatrix GA,EdgeNode T) {
    int i,j,k,min,u,m,w;
    Edge temp;
    /*給T賦初值。相應(yīng)為v1依次到其余各頂點的邊*/
    k=1;
    for(i=1; i<=n; i++) {
        if(i!=1) {
            T[k].fromvex=1;
            T[k].tovex=i;
            T[k].weight=GA[1][i];
            k++;
        }
    }
    /*進行n-1次循環(huán)，每次求出最小生成樹中的第k條邊*/
    for(k=1; k<n; k++) {
        min=MaxNum;
        m=k;
        for(j=k; j<n; j++) {
            if(T[j].weight<min) {
                min=T[j].weight;
                m=j;
            }
        }
        /*把最短邊對調(diào)到k-1下標(biāo)位置*/ 可用swap替換
        temp=T[k];
        T[k]=T[m];
        T[m]=temp;
        /*把新增加最小生成樹T中的頂點序號賦給j*/
        j=T[k].tovex;
        /*改動有關(guān)邊，使T中到T外的每個頂點保持一條到眼下為止最短的邊*/
        for(i=k+1; i<n; i++) {
            u=T[i].tovex;
            w=GA[j][u];
            if(w<T[i].weight) {
                T[i].weight=w;
                T[i].fromvex=j;
            }
        }
    }
}
 
/*輸出邊集數(shù)組的每條邊*/
void OutEdge(EdgeNode GE,int e) {
    int i;
    printf("依照起點，終點。權(quán)值的形式輸出的最小生成樹為：\n");
    for(i=1; i<=e; i++) {
        printf("%d,%d,%d\n",GE[i].fromvex,GE[i].tovex,GE[i].weight);
    }
    printf("=============================\n");
}
 
int main() {
    adjmatrix GA;
    Edge GE[n*(n-1)/2], T[n];
    CreatMatrix(GA);
    InitEdge(GE,arcnum);
    GetEdgeSet(GA,GE);
    SortEdge(GE,arcnum);
    Prim(GA,T);
    printf("\n");
    OutEdge(T,n-1);
    return 0;
}