数据结构-最小通信网问题

问题描述：要在8个城市间建立通信网，已知各个城市间的距离（权），现要求如何才能使得建立的通信网络代价最小（最短）。
数据结构：用图来描述8个城市间的关系，顶点为城市，边为两个城市间的代价。
结果形式：输入城市图，输出应建立线路的边和总的代价。
测试数据：自定。

 typedef int VRType;
 typedef char InfoType;
 #define MAX_NAME 3 // 顶点字符串的最大长度+1
 #define MAX_INFO 20 // 相关信息字符串的最大长度+1
 typedef char VertexType[MAX_NAME];
 #include“Graph_Matrix.h“
 #include“Graph.h“

 typedef struct
 { // 记录从顶点集U到V-U的代价最小的边的辅助数组定义
   VertexType adjvex;
   VRType lowcost;
 }minside[MAX_VERTEX_NUM];

 int minimum（minside SZMGraph G）
 { // 求SZ.lowcost的最小正值，并返回其在SZ中的序号
   int i=0jkmin;
   while（!SZ[i].lowcost）
     i++;
   min=SZ[i].lowcost; // 第一个不为0的值
   k=i;
   for（j=i+1;j     if（SZ[j].lowcost>0&&min>SZ[j].lowcost） // 找到新的大于0的最小值
     {
       min=SZ[j].lowcost;
       k=j;
     }
   return k;
 }

 void MiniSpanTree_PRIM（MGraph GVertexType u）
 { // 用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。
   int ijkm;
   minside closedge;
   k=LocateVex（Gu）;
   for（j=0;j   {
     strcpy（closedge[j].adjvexu）;
     closedge[j].lowcost=G.arcs[k][j].adj;
   }
   closedge[k].lowcost=0; // 初始U={u}
   printf（“最小代价生成树的各条边为:\n“）;
   for（i=1;i   { // 选择其余G.vexnum-1个顶点
     k=minimum（closedgeG）; // 求出T的下一个结点：第k顶点
	 m=LocateVex（Gclosedge[k].adjvex）;//获取第一个顶点在数组中的位置
     printf（“（%s-%s） %d\n“closedge[k].adjvexG.vexs[k]G.arcs[m][k].adj）; // 输出生成树的边及权值
     closedge[k].lowcost=0; // 第k顶点并入U集
     for（j=0;j       if（G.arcs[k][j].adj       { // 新顶点并入U集后重新选择最小边
         strcpy（closedge[j].adjvexG.vexs[k]）;
         closedge[j].lowcost=G.arcs[k][j].adj;
       }
   }
 }

 void main（）
 {
   MGraph g;
   CreateUDN（g）; // 构造无向网g
   Display（g）; // 输出无向网g
   MiniSpanTree_PRIM（gg.vexs[0]）; // 用普里姆算法从g的第1个顶点出发输出最小生成树的各条边
   getchar（）;
   getchar（）;
 }

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      31744  2009-04-15 21:02  4-tongxin\Debug\tongxin.exe

     文件     330792  2009-04-15 21:02  4-tongxin\Debug\tongxin.ilk

     文件     519168  2009-04-15 21:02  4-tongxin\Debug\tongxin.pdb

     文件      11468  2009-04-15 21:03  4-tongxin\tongxin\Debug\BuildLog.htm

     文件      35485  2009-04-15 21:02  4-tongxin\tongxin\Debug\Main.obj

     文件         65  2009-04-15 21:03  4-tongxin\tongxin\Debug\mt.dep

     文件        621  2009-04-15 21:02  4-tongxin\tongxin\Debug\tongxin.exe.intermediate.manifest

     文件     191488  2009-04-15 21:02  4-tongxin\tongxin\Debug\vc90.idb

     文件     217088  2009-04-15 21:02  4-tongxin\tongxin\Debug\vc90.pdb

     文件       2265  2009-04-15 21:02  4-tongxin\tongxin\Graph.h

     文件        601  2009-04-15 19:09  4-tongxin\tongxin\Graph_Matrix.h

     文件       1949  2009-04-15 20:56  4-tongxin\tongxin\Main.cpp

     文件       3783  2009-04-15 19:09  4-tongxin\tongxin\tongxin.vcproj

     文件       1411  2009-04-15 21:05  4-tongxin\tongxin\tongxin.vcproj.Dave-PC.文刀.user

     文件    1182720  2009-04-15 21:05  4-tongxin\tongxin.ncb

     文件        887  2009-04-15 18:54  4-tongxin\tongxin.sln

    ..A..H.     10752  2009-04-15 21:05  4-tongxin\tongxin.suo

     文件      98304  2009-05-13 17:06  4-最小通信网.doc

     目录          0  2009-04-15 23:40  4-tongxin\tongxin\Debug

     目录          0  2009-04-15 23:40  4-tongxin\Debug

     目录          0  2009-04-15 23:40  4-tongxin\tongxin

     目录          0  2009-04-15 23:40  4-tongxin

----------- ---------  ---------- -----  ----

              2640591                    22