最小生成树算法---普里姆Prim算法

转自 http://blog.csdn.net/hustspy1990/article/details/6043698

1. 邻接矩阵存储

 

[cpp] view plaincopy

1. //图的邻接矩阵存储表示  
2. #define INFINITY INT_MAX  
3. #define MAX_VERTEX_NUM 20  
4. typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网}  
5. typedef enum {OK, ERROR} Status;  
6. typedef struct ArcCell{  
7.     int adj;        //顶点关系类型。对于无权图，用0或1表示相邻否。对于有权图，则为权值类型。  
8.     string info;    //该弧所携带的信息  
9. }ArcCell, AdjMatrix;  
10. typedef struct {  
11.     int vexs[MAX_VERTEX_NUM];   //顶点向量  
12.     AdjMatrix arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];             //邻接矩阵  
13.     int vexnum, arcnum;         //图的当前顶点数和弧数  
14.     GraphKind kind;             //图的种类标志  
15. }MGraph;  
16. bool visited[MAX_VERTEX_NUM];   //设访问标志数组，供遍历时使用  

 

 

[cpp] view plaincopy

1. //Prim算法-记录从顶点集U到V-U的代价最小的边的辅助数组定义  
2. struct {  
3.     int adjvex;  
4.     int lowcost;  
5. }closedge[MAX_VERTEX_NUM];  

 

 

2. Prim算法

 

[cpp] view plaincopy

1. void MiniSpanTree_PRIM(MGraph G, int u)  
2. {  
3.     //用普里姆Prim算法从第u个顶点出发，构造网G的最小生成树T，输出T的各条边  
4.     //记录从顶点集U到V-U的代价最小的边的辅助数组定义  
5.     //  struct {  
6.     //      int adjvex;  
7.     //      int lowcost;  
8.     //  }closedge[MAX_VERTEX_NUM];  
9.     int i,j,k;  
10.     for(j=0; j<G.vexnum; ++j)        //辅助数组初始化  
11.         if(j!=u)  
12.         {  
13.             closedge[j].adjvex = u;  
14.             closedge[j].lowcost = G.arcs[u][j].adj;  
15.         }  
16.     closedge[u].lowcost = 0;        //初始化U={u}  
17.     for(i=0; i<G.vexnum; ++i)  
18.     {  
19.         int min = INT_MAX;  
20.         k=-1;  
21.         for(j=0; j<G.vexnum; ++j)    //求出最小生成树的下一个顶点k  
22.             if(closedge[j].lowcost >0 && closedge[j].lowcost < min)  
23.             {  
24.                 k = j;  
25.                 min = closedge[j].lowcost;  
26.             }//if  
27.         if(k <0)  
28.             return;  
29.         cout<<closedge[k].adjvex<<"——"<<G.vexs[k]<<" ： "<<closedge[k].lowcost<<endl;    //输出生成树的边  
30.         closedge[k].lowcost = 0;                    //第k顶点并入U集  
31.         for(j=0; j<G.vexnum; ++j)  
32.             if(G.arcs[k][j].adj < closedge[j].lowcost)   //新顶点并入U后，重新选择最小边  
33.             {  
34.                 closedge[j].adjvex = G.vexs[k];  
35.                 closedge[j].lowcost = G.arcs[k][j].adj;  
36.             }  
37.     }  
38. }//MiniSpanTree_PRIM  

 

3. 构造一个测试用的无向网

 

[cpp] view plaincopy

1. void CreateUDNTest(MGraph &G)  
2. {   //构造一个测试用的无向网  
3.     int i,j;  
4.     //数组a[10][3]存放“边”和对应的权值  
5.     int a[10][3] = { {0, 1, 6}, {0, 2, 1}, {0, 3, 5},  
6.     {1, 2, 5}, {1, 4, 3}, {2, 3, 5}, {2, 4, 6}, {2, 5, 4},  
7.     {4, 5, 6}, {3, 5, 2}  
8.     };  
9.     G.kind = UDN;  
10.     G.vexnum = 6;  
11.     G.arcnum = 10;  
12.     for(i=0; i<G.vexnum; ++i)        //构造顶点向量  
13.         G.vexs[i] = i;  
14.     for(i=0; i<G.vexnum; ++i)        //初始化为全INT_MAX  
15.         for(j=0; j<G.vexnum; ++j)  
16.         {  
17.             G.arcs[i][j].adj = INT_MAX;  
18.             G.arcs[i][j].info = "";  
19.         }  
20.     for(i=0; i<G.arcnum; ++i)        //对存在的边赋值  
21.         G.arcs[a[i][0]][a[i][1]].adj = G.arcs[a[i][1]][a[i][0]].adj = a[i][2];  
22. }  

 

4.主函数

 

[cpp] view plaincopy

1. int main()  
2. {  
3.     MGraph gra2;  
4.     CreateUDNTest(gra2);            //构造无向网G  
5.     cout<<"构造最小生成树："<<endl;  
6.     MiniSpanTree_PRIM(gra2, 0);  
7.     return 0;  
8. }