#include?“LGraph.h“

Status?CreateGraph（AMLGraph?&G）//利用鄰接多重表創(chuàng)建圖
{
	FILE?*fp*fq;
	int?i;
	int?x1y1;//用來儲存輸入的兩個頂點的位置
	PEBox?p;
	if（（fp=fopen（“Edge.txt““r“））==NULL）//打開文件
????{
????????printf（“Open?Failed!“）;
????}
????if（（fq=fopen（“City.txt““r“））==NULL）//打開文件
????{
????????printf（“Open?Failed!“）;
????}
	G.g=（VexBox*）malloc（MAX_VERTEX_NUM*sizeof（VexBox））;//為鄰接多重表的頭結(jié)點申請空間
	if（!G.g）
????????return?0;
	G.vexnum=25;//結(jié)點個數(shù)
	G.edgenum=30;//邊數(shù)
	for（i=0;i????{
		fscanf（fq“%s“&G.g[i].city）;
		G.g[i].data=i+1;
		G.g[i].firstedge=NULL;
	}
	for（i=0;i????{
		p=（PEBox）malloc（sizeof（EBox））;//新申請一個表結(jié)點來儲存邊的信息
		if（!p）?return?0;
		p->ilink=NULL;
		p->jlink=NULL;
		fscanf（fp“%d“&x1）;
		fscanf（fp“%d“&y1）;
		x1--;
		y1--;
		p->ivex=x1;
		p->jvex=y1;
		p->ilink=G.g[x1].firstedge;//將表結(jié)點插入到鄰接多重表中
		G.g[x1].firstedge=p;
		p->jlink=G.g[y1].firstedge;
		G.g[y1].firstedge=p;
	}
	return?OK;
}
//深度遍歷并給出序列
Status?DFSTraverse（AMLGraph?&Gint?yint?visited[]）
{
????PEBox?w;
????printf（“%s??“G.g[y].city）;
????visited[y]=1;//標(biāo)記為已遍歷
????w=G.g[y].firstedge;//指向該位置下的第一個表結(jié)點
	while（w）{
		if（w->ivex==y）{//查找相應(yīng)數(shù)據(jù)的位置
			if（visited[w->jvex]==0）{//判斷是否遍歷過
			DFSTraverse（Gw->jvexvisited）;//未被遍歷過則深度優(yōu)先遍歷該結(jié)點
			}
			w=w->ilink;//指針后移
		}
		else{
			if（visited[w->ivex]==0）{//判斷是否遍歷過
			DFSTraverse（Gw->ivexvisited）;//未被遍歷過則深度優(yōu)先遍歷該結(jié)點
			}
			w=w->jlink;//指針后移
			}
????}
????return?OK;
}
//查詢a在鄰接多重表中的位置
Status?Locate（AMLGraph?Gchar?a[]）
{
	int?i;
	for（i=0;i		if（strcmp（G.g[i].citya）==0）
????????????return?i;
	}
	return?ERROR;
}
//廣度遍歷并給出序列

void?BFSTraverse（AMLGraph?G）
{
	linkQueue?Q;
	int?ab;
	int?visi[MAX_VERTEX_NUM];//標(biāo)志數(shù)組
	char?y[20];
	for（a=0;a		visi[a]=0;
	InitQueue（Q）;//創(chuàng)建隊列
	printf（“please?input?the?starting?point：“）;
	scanf（“%s“&y）;
	a=Locate（Gy）;//查找y在鄰接多重表的位置
	visi[a]=1;//標(biāo)記為已遍歷
	EnQueue（Qa）;//進隊列
	while（Q.front!=Q.rear）//隊不為空則進行循環(huán)
????{
????????DeQueue（Qa）;//隊頭出隊列
????????Print（GG.g[a].city）;
	????for（b=FirstAdjVex（GG.g[a].city）;b>=0;b=NextAdjVex（GG.g[a].cityG.g[b].city））
????????{
????????????if（visi[b]==0）
????????????{
????????????????visi[b]=1;
????????????????EnQueue（Qb）;
????????????}
????????}
????}
}
//深度遍歷并給出生成樹
Status?DFSTree（AMLGraph?&Gint?yint?visited[]int?p）
{
????PEBox?w;
????printf（“<%s%s>\t“G.g[p].cityG.g[y].city）;
????visited[y]=1;//標(biāo)記為已遍歷
????w=G.g[y].firstedge;//指向該位置下的第一個表結(jié)點
	while（w）
	{
		if（w->ivex==y）//查找相應(yīng)數(shù)據(jù)在表結(jié)點中的位置
????????{
			if（visited[w->jvex]==0）//判斷是否遍歷過
			{
			????DFSTree（Gw->jvexvisitedy）;//對該結(jié)點深度優(yōu)先遍歷
			}
			w=w->ilink;//指針后移
		}
		else
		{
			if（visited[w->ivex]==0）//判斷是否遍歷過
			{
			????DFSTree（Gw->ivexvisitedy）;//對該結(jié)點深度優(yōu)先遍歷
			}
			w=w->jlink;//指針后移
????????}
????}
????return?OK;
}
//廣度優(yōu)先生成樹
Status?BFSTree（AMLGraph?&G?int?s[]）
{
	linkQueue?Q;
	int?a;
	char?y[30];
	EBox?*p;
	InitQueue（Q）;
?

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2019-09-10?12:15??LGraph\
?????文件?????????158??2015-02-19?10:39??LGraph\City.txt
?????文件?????????184??2018-01-13?11:12??LGraph\Edge.txt
?????文件????????1229??2018-01-12?11:46??LGraph\LGraph.cbp
?????文件????????5440??2018-01-17?17:46??LGraph\LGraph.cpp
?????文件?????????356??2019-01-14?16:44??LGraph\LGraph.depend
?????文件????????1219??2018-01-18?10:19??LGraph\LGraph.h
?????文件?????????505??2019-01-17?10:48??LGraph\LGraph.layout
?????文件?????????544??2018-01-12?11:40??LGraph\Queue.cpp
?????文件?????????517??2018-01-12?11:40??LGraph\Queue.h
?????目錄???????????0??2019-09-10?12:15??LGraph\bin\
?????目錄???????????0??2019-09-10?12:15??LGraph\bin\Debug\
?????文件??????978310??2019-01-14?16:44??LGraph\bin\Debug\LGraph.exe
?????文件????????2555??2018-01-17?16:57??LGraph\main.cpp
?????目錄???????????0??2019-09-10?12:15??LGraph\obj\
?????目錄???????????0??2019-09-10?12:15??LGraph\obj\Debug\
?????文件???????10158??2019-01-14?16:44??LGraph\obj\Debug\LGraph.o
?????文件????????3214??2019-01-14?16:44??LGraph\obj\Debug\Queue.o
?????文件???????13379??2019-01-14?16:44??LGraph\obj\Debug\main.o