地铁建设问题最小生成树

城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。 （1）使用恰当的数据结构存储辖区名称和距离信息。 （2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线。 （3）输出应该建设的路线，以及所需建设的总里程信息。

#include
#include
#include
#include 
#include 
#include 
#include
#include 

 /* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR -1
#define INFEASIBLE -1

#define MAXVEX 30
#define MAXNAME 20   /*顶点信息长度最大值*/
#define MAX 32767    /*若顶点间无路径则以此最大值表示不通*/
typedef char VexType[MAXNAME];   /*顶点信息*/
typedef float AdjType;   /*两顶点间的权值信息*/
typedef struct   /*边结构体*/
{
    int start_vex stop_vex;        /* 边的起点和终点 */
    AdjType weight;                 /* 边的权 */
} Edge;
typedef struct  /*图结构*/
{
    int vexNum;                     /* 图的顶点个数 */
	int edgeNum;					/*图中边的数目*/
	Edge mst[MAXVEX-1];				/*用于保存最小生成树的边数组只用到 顶点数-1 条*/
    VexType vexs[MAXVEX];			/*顶点信息 */
    AdjType arcs[MAXVEX][MAXVEX];   /* 边的邻接矩阵 */
} GraphMatrix;
int LocateVex（GraphMatrix *g VexType u）    /*操作结果: 若g中存在顶点u则返回该顶点在图中位置;否则返回-1*/
 {
   int i;
   for（i=0;ivexNum;++i）
     if（strcmp（ug->vexs[i]）==0）
       return i;
   return ERROR;
 }
void GraphInit（GraphMatrix *g）   /*用包含图的信息的文件初始化图*/
{
	int ijt;
	float w;   /*边的权值*/
	VexType vavb;    /*用于定位图的顶点（字符串）在邻接矩阵中的下标*/
	FILE *fp;
    fp=fopen（“spaningtree.txt““r“）;
	fscanf（fp“%d“&g->vexNum）;   /*读入图的顶点数和边数*/
	fscanf（fp“%d“&g->edgeNum）;
	for（i=0;ivexNum;i++）   /*初始化邻接矩阵*/
		for（j=0;j<=i;j++）
			g->arcs[i][j]=g->arcs[j][i]=MAX;
	for（i=0;ivexNum;i++）   /*从文件读入顶点信息*/
		fscanf（fp“%s“g->vexs[i]）;
	for（t=0;tedgeNum;t++）  /*定位各边并赋权值*/
	{
		fscanf（fp“%s%s%f“vavb&w）;
		i=LocateVex（gva）;
		j=LocateVex（gvb）;
		g->arcs[i][j]=g->arcs[j][i]=w;
	}
	fclose（fp）;
}
void Prim（GraphMatrix * pgraph）   /* 用邻接矩阵求图的最小生成树-普里姆算法*/
{
    int i j min;
	int vx vy;    /*起始终止点*/
    float weight minweight; 
	Edge edge;   /*用于交换边*/
    for （i = 0; i < pgraph->vexNum-1; i++）   /*初始化最小生成树边的信息*/
	{
        pgraph->mst[i].start_vex = 0;   /*起始点为0号顶点*/
        pgraph->mst[i].stop_vex = i+1;   /*终止点为其他各顶点*/
        pgraph->mst[i].weight = pgraph->arcs[0][i+1];   /*权值为0号顶点到其他各顶点的路径权值无路径则为MAX*/
    }
    for （i = 0; i < pgraph->vexNum-1; i++）   /* 共n-1条边 */
	{
        minweight = MAX;  min = i;
        for （j = i; j < pgraph->vexNum-1; j++）/* 从所有边（vxvy）（vx∈Uvy∈V-U）中选出最短的边 */
            if（pgraph->mst[j].weight < minweight）
			{
                minweight = pgraph->mst[j].weight; 
                min = j;
            }
        /* mst[min]是最短的边（vxvy）（vx∈U vy∈V-U），将mst[min]加入最小生成树 */
        edge = pgraph->mst[min];  
        pgraph->mst[min] = pgraph->mst[i];   
        pgraph->mst[i] = edge;
        vx = pgraph->mst[i].stop_vex;            /* vx为刚加入最小生成树的顶点的下标 */
        for（j = i+1; j < pgraph->vexNum-1; j++） /* 调整mst[i+1]到mst[n-1] */
		{ 
            vy=pgraph->mst[j].stop_vex;
			weight = pgraph->arcs[vx][vy];
            if （weight < pgraph->mst[j].weight） 
			{
                pgraph->mst[j].weight = weight;  
                pgraph->mst[j].st

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2011-09-14 20:12  地铁建设问题\
     目录           0  2011-09-14 20:07  地铁建设问题\Debug\
     文件      208975  2011-09-14 19:51  地铁建设问题\Debug\Subway construction.exe
     文件      206260  2011-09-14 19:51  地铁建设问题\Debug\Subway construction.ilk
     文件        7190  2011-09-14 20:07  地铁建设问题\Debug\Subway construction.obj
     文件      259112  2011-09-14 19:51  地铁建设问题\Debug\Subway construction.pch
     文件      402432  2011-09-14 19:51  地铁建设问题\Debug\Subway construction.pdb
     文件       41984  2011-09-14 20:07  地铁建设问题\Debug\vc60.idb
     文件       53248  2011-09-14 20:07  地铁建设问题\Debug\vc60.pdb
     文件         442  2011-09-14 19:49  地铁建设问题\spaningtree.txt
     文件        3903  2011-09-14 20:12  地铁建设问题\Subway construction.cpp
     文件        3559  2011-09-14 19:51  地铁建设问题\Subway construction.dsp
     文件         563  2011-09-14 20:12  地铁建设问题\Subway construction.dsw
     文件       33792  2011-09-14 20:12  地铁建设问题\Subway construction.ncb
     文件       48640  2011-09-14 20:12  地铁建设问题\Subway construction.opt
     文件         731  2011-09-14 20:07  地铁建设问题\Subway construction.plg