//?poquan.cpp?:?定義控制臺應用程序的入口點。
//

#include?“stdafx.h“


#include?
#include?

int?n;??//存儲結點數
int?e;??//存儲邊數
#define?maxvertexnum?50??//最大結點數

int?visited[maxvertexnum];//標記結點是否被訪問
float?larr[maxvertexnum][maxvertexnum];//存儲圖的邊的權值信息
typedef??struct??{?int?ijw;}?myedge;??//頂點信息為頂點編號，權是整數
myedge*?edge;


void?createtree（）
{
??int?ij;
??for（i=0;i	??for（j=0;j		??larr[i][j]=0;??//權值為0表示沒有該邊，即兩個結點不鄰接
??for（i=0;i	??visited[i]=0;
??printf（“請輸入邊數\n“）;
??scanf?（?“%d“&e）;//輸入邊數
??printf（“請輸入頂點數\n“）;
??scanf?（?“%d“&n）;//輸入頂點數
??edge=（myedge*）malloc（sizeof（myedge）*e）;
??
??printf（“請依次輸入邊的兩個頂點的編號和邊權值\n“）;
??for（i=1;i<=e;i++）??//輸入e條邊的頂點和權值
??{scanf（“%d%d%d“&edge[i].i&edge[i].j&edge[i].w）;
??larr[edge[i].i][edge[i].j]=edge[i].w;
??larr[edge[i].j][edge[i].i]=edge[i].w;
??}
}

//connect（k）是測試去掉邊edge[k]后是否仍然連通，即是否能夠DFS遍歷完全
int?connect（?int?k）??
{??
????int?temp=edge[k].w;??//先保存以備恢復
????edge[k].w=0;??//嘗試刪除邊
	larr[?edge[k].i][?edge[k].j]=0;
	larr[?edge[k].j][?edge[k].i]=0;
	//非遞歸dfs遍歷????
???//初始化?
???int?top?=?-1?;?
???int?stack[1000];?//假設棧空間夠用??
???int?i;
???for（i=0;i???{
	??visited[i]=0;?
???}
???//從0結點開始遍歷
????visited[0]?=?1?;??
	int?count=1;?//訪問的結點數
????stack[++top]?=?0?;??
????while?（?top?!=?-1）??
????{??
????????int?v?=?stack[top]?;??
????????for?（?i?=?0?;?i?????????{??
????????????if?（larr[v][i]?!=0?&&!visited[i]）??
????????????{??
???????????????
????????????????visited[i]?=?1?;?
				count++;
????????????????stack[?++top?]?=?i?;??
????????????????break?;??
????????????}??
????????}??
????????if（?i?==?n）??
????????{??
????????????top?--?;??
????????}??
????}
????if（count==n）??//仍然連通
	{
		return?1;
	}
	else
	{
	edge[k].w=temp;??//恢復邊
	larr[?edge[k].i][?edge[k].j]=temp;
	larr[?edge[k].j][?edge[k].i]=temp;
	return?0;
	}	
??????
}
void??spntree（）
{?
??
??int?ij;
????
??for（i=2;i<=e;i++）??//按權值大小，對邊進行逆序排序
??????{?edge[0]=edge[i];
????????j=i-1;
????????while（edge[0].w>edge[j].w）??edge[j+1]=edge[j--];
????????edge[j+1]=edge[0];
???????}
	int?k=1;
	int?eg=e;
	while（eg>=n）?//破圈，直到邊數e=n-1
	{??if（connect（k））??//刪除邊edge[k]，若仍連通
		{edge[k].w=0;eg--;}??//權值置0表示該邊被刪除
	???k++;??//測試下一條邊
	}//while
	printf（“最小生成樹如下：\n“）;
	for?（i=1;i<=e;i++）
	{
		if（edge[i].w!=0）
		{printf（“%d<->%d??%d\n“edge[i].iedge[i].jedge[i].w）;}
	}
}//算法結束
void?main（）
{
	createtree（）;
	spntree（）;
}

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-03-02?08:36??12.poquan\
?????目錄???????????0??2015-03-02?08:42??12.poquan\poquan\
?????目錄???????????0??2015-03-02?08:36??12.poquan\poquan\Debug\
?????文件???????30720??2015-03-02?08:36??12.poquan\poquan\Debug\poquan.exe
?????文件??????313448??2015-03-02?08:36??12.poquan\poquan\Debug\poquan.ilk
?????文件??????429056??2015-03-02?08:36??12.poquan\poquan\Debug\poquan.pdb
?????目錄???????????0??2015-03-02?08:36??12.poquan\poquan\ipch\
?????目錄???????????0??2015-03-02?08:36??12.poquan\poquan\ipch\poquan-1033e1d7\
?????文件?????2359296??2015-03-02?08:36??12.poquan\poquan\ipch\poquan-1033e1d7\poquan-6c597ee0.ipch
?????目錄???????????0??2015-03-02?08:36??12.poquan\poquan\poquan\
?????目錄???????????0??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\
?????文件????????3026??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\CL.read.1.tlog
?????文件?????????706??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\CL.write.1.tlog
?????文件????????1402??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\cl.command.1.tlog
?????文件???????????2??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link-cvtres.read.1.tlog
?????文件???????????2??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link-cvtres.write.1.tlog
?????文件???????????2??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link.28396-cvtres.read.1.tlog
?????文件???????????2??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link.28396-cvtres.write.1.tlog
?????文件???????????2??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link.28396.read.1.tlog
?????文件???????????2??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link.28396.write.1.tlog
?????文件????????1544??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link.command.1.tlog
?????文件????????3416??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link.read.1.tlog
?????文件?????????768??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\link.write.1.tlog
?????文件?????????364??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\mt.command.1.tlog
?????文件?????????286??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\mt.read.1.tlog
?????文件?????????286??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\mt.write.1.tlog
?????文件?????????406??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\poquan.exe.embed.manifest
?????文件?????????472??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\poquan.exe.embed.manifest.res
?????文件?????????381??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\poquan.exe.intermediate.manifest
?????文件??????????54??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\poquan.lastbuildstate
?????文件????????5102??2015-03-02?08:36??12.poquan\poquan\poquan\Debug\poquan.log
............此處省略21個文件信息