如果連通圖是一個網，則稱該網中所有生成樹中權值總和最小的生成樹為最小生成樹，也稱最小代價生成樹。利用Prim算法構造的最小生成樹方法思想：
假設G=(V,E)是一個具有n個頂點的連通網，頂點集V={v1,v2,...,vn}.設所求的最小生成樹T=(U,TE),其中U是T的頂點集，TE是T的邊集，U和TE初值均為空集。
Prim算法的基本思想如下：首先從V中任取一個頂點(假定取v1),將生成樹T置為僅有一個結點v1的樹，即U={v1};然後只要U是V的真子集，就在所有那些一個端點在T中，另一個端點在T外的邊中，找一條最短（即權值最小 )的邊。假定符合條件的最短邊為(vi,vj),則把該條邊和其不在T中的頂點vj，分別並入T的邊集TE和頂點集U。如此進行下去，每次往生成樹裡並入一個頂點和一條邊，直到把所有頂點都包括進生成樹T為止。此時，必有U=V，TE中有n-1條邊，則T=(U,TE)是G的一棵最小生成樹。
設一個edge數組，記錄從頂點Ｕ集到Ｖ－Ｕ的代價最小的邊，每條邊的信息包括邊的始點和，終點和權值。從頂點u出發，利用prim算法求最小生成樹步驟如下：
(1) 初始化edge數組，記錄頂點u到圖中其余結點的代價最小的n-1的邊。
(2) 將頂點u加入Ｕ中。
(3) 當U不等於V時，做如下處理。
1) 從edge數組中選一條代價最小的邊。
2) 將該邊的終點加入U中。
3) 調整edges數組，使它始終記錄頂點U到V-U的代價最小的邊。
// 定義邊結構體
typedef struct{
int start;
int end;
int cost;
}Edge;
/*
*Prim算法求最小生成樹
* */
void Prim_MG(MGraph MG,char vs){
Edge edge[MAX_VEX_NUM];
int i,j,k,v,min;
int s = getIndexOfVexs(vs,&MG);
//初始化邊
for(i = 1;i <= MG.vexnum;i++){
if(s != i){
edge[i].start = s;
edge[i].end = i;
edge[i].cost = MG.arcs[s][i];
}
}
//首先將s加入生成樹集合中
edge[s].cost = 0;
for(i = 2;i <= MG.vexnum;i++){
min = 1000;
for(j = 1;j<= MG.vexnum;j++){
if(edge[j].cost != 0 && edge[j].cost < min ){
min = edge[j].cost;
k = j;
}
}
v = edge[k].end;
edge[v].cost = 0; // 加入新節點
//輸出生成樹中的邊
printf(%c %c %d
,MG.vexs[edge[v].start],MG.vexs[edge[v].end],MG.arcs[edge[v].start][edge[v].end]);
//重新調整數組
for(j = 1;j <= MG.vexnum;j++){
if(edge[j].cost != 0 && MG.arcs[v][j] != 0 && MG.arcs[v][j] < edge[j].cost){
edge[j].start = k;
edge[j].end = j;
edge[j].cost = MG.arcs[v][j];
}
}
}
}
假設圖中有n個頂點，則第一個進行初始化的循環語句的頻度為n,第二個循環語句頻度為n-1。其中有兩個內循環；其一是在edge數組中找權值最小的邊，其頻度為n-1,其二是重新調整edge數組的邊，頻度為n,所以Prim算法的時間復雜度為O(n^2)，而與圖中的邊數無關，因此適用於求稠密的最小生成樹。
/* * ===================================================================================== * * Filename: Prim.c * * Description: 最小生成樹算法之Prim算法 * * Version: 1.0 * Created: 2015年03月11日 15時27分19秒 * Revision: none * Compiler: gcc * * Author: jesson20121020 (), [email protected] * Organization: * * ===================================================================================== */ #include#include #define MAX_VEX_NUM 50 #define UN_REACH 1000 typedef char VertexType; typedef enum { DG, UDG } GraphType; typedef struct { VertexType vexs[MAX_VEX_NUM]; int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; int vexnum, arcnum; GraphType type; } MGraph; /** * 根據名稱得到指定頂點在頂點集合中的下標 * vex 頂點 * return 如果找到，則返回下標，否則，返回０ */ int getIndexOfVexs(char vex, MGraph *MG) { int i; for (i = 1; i <= MG->vexnum; i++) { if (MG->vexs[i] == vex) { return i; } } return 0; } /** * 創建鄰接矩陣 */ void create_MG(MGraph *MG) { int i, j, k,weight; int v1, v2, type; char c1, c2; printf(Please input graph type DG(0) or UDG(1) :); scanf(%d, &type); if (type == 0) MG->type = DG; else if (type == 1) MG->type = UDG; else { printf(Please input correct graph type DG(0) or UDG(1)!); return; } printf(Please input vexmun : ); scanf(%d, &MG->vexnum); printf(Please input arcnum : ); scanf(%d, &MG->arcnum); getchar(); for (i = 1; i <= MG->vexnum; i++) { printf(Please input %dth vex(char):, i); scanf(%c, &MG->vexs[i]); getchar(); } //初始化鄰接矩陣 for (i = 1; i <= MG->vexnum; i++) { for (j = 1; j <= MG->vexnum; j++) { if(i == j) MG->arcs[i][j] = 0; else MG->arcs[i][j] = UN_REACH; } } //輸入邊的信息，建立鄰接矩陣 for (k = 1; k <= MG->arcnum; k++) { printf(Please input %dth arc v1(char) v2(char) weight(int): , k); scanf(%c %c %d, &c1, &c2,&weight); v1 = getIndexOfVexs(c1, MG); v2 = getIndexOfVexs(c2, MG); if (MG->type == 1) MG->arcs[v1][v2] = MG->arcs[v2][v1] = weight; else MG->arcs[v1][v2] = weight; getchar(); } } /** * 打印鄰接矩陣和頂點信息 */ void print_MG(MGraph MG) { int i, j; if(MG.type == DG){ printf(Graph type: Direct graph ); } else{ printf(Graph type: Undirect graph ); } printf(Graph vertex number: %d ,MG.vexnum); printf(Graph arc number: %d ,MG.arcnum); printf(Vertex set: ); for (i = 1; i <= MG.vexnum; i++) printf(%c , MG.vexs[i]); printf( Adjacency Matrix: ); for (i = 1; i <= MG.vexnum; i++) { j = 1; for (; j < MG.vexnum; j++) { printf(%d , MG.arcs[i][j]); } printf(%d , MG.arcs[i][j]); } } // 定義邊結構體 typedef struct{ int start; int end; int cost; }Edge; /* *Prim算法求最小生成樹 * */ void Prim_MG(MGraph MG,char vs){ Edge edge[MAX_VEX_NUM]; int i,j,k,v,min; int s = getIndexOfVexs(vs,&MG); //初始化邊 for(i = 1;i <= MG.vexnum;i++){ if(s != i){ edge[i].start = s; edge[i].end = i; edge[i].cost = MG.arcs[s][i]; } } //首先將s加入生成樹集合中 edge[s].cost = 0; for(i = 2;i <= MG.vexnum;i++){ min = 1000; for(j = 1;j<= MG.vexnum;j++){ if(edge[j].cost != 0 && edge[j].cost < min ){ min = edge[j].cost; k = j; } } v = edge[k].end; edge[v].cost = 0; // 加入新節點 //輸出生成樹中的邊 printf(%c %c %d ,MG.vexs[edge[v].start],MG.vexs[edge[v].end],MG.arcs[edge[v].start][edge[v].end]); //重新調整數組 for(j = 1;j <= MG.vexnum;j++){ if(edge[j].cost != 0 && MG.arcs[v][j] != 0 && MG.arcs[v][j] < edge[j].cost){ edge[j].start = k; edge[j].end = j; edge[j].cost = MG.arcs[v][j]; } } } } /** * 主函數 */ int main(void) { MGraph MG; char startVex; create_MG(&MG); print_MG(MG); printf( Please input the start vex(char):); scanf(%c,&startVex); printf( The result of Prim: ); Prim_MG(MG,startVex); return EXIT_SUCCESS; }
jesson@jesson-HP:~/develop/workspace/c_learning/csdn/Prim$ gcc -o Prim Prim.c jesson@jesson-HP:~/develop/workspace/c_learning/csdn/Prim$ ./Prim Please input graph type DG(0) or UDG(1) :1 Please input vexmun : 4 Please input arcnum : 5 Please input 1th vex(char):a Please input 2th vex(char):b Please input 3th vex(char):c Please input 4th vex(char):d Please input 1th arc v1(char) v2(char) weight(int): a b 1 Please input 2th arc v1(char) v2(char) weight(int): a c 3 Please input 3th arc v1(char) v2(char) weight(int): a d 4 Please input 4th arc v1(char) v2(char) weight(int): b c 2 Please input 5th arc v1(char) v2(char) weight(int): c d 3 Please input the start vex(char):a The result of Prim: a b 1 b c 2 c d 3
