#include?
#define?TRUE?1
#define?FALSE?0
#define?OK?1
#define?ERROR?0
#define?INFINITY?10000????????????????????//最大值
#define?MAXVEX?20?????????????????????????//最大頂點(diǎn)個數(shù)
typedef?int?Status;
typedef?char?VertexType;??????????????????//?頂點(diǎn)類型應(yīng)由用戶定義
typedef?int?EdgeType;?????????????????????//邊上的權(quán)值類型應(yīng)由用戶定義

typedef?struct{
	VertexType?vexs[MAXVEX];??????????????//頂點(diǎn)向量
????EdgeType?arc[MAXVEX][MAXVEX];?????????//鄰接矩陣可看作邊表
	int?vexnumarcnum;????????????????????//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)
}MGraph;

//建立無向圖的鄰接矩陣表示
void?CreateMGraph（MGraph?*G）
{
	int?ijkw;
	printf（“Please?enter?the?number?of?station?and?road:\n“）;
	scanf（“%d%d“&G->vexnum&G->arcnum）;?//輸入車站（頂點(diǎn)）數(shù)量和道路（邊）數(shù)量
	for（i=0;ivexnum;i++）??????????????//讀入頂點(diǎn)信息建立頂點(diǎn)表
		scanf（&G->vexs[i]）;
	for（i=0;ivexnum;i++）
		for（j=0;jvexnum;j++）
			G->arc[i][j]=INFINITY;	??????//鄰接矩陣初始化
	for（k=0;karcnum;k++）??????????????//讀入arcnum條邊建立鄰接矩陣
	{
		printf（“Enter?road（vivj）‘s?Sign?iSign?j?and?Distance?w:\n“）;
		scanf（“%d%d%d“&i&j&w）;???????//輸入邊（vivj）上的權(quán)w
		G->arc[i][j]=w;?
		G->arc[j][i]=?G->arc[i][j];???????//因?yàn)槭菬o向圖矩陣對稱
	}
}

//Prim算法生成最小生成樹
void?MiniSpanTree_Prim（MGraph?G）
{
	int?min?i?j?ksum=0;
	int?adjvex[MAXVEX];		??????????????//保存相關(guān)頂點(diǎn)下標(biāo)
	int?lowcost[MAXVEX];	??????????????//保存相關(guān)頂點(diǎn)間邊的權(quán)值
	printf（“The?shortest?line（By?Prim）?is:\n“）;
	lowcost[0]=0;?????????????????????????//初始化第一個權(quán)值為0即v0加入生成樹
			??????????????????????????????//lowcost的值為0在這里就是此下標(biāo)的頂點(diǎn)已經(jīng)加入生成樹
	adjvex[0]=0;			??????????????//初始化第一個頂點(diǎn)下標(biāo)為0
	for（i=1;i	{
		lowcost[i]=G.arc[0][i];	??????????//將v0頂點(diǎn)與之有邊的權(quán)值存入數(shù)組
		adjvex[i]=0;					??//初始化都為v0的下標(biāo)
	}
	for（i=1;i	{
		min=INFINITY;	??????????????????//初始化最小權(quán)值
		j=1;k=0;
		while（j		{
			if（lowcost[j]!=0&&lowcost[j]			??????????????????????????????//如果權(quán)值不為0且權(quán)值小于min
			{	
				min=lowcost[j];	??????????//則讓當(dāng)前權(quán)值成為最小值
				k=j;			??????????//將當(dāng)前最小值的下標(biāo)存入k
			}
			j++;
		}
		printf（“（%d%d）\n“adjvex[k]k）;??//打印當(dāng)前頂點(diǎn)邊中權(quán)值最小的邊
		sum=sum+lowcost[k];???????????????//累加最短路徑
		lowcost[k]=0;?????????????????????//將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0表示此頂點(diǎn)已經(jīng)完成任務(wù)
		for（j=1;j		{
			if（lowcost[j]!=0&&G.arc[k][j]			{?????????????????????????????//如果下標(biāo)為k頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)未被加入生成樹權(quán)值
				lowcost[j]=G.arc[k][j];???//將較小的權(quán)值存入lowcost相應(yīng)位置
				adjvex[j]=k;		??????//將下標(biāo)為k的頂點(diǎn)存入adjvex
			}
		}
	}
	printf（“The?whole?length?is:%d“sum）;
}

int?main（void）
{
	MGraph?G;
	printf（“Data?Structure?Design-The?Construction?of?Subway\n“）;
	CreateMGraph（&G）;
	MiniSpanTree_Prim（G）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tThe?End.“）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tSoftWare?College?of?LNTU.“）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tNetWork?Engineer?Class?One?LiuDongnan.“）;
	printf（“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tThank?you.“）;
	return?0;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3329??2013-01-24?00:21??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\pro.c

?????文件?????347716??2014-01-13?21:39??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).doc

?????文件??????42043??2013-01-23?23:20??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\1.jpg

?????文件??????34633??2013-01-24?00:17??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\2.jpg

?????文件??????35795??2013-01-24?00:13??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\3.jpg

?????文件??????79903??2013-01-23?22:40??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\4.jpg

?????文件??????40940??2013-01-24?00:05??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\5.jpg

?????文件??????29184??2013-01-23?20:23??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\Doc1.doc

?????文件??????24008??2013-01-24?00:52??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\文檔?1.doc

?????目錄??????????0??2013-05-03?13:35??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖

?????目錄??????????0??2014-01-13?21:40??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼

-----------?---------??----------?-----??----

???????????????637551????????????????????11