#include
#define?MAX_VERTEX_NUM?20???//最多頂點個數?為?20個
#define?XX?99??//表示極大值，即∞
typedef?struct?ArcNode{
	//定義鄰接矩陣中的節點
	int?adj;????//存儲權值，若無權值則為∞
}ArcNode;
typedef?struct{
	//定義鄰接矩陣
	char?vertex[MAX_VERTEX_NUM];???//一位數組存放頂點
	ArcNode?arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];??//二維數組表示頂點之間的關系
	int?vexnum;??//頂點數
	int?arcnum;??//弧數
}AdjMatrix;
void?CreateGraph（AdjMatrix*?m）;
void?PrintGraph（AdjMatrix*?m）;
void?dfs_graph（AdjMatrix?*?graph?bool?visited[]?const?int?i）;
void?g_depth_first_search（AdjMatrix?*?graph）;
void?init_prim（AdjMatrix?*?graph?AdjMatrix?*?prim_tree）;
void?Prim（AdjMatrix?*?graph?AdjMatrix?*?prim_tree）;
bool?Connectivity_Warshall（AdjMatrix*?m）;
int?main（）
{
	AdjMatrix?M;
	AdjMatrix?prim_tree;

	CreateGraph（&M）;

	PrintGraph（&M）;

	g_depth_first_search（&M）;

	Prim（&M?&prim_tree）;

	if（Connectivity_Warshall（&M））
		printf（“是連通樹\n“）;
	else
		printf（“不是連通樹\n“）;
	return?0;
}
void?CreateGraph（AdjMatrix*?m）
{
	//創建連通圖
	int?iixjy;

	printf（“請輸入圖的頂點個數：\n“）;
	scanf（“%d“&m->vexnum）;
	printf（“請輸入圖的頂點：\n“）;
	getchar（）;
	for（i?=?0;?i?vexnum;?i++）
	{
		m->vertex[i]?=?getchar（）;	
	}
	printf（“請輸入圖的頂點關系：\n“）;
	for（ix?=?0;?ix?vexnum;?ix++）{
		for（jy?=?0;?jy?vexnum;?jy++）{
			scanf（“%d“&m->arcs[ix][jy].adj）;
			if（getchar（）?==?‘?‘）
		?????	continue;
	????	else
			????break;
		}
	}
}
//輸出圖的鄰接矩陣
void?PrintGraph（AdjMatrix*?m）
{
	int?ixjy;
	printf（“圖的（鄰接矩陣）遍歷結果：\n“）;
	for（ix?=?0;?ix?vexnum;?ix++）{
		printf（“%c???“m->vertex[ix]）;
		for（jy?=?0;?jy?vexnum;?jy++）{
			printf（“%-5d“m->arcs[ix][jy].adj）;
		}
		printf（“\n“）;
	}
}
void?g_depth_first_search（AdjMatrix?*?graph）
{
????bool?visited[MAX_VERTEX_NUM];
????int?i;
	printf（“深度遍歷結果如下：“）;
????for?（?i?=?0;?i?vexnum;?i++?）
????????visited[i]?=?false;
????visited[0]?=?true;
????dfs_graph（graph?visited?0）;
????printf（“\n“）;
}
void?dfs_graph（AdjMatrix?*?graph?bool?visited[]?const?int?i）
{
????int?j;
????printf（“%c\t“?graph->vertex[i]）;
????for?（?j?=?0;?j?vexnum;?j++?）//依次檢查矩陣
????{
????????if?（?graph->arcs[i][j].adj?!=?XX?&&?!visited[j]?）//i?代表矩陣的行?j?代表矩陣的列
????????{
????????????visited[j]?=?true;
????????????dfs_graph（graph?visited?j）;
????????}
????}
}

//判斷是否為連通樹
bool?Connectivity_Warshall（AdjMatrix*?m）
{
?AdjMatrix?judgemat;
?judgemat.vexnum=m->vexnum;
?int?ij;
?for（i=1;i<=m->vexnum;i++）
?{
??for（j=1;j<=m->vexnum;j++）
??{
???if（m->arcs[i][j].adj）
????judgemat.arcs[i][j].adj=1;?//初始化判斷矩陣
???else
????judgemat.arcs[i][j].adj=0;
??}
??judgemat.arcs[i][j].adj=1;
?}

?for（int?x=1;x<=judgemat.vexnum;x++）?//采用warshall算法判斷圖的連通性。注意下標。
?{
??for（int?y=1;y<=judgemat.vexnum;y++）
??{
???if（judgemat.arcs[x][y].adj）
???{
????for（int?z=1;z<=judgemat.vexnum;z++）
????{
?????if（judgemat.arcs[z][x].adj）
??????judgemat.arcs[z][y].adj=1;
????}
???}
??}
??//print（judgemat）;
?}
?for（i=1;i<=judgemat.vexnum;i++）
?{
??for（j=1;j<=judgemat.vexn

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

?????文件??????16883??2018-12-14?09:54??數據結構試驗4\第四次實驗.docx

?????文件????????528??2018-12-20?22:38??數據結構試驗4\帶權連通圖.dsw

?????文件??????48640??2018-12-20?22:38??數據結構試驗4\帶權連通圖.opt

?????文件?????142003??2019-03-08?12:28??數據結構試驗4\圖.docx

?????文件??????41984??2018-12-20?21:39??數據結構試驗4\Debug\vc60.idb

?????文件??????53248??2018-12-20?21:14??數據結構試驗4\Debug\vc60.pdb

?????文件?????451584??2018-12-20?21:14??數據結構試驗4\Debug\帶權連通圖.pdb

?????文件?????203700??2018-12-15?10:38??數據結構試驗4\Debug\帶權連通圖.pch

?????文件?????206840??2018-12-20?21:14??數據結構試驗4\Debug\帶權連通圖.ilk

?????文件?????184387??2018-12-20?21:14??數據結構試驗4\Debug\帶權連通圖.exe

?????文件??????11545??2018-12-20?21:14??數據結構試驗4\Debug\帶權連通圖.obj

?????文件???????1285??2018-12-20?21:14??數據結構試驗4\帶權連通圖.plg

?????文件??????33792??2018-12-20?17:47??數據結構試驗4\帶權連通圖.ncb

?????文件???????4756??2018-12-20?21:14??數據結構試驗4\帶權連通圖.cpp

?????文件???????3451??2018-12-20?22:38??數據結構試驗4\帶權連通圖.dsp

?????目錄??????????0??2018-12-14?10:32??數據結構試驗4\Debug

?????目錄??????????0??2018-12-14?09:54??數據結構試驗4

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

??????????????1404626????????????????????17