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

时间:2021-03-02 09:52:55

转自 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. }