MST_PRIM算法学习心得
MST_PRIM算法学习心得2010-06-08 11:48 数据结构书中有一个很经典的问题，就是求n个城市之间以最节省经费建立通信网问题，它属于构造最小生成树的问题，构造最小生成树算法属Prim（普利姆）算法和Kruskal（克鲁斯卡尔）算法最为经典，当然，还有很多其它算法构造最小生成树，这里不多提了，待自己去啃资料了。Prim算法，它的基本思想是这样的：一个集合U表结点全集，定义两个集合V和S，S代表最小生成树结点集，V代表S的补集，从起始节点k开始访问，把k放入S中，然后取连接在集S和集V中各找出一结点组成的边，一一比较它们的大小，找出具最小权值的边，然后把该边对应的在补集V中的节点v放入S中，循环执行找最小边过程，直到最小生成树集S=U时退出循环，在这个过程当中所找出来的都是满足连接两集合的最小边，这样就保证了构成的是一棵最小生成树。在对Prim算法基本思想粗略理解的基础上，小弟想出了一个比较直接表达该思想的算法，时间复杂度为O（n^3），算法描述如下：1.定义一个辅助数组flag[]，用来标记该点是否存入最小生成树集S中，如果flag[i]=1,说明第i个节点已经并入S中，反之则反。2.算法过程函数MST_PRIM（MGraph， int），传入两个参数，第一个是用邻接矩阵表示的图MG，第二个参数表示起始节点的数据u；3.首先找出起始节点的编号赋予k（k=LocateVex（MG, u）），把该节点放入S中（即flag[k]=1）；4.比较所有连接S和V的边的权值，找出具最小权值的边，（此处反映出Prim算法思想）记录该边对应集V（非最小生成树集）中结点v的编号j，把节点v放入S中；5.重复步骤4，直到S=U退出循环。代码如下：//图的邻接矩阵表示结构体typedef struct MG{int vexs[20][2];int adj[20][20];int vexnum, arcnum;}MGraph;MGraph MG1;int LocateVex(MGraph G, int u){int i;for(i=1; i<=G.vexnum; i++){if(u==G.vexs[i][0])return i;}return -1;}void MST_PRIM(MGraph G, int u){int k, i, j, count=1, min,flag[20], h, l;for(i=0; i<20; i++)flag[i]=0;k = LocateVex(G, u);flag[k]=1;while(count++
G.adj[h][i] && G.adj[h][i]>0 && i!=h){min=G.adj[h][i];j=i;l=h;}}}}printf("(%d, %d) ", l, j);flag[j]=1;}printf("/n");}int main(){int u, i;MG1.vexnum=6;for(i=0; i<20; i++){closedge[i].lowcost = 0;}for(i=1; i<=MG1.vexnum; i++){MG1.vexs[i][0]=i;MG1.vexs[i][1]=0;}//十条边MG1.arcnum=10;//给边赋权值MG1.adj[1][2]=6;MG1.adj[2][1]=6;MG1.adj[1][3]=1;MG1.adj[3][1]=1;MG1.adj[1][4]=5;MG1.adj[4][1]=5;MG1.adj[2][3]=5;MG1.adj[3][2]=5;MG1.adj[2][5]=3;MG1.adj[5][2]=3;MG1.adj[3][5]=6;MG1.adj[5][3]=6;MG1.adj[3][6]=4;MG1.adj[6][3]=4;MG1.adj[3][4]=5;MG1.adj[4][3]=5;MG1.adj[4][6]=2;MG1.adj[6][4]=2;MG1.adj[5][6]=6;MG1.adj[6][5]=6;//从第几个点开始printf("Enter u: ");scanf("%d", &u);MST_PRIM(MG1, u);system("pause");return 0;}当对上面这个程序进行调整后，可以优化成一个时间复杂度为O（n^2）的算法，变化如下：1．添加两个辅助数组prevVex[]和LowestC[]；2．prevVex存储V中结点v找到最小边时对应S中的结点u（prevVex[v]=u，u为v的前驱，即u->v），lowestC存储从源结点到对应V中结点v的最小权值（lowestC[v]=adj[u][v]）；3．如果表lowestC[]原来存在有对应的值，当进行下一轮搜索最小边时当前边权值adj[a][b]就先和原来存在的lowestC[b]值比较，如果小于原lowestC[b]值时用adj[a][b]进行覆盖，否则不改变该lowestC[b]值，并且对应结点b的prevVex[b]指向的源结点也不改变；4．从起始结点开始遍历，循环查找直到S=U退出循环。代码如下:void MST_PRIM_O_2(MGraph G, int u){int k, i, j, min, flag[20]={0}, lowestC[20]={0}, prevVex[20]={0};//定位起始结点k = LocateVex(G, u);flag[k]=1;//用表存起始结点所有的邻边权值for(i=1; i<=G.vexnum; i++){if(i!=k && G.adj[k][i]>0){prevVex[i]=k;lowestC[i]=G.adj[k][i];}}//从起始结点开始的最小边搜索for(j=2; j<=G.vexnum; j++){min=1000;//找出权值最小边，记录其编号for(i=1; i<=G.vexnum; i++){if(lowestC[i]>0 && min>lowestC[i] && !flag[i]){min=lowestC[i];k=i;}}printf("(%d, %d)", prevVex[k], G.vexs[k]);flag[k]=1;//用表存k结点的邻接边的权值for(i=1; i<=G.vexnum; i++){//满足三个条件：//1.结点未被访问；//2.原表中值大于对应边（k，i）的权值或者原表中值为空；//3.边存在（即权值大于0）。if(!flag[i] && (G.adj[k][i]
0){lowestC[i]=G.adj[k][i];prevVex[i]=k;}}}printf("/n");}总结：时间复杂度为O（n^3）的算法直接对边的权值进行比较，找出满足条件的具最小权值的边，输出该边；时间复杂度为O（n^2）的算法用一表暂存每个结点对应的经处理后的邻边的权值序列，具最小权值的边必在这个序列中，找出并输出该边。附上数据结构课本Prim算法的代码：void MiniSpanTree_PRIM(MGraph G, int u){int i, j, k;k = LocateVex(G, u);for(j=1; j<=G.vexnum; ++j)if(j!=k){closedge[j].adjvex = u;closedge[j].lowcost = G.adj[k][j];}closedge[k].lowcost = -1;for(i=2; i<=G.vexnum; i++){k = minimum(closedge);printf("(%d, %d) ", closedge[k].adjvex, G.vexs[k]);closedge[k].lowcost = -1;for(j=1; j<=G.vexnum; j++)if(closedge[j].lowcost>=0 && G.adj[k][j]>0 && j!=k && (G.adj[k][j] < closedge[j].lowcost || closedge[j].lowcost==0)){closedge[j].adjvex = G.vexs[k];closedge[j].lowcost = G.adj[k][j];}}printf("/n");}
[i]>
){min=1000;for(h=1;>