#include?


#define?INFINITY?INT_MAX??
#define?MAX_VERTEX_NUM?20??

enum?GraphKind{DGDNUDGUDN};??????//圖的類型



?
typedef?struct?
{
????int?weight;?????????????????????????????????????//權(quán)值
}ArcCellAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];?//?二維數(shù)組?

typedef?struct??
{?
????char?vexs[MAX_VERTEX_NUM];??
????AdjMatrix?arcs;??
????int?vexnumarcnum;??
????GraphKind?kind;??
}Graph;?


int?LocateVex（Graph?Gchar?u）?
{??
????for（int?i=0;i????????if（G.vexs[i]==u）?
????????????return?i;?
????????return?-1;?
}?

void?CreateUDN（Graph?&G）?
{??
????
	int?ijk;
	int?weight;
????char?vavb;
????printf（“請(qǐng)輸入無向圖G的頂點(diǎn)數(shù)邊數(shù)\n“）;?
????scanf（“%d%d“&G.vexnum&G.arcnum）;?
	getchar（）;

????printf（“請(qǐng)輸入?%d?個(gè)頂點(diǎn)的值:\n“G.vexnum）;?
????for（i=0;i	{
		printf（“請(qǐng)輸入第?%d?個(gè)頂點(diǎn)的值:\n“i+1）;
????????scanf（“%c“&G.vexs[i]）;?
		getchar（）;
	}
	
????for（i=0;i????????for（j=0;j????????{?
			if（i!=j）
				G.arcs[i][j].weight=1000;
			else
				G.arcs[i][j].weight=0;??
????????}?
		
????????printf（“請(qǐng)輸入?%d?條邊的兩個(gè)頂點(diǎn)及邊權(quán)值:\n“G.arcnum）;?
????????for（k=0;k????????{?
			printf（“請(qǐng)輸入第?%d?條邊的兩個(gè)頂點(diǎn)及權(quán)值:\n“k+1）;
????????????scanf（“%c%c%d“&va&vb&weight）;
			getchar（）;
			
????????????i=LocateVex（Gva）;?
????????????j=LocateVex（Gvb）;?
????????????G.arcs[i][j].weight=G.arcs[j][i].weight=weight;?//?無向圖?
????????}?

????????G.kind=UDN;?
}?

int?FirstAdjVex（Graph?Gchar?v）?
{??
????int?ik;?
????k=LocateVex（Gv）;?
????for（i=0;i????????if（G.arcs[k][i].weight!=0）?
????????????return?i;?
????????return?-1;?
}?
?
int?NextAdjVex（Graph?Gchar?vchar?w）?
{??
????int?ik1k2;?
????k1=LocateVex（Gv）;??
????k2=LocateVex（Gw）;??
????for（i=k2+1;i????????if（G.arcs[k1][i].weight!=0）?
????????????return?i;?
????????return?-1;?
}?

void?MiniSpanTree_P（Graph?G?char?u）
{
	struct
	{
		char	adjvex;				//?U集中的頂點(diǎn)序號(hào)
		int????lowcost;				//?邊的權(quán)值
	}?closedge?[MAX_VERTEX_NUM];

	int?ijknlm;
	
	//用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹

	k?=?LocateVex?（Gu）;?
	
	for?（j=0;j		if?（j!=k）?
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].weight;
		}

		closedge[k].lowcost?=?0;			//?初始，U＝{u}

	
		for?（m=1;m		{
			k=100;
			for（i=0;i			{
				if（（closedge[i].lowcost!=0）&&（k>closedge[i].lowcost））
				{
					k=closedge[i].lowcost;
					l=i;
				}
			}?
									
			printf（“%c%c\n“closedge[l].adjvex?G.vexs[l]）;
			
			closedge[l].lowcost?=?0;????//?第k頂點(diǎn)并入U(xiǎn)集

			for?（j=0;j				if?（G.arcs[l][j].weight				{
						closedge[j].adjvex=G.vexs[l];
						closedge[j].lowcost=G.arcs[l][j].weight;
				}
				
		}
}

void?main（）
{
	Graph?G;
	CreateUDN（G）;
	MiniSpanTree_P（G‘1‘）;
	
}

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件?????184394??2008-11-30?22:27??Prime\Debug\Prime.exe

?????文件?????353280??2008-11-30?22:27??Prime\Debug\Prime.pdb

?????文件?????184393??2008-12-01?12:31??Prime\Debug\Test.exe

?????文件???????9429??2008-12-01?12:31??Prime\Debug\Test.obj

?????文件?????443392??2008-12-01?12:31??Prime\Debug\Test.pdb

?????文件??????53248??2008-12-01?12:31??Prime\Debug\vc60.pdb

?????文件???????3035??2008-12-01?12:31??Prime\Prime.cpp

?????文件???????4210??2008-11-30?22:26??Prime\Prime.dsp

?????文件????????535??2008-11-30?22:26??Prime\Prime.dsw

?????文件??????25600??2008-11-30?22:36??Prime\Prime.ncb

?????文件??????????0??2008-11-30?22:36??Prime\Prime.plg

?????文件???????3377??2008-12-01?12:29??Prime\Test.dsp

?????文件????????533??2008-12-01?12:36??Prime\Test.dsw

?????文件??????41984??2008-12-01?12:36??Prime\Test.ncb

?????文件??????48640??2008-12-01?12:36??Prime\Test.opt

?????文件????????736??2008-12-01?12:31??Prime\Test.plg

?????目錄??????????0??2009-09-21?22:09??Prime\Debug

?????目錄??????????0??2009-09-21?22:09??Prime

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

??????????????1356786????????????????????18