#include
#include
#include
#include
#define?INF??10000
typedef?struct
{
	int?Adj;//權值
}AdjMatrix[100][100];//鄰接矩陣
typedef?struct
{
	int		??Vexts[100];//頂點向量
	AdjMatrix?Arcs;//臨街矩陣
	int???????Vexnum;//圖的當前頂點數
}MGraph;
typedef?struct
{
	int?Vext;//頂點
	int?Lowcost;//權值
}CLOSEDGE;
CLOSEDGE??closedge[100];//輔助數組
///克魯斯卡爾
typedef?struct
{
	int?Vext[2];//邊的兩個定點
	int?Adj;	//權值
}EDGE;//一條邊
EDGE?edge[100];//設置一百條邊
int??EdgeLength=0;
void?MiniSpanTree_Prim（MGraph?Gint?u）;
//用普利姆算法從第u個頂點除法構造網G的最小生成樹T
//記錄從頂點集u到v-u的代價最小邊的輔助數組定義
int?LocateVex（MGraph?Gint?u）;
//找到頂點u的位置
int?Mininum（CLOSEDGE?closedge[]int?num）;
//找出下一個節點第k頂點
void?FileRead（MGraph?&G）;
void?MiniSpanTree_Kruakal（MGraph?G）;
//克魯斯卡爾構造最小生成樹
void?RandProduction（MGraph?&G）;
//隨機產生圖
void?Print（MGraph?G）;
void?main（）
{
	MGraph?G;
	srand（（long）time（NULL））;?
	do
	{
	//	FileRead（G）;
		RandProduction（G）;
		Print（G）;
		int?choice=0;
		printf（“請輸入從第幾個點開始構造:\n“）;
		scanf（“%d“&choice）;
		printf（“普利姆算法:\n“）;
		MiniSpanTree_Prim（Gchoice）;
		printf（“克魯斯科爾算法:\n“）;
		MiniSpanTree_Kruakal（G）;
		printf（“\t\t\t....按任意鍵繼續:\n“）;
		getch（）;
		system（“cls“）;
	}while（1）;
}
void?MiniSpanTree_Prim（MGraph?Gint?u）
{
	int?k=0;
	k=LocateVex（Gu）;
	for（int?j=0;j	{
		if（j!=k）
		{
			closedge[j].Vext=u;						//賦值
			closedge[j].Lowcost=G.Arcs[k][j].Adj;	//賦值
		}
	}
	closedge[k].Lowcost=0;//初始U={u};
	for（int?i=1;i	{
		k=Mininum（closedgeG.Vexnum）;//找到下一個節點權值是最小的要并入U集合中
		printf（“邊:%d->%d?權值:%d\n“closedge[k].VextG.Vexts[k]
			G.Arcs[closedge[k].Vext-1][G.Vexts[k]-1]）;
		closedge[k].Lowcost=0;//把第k個頂點并入U集
		for（j=0;j		{
			if（G.Arcs[k][j].Adj				&&（G.Arcs[k][j].Adj>0））//新加的點和原來已有的點的距離比較是不是較小
			{
			//	closedge[j]
				closedge[j].Vext=G.Vexts[k];
				closedge[j].Lowcost=G.Arcs[k][j].Adj;
			}
		}
	}
}
int?LocateVex（MGraph?Gint?u）
{
	for（int?i=0;i	{
		if（u==G.Vexts[i]）
		{
			return?i;//返回位置
		}
	}
	return?-1;
}
int?Mininum（CLOSEDGE?closedge[]int?num）
{
	int?min=0;
	bool?first=true;		//尋找第一個非零點
	for（int?i=0;i	{
		if（closedge[i].Lowcost>0）//在v-u點中找
		{
			if（first）
			{
				min=closedge[i].Lowcost;//這個元素為最小的
				first=false;
			}
			if（closedge[i].Lowcost			{
				min=closedge[i].Lowcost;		//將這個元素標稱最小的
			}
		}
	}
	//已經找到了最小的元素了找到他的位置
	for（int?j=0;j	{
		if（closedge[j].Lowcost==min）
		{
			return?j;
		}
	}
	return?-1;
}
void?FileRead（MGraph?&G）
{
	int?temp=0;
	int?length=0;
	int?i=0;
	int?j=0;
	printf（“請輸入文件名:\n從（1到10）.txt中輸入一個\n“）;
	char?filename[20];
	fflush（stdin）;
	gets（filename）;
	FILE?*in;
	in=fopen（filename“r“）;
	if（!in）
	{
		printf（“文件打開失敗!\n“）;
		exit（0）;
	}
	while（!feof（in））
	{
		fscanf（in“%d“&temp）;
		if（temp==0）
		{
			temp=INF;
		}
		char?ch;
		ch=fgetc（in）;
		G.Arcs[i][j].Adj=temp;
		j++;
		if（ch==‘\n

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

?????文件?????????76??2008-11-15?14:39??最小生成樹\1.txt

?????文件??????????0??2008-11-15?20:14??最小生成樹\2.txt

?????文件??????41984??2008-11-15?14:09??最小生成樹\Debug\Prim_And_Kruskal.bsc

?????文件?????209002??2008-11-15?20:33??最小生成樹\Debug\Prim_And_Kruskal.exe

?????文件?????446756??2008-11-15?20:33??最小生成樹\Debug\Prim_And_Kruskal.ilk

?????文件??????14069??2008-11-15?20:33??最小生成樹\Debug\Prim_And_Kruskal.obj

?????文件??????43520??2008-11-15?14:53??最小生成樹\Debug\Prim_And_Kruskal.opt

?????文件?????222120??2008-11-15?20:20??最小生成樹\Debug\Prim_And_Kruskal.pch

?????文件?????582656??2008-11-15?20:33??最小生成樹\Debug\Prim_And_Kruskal.pdb

?????文件??????11503??2008-11-15?20:33??最小生成樹\Debug\Prim_And_Kruskal.sbr

?????文件??????41984??2008-11-15?20:33??最小生成樹\Debug\vc60.idb

?????文件??????53248??2008-11-15?20:33??最小生成樹\Debug\vc60.pdb

?????文件???????5213??2008-11-15?20:33??最小生成樹\Prim_And_Kruskal.cpp

?????文件???????3525??2008-11-15?14:03??最小生成樹\Prim_And_Kruskal.dsp

?????文件????????540??2008-11-15?11:58??最小生成樹\Prim_And_Kruskal.dsw

?????文件??????50176??2008-11-15?20:33??最小生成樹\Prim_And_Kruskal.ncb

?????文件??????48640??2008-11-15?20:33??最小生成樹\Prim_And_Kruskal.opt

?????文件???????1252??2008-11-15?20:33??最小生成樹\Prim_And_Kruskal.plg

?????目錄??????????0??2008-11-15?20:33??最小生成樹\Debug

?????目錄??????????0??2008-11-15?20:33??最小生成樹

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

??????????????1776264????????????????????20