2 算法描述
本设计是基于最小生成树普里姆算法的思想上，以实现在网络中可以选择出最短线路，
从而达到省时省力的效果。
2.1算法思想
普里姆算法的基本思想：从连通网络 N = { V, E }中的某一顶点 u0 出发, 选择与它关联的具有最小权值的边 ( u0, v ), 将其顶点加入到生成树顶点集合U中。以后每一步从一个顶点在 U 中,而另一个顶点不在 U 中的各条边中选择权值最小的边(u, v), 把它的顶点加入到集合 U 中。如此继续下去, 直到网络中的所有顶点都加入到生成树顶点集合 U 中为止。
存储方式：采用邻接矩阵作为图的存储表示
假设要在n个城市之间建立通信联络网，则联通n个城市只需要n-1条线路，然而n个城市之间最多可能设置n(n-1)/2条线路，此时，自然会考虑一个问题，如何在这些可能的线路中选择n-1条，使的在最节省经费的前提下建立起这个通信网。这就可以简化为构造联通网的最小代价生成树（简称 最小生成树）问题。
任务：根据普里姆的算法思想，输出连通网络图的最小生成树。
2
2.2最小生成树生成过程
普里姆算法最小生成树生成过程的图示如图2.1所示：
3
2.3普里姆算法
void MiniSpanTree_PRIM(Graph G,VertexType u) {
//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。 //记录从顶点集U到V-U的代价最小边的辅助数组定义： //struct {
// Vertextype adjvex; // VRType lowcost;
// }closedege[MAX_VERTEX_NUM]; k=LocateVex (G, u);
for(j=0;j if(j!=k) closedge[j]={u, G.arcs[k][j].adj}; //{adjvex, lowcost } closedge[k].lowcost=0; /* 初始，U={u} */ for(i=1;i closedge[k].lowcost=0; /* 第k顶点并入U集 */ for(j=0;j<=G.vexnum;++j) if(G.arcs[k][j].adj } }// MiniSpanTree 2.4需要解决的问题 PRIM算法中需要解决的两个问题：①在无向网中，当出现从一个顶点到其它顶点时，若其边上的权值相等，则可能从某一起点出发时会得出不同的最小生成树，但最小生成树的权必定都相等，此时我们应该怎样将所有的最小生成树求解出来； ②每次如何从生成树T中到T外的所有边中，找出一条最短边。例如，在第k次（1≤k≤n-1）前，生成树T中已有k个顶点和k-1条边，此时T中到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相联，其权值被看做常量INFINIT的边在内，从如此多的边中查找最短边，其时间复杂度为O(k(n-k))，显然是很费时的，是否有一种好的方法能够降低查找最短边的时间复杂度。 4 2.5解决问题的方法 针对①中出现的问题可以通过在算法中实现，详情请看PRIM算法的基本思想； 针对②中出现的问题，通过对PRIM算法的分析，可以使查找最短边的时间复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点（共n-k个顶点）的各一条最短边，进行第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从T中到T外的所有边中的最短边，假设为（i,j），此步需进行n-k次比较；然后把边（i,j）和顶点j分别并入T中的边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t，若（j,t）边上的权值小于已保留的从原T中到顶点t的最短边的权值，则用（j,t）修改之，使从T中到T外顶点t的最短边为（j,t），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。 5 3 流程图 1) 主函数流程图如图3 .1所示： 开始 显示菜单，进行选择 输出函数put() 退出系统 示例帮助（example()） break break 谢谢使用! 结束 图 3.1 主函数流程图 6