数据结构——Prim算法—

数据结构——Prim算法——最小生成树

数据结构上机要求用prim算法求最小生成树。

首先应该明白prim算法思想，即在一个网状图N=（V，{E}）中，假设M是图N最小生成树边的集合。再设有U和V两个点集合，从U={u0}（u0∈V）,M={}开始，进入循环操作：找出从点集U到点集V-U代价最小的边（u0,v0）u0∈U,v0∈V-U.并把边并入边集M中，v0也并入点集U中，直到U=V为止。此时M一定要有n-1条边（假设有n个顶点），Min=(U,{M})即为N的最小生成树。

该算法用到了最小生成树的一个MST性质：假设N=(V,{E})是一个连通网，U是点集V的一个非空子集。若（u，v）是一条最小权值边，其中u∈U,v∈V，则必存在一棵包含边（u，v）的最小生成树.

下面给出源码：

  1 #include"iostream"
  2 using namespace std;
  3 
  4 #define MAX 1000
  5 
  6 typedef struct ArcCell
  7 {
  8     double adj;
  9     int *info;
 10 }ArcCell,adjmatrix[100][100];//adj表示边的权值大小
 11 
 12 typedef struct 
 13 {
 14     char vexs[100];
 15     adjmatrix arcs;
 16     int vexnum,arcnum;//图的顶点个数和弧度数
 17 }MGraph;//以上均为用邻矩阵的储存结构定义图
 18 
 19 typedef struct Pnode
 20 {//建立一个储存U和V之间最短边的结构体
 21     char adjvex;
 22     int lowcost;
 23 }closedge[100];
 24 
 25  typedef struct Node
 26 {//建立一个储存两个顶点和它们之间权值大小的结构体
 27     char start;
 28     char end;
 29     double value;
 30 }Node,Dgevalue[100];
 31 
 32 int locatevex(MGraph G,char ch)
 33 {//定位起始顶点ch在图中的位置
 34     int k;
 35     for(int i=0;i<G.vexnum;i++)
 36     {
 37         if(G.vexs[i]==ch)
 38             k=i;
 39     }
 40     return k;
 41 }
 42 
 43 int creatmatrix(MGraph &G,Dgevalue &dgevalue)
 44 {//构造邻接矩阵
 45     int i,j,k;
 46     cout<<"请输入顶点个数和弧度数"<<endl;
 47     cin>>G.vexnum>>G.arcnum;
 48     
 49     for(i=0;i<G.vexnum;i++)//读入顶点
 50         cin>>G.vexs[i];
 51 
 52     for(i=0;i<G.vexnum;i++)
 53     {//初始化边的权值为MAX
 54         for(j=0;j<G.vexnum;j++)
 55         {
 56             G.arcs[i][j].adj=MAX;
 57         }
 58     }
 59     cout<<"请输入一条边两端的定点及其上权值"<<endl;
 60     for(k=0;k<G.arcnum;k++)
 61     {//读入始终点及其上的权值value
 62         cin>>dgevalue[k].start>>dgevalue[k].end>>dgevalue[k].value;
 63         i=locatevex(G,dgevalue[k].start);
 64         j=locatevex(G,dgevalue[k].end);
 65         G.arcs[i][j].adj=dgevalue[k].value;
 66         G.arcs[j][i].adj=G.arcs[i][j].adj;
 67     }
 68     return 0;
 69 }
 70 
 71 
 72 int minum(MGraph G,closedge close)
 73 {//求U和V之间的最短边
 74         int i,j,k=1000;
 75         for(i=0;i<G.vexnum;i++)
 76         {
 77             if(close[i].lowcost!=0&&close[i].lowcost<k)
 78                 {
 79                     k=close[i].lowcost;    
 80                      j=i;
 81                 }
 82         }
 83         return j;
 84 }
 85 
 86 void creatminitree_prim(MGraph G,char u)
 87 {//用prim算法从第u个顶点出发，构造最小生成树,输出各边
 88         int i,j,k;
 89         closedge close;
 90 
 91         k=locatevex(G,u);
 92         for(i=0;i<G.vexnum;i++)
 93         {
 94             if(i!=k)//初始化close[].adjvex全为u
 95             {
 96                 close[i].adjvex=u;
 97                 close[i].lowcost=G.arcs[k][i].adj;
 98             }
 99         }
100         close[k].lowcost=0;
101 
102         
103 
104         for(j=1;j<G.vexnum;j++)
105         {
106             k=minum(G,close);
107             cout<<close[k].adjvex<<","<<G.vexs[k]<<" "<<close[k].lowcost<<endl;
108             
109             close[k].lowcost=0;//将k并入集合U
110             for(i=0;i<G.vexnum;i++)
111             {//将k并入U后，原本储存的各个点从U到V的最小边就会改变，逐一更新
112                 if(G.arcs[k][i].adj<close[i].lowcost)
113                 {
114                     close[i].lowcost=G.arcs[k][i].adj;
115                     close[i].adjvex=G.vexs[k];
116                 }
117             }
118     }
119 }
120 
121 int main()
122 {//主函数调用
123     char u;
124      MGraph G;
125      Dgevalue dgevalue;
126      creatmatrix(G,dgevalue);
127      cout<<"用prim算法求最小生成树"<<endl;
128     cout<<"请输入起点" <<endl;
129      cin>>u;
130      creatminitree_prim(G,u);
131     
132 
133      return 0;
134 }

第一次写东西，希望有个好的开始，cheer up~!~ 2012-12-09