#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?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?vexNum-1;?i++）???/*?共n-1條邊?*/
	{
????????minweight?=?MAX;??min?=?i;
????????for?（j?=?i;?j?vexNum-1;?j++）/*?從所有邊（vxvy）（vx∈Uvy∈V-U）中選出最短的邊?*/
????????????if（pgraph->mst[j].weight?			{
????????????????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?vexNum-1;?j++）?/*?調整mst[i+1]到mst[n-1]?*/
		{?
????????????vy=pgraph->mst[j].stop_vex;
			weight?=?pgraph->arcs[vx][vy];
????????????if?（weight?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