//?graph.cpp?:?Defines?the?entry?point?for?the?console?application.
//?此程序參考《軟件技術基礎》深度優先搜索遍歷算法，圖1.41，并將其實現

#include?“stdafx.h“
#include?“stdio.h“
#include?“graph.h“
#include?“malloc.h“


int?_tmain（int?argc?_TCHAR*?argv[]）
{
	start（）;??/*進入應用程序*/
	printf（“\n?run?OK.......\n“）;
	while（1）;
	return?0;
}

void?start（）?
{
	/*initMatrix（vexMatrixMAXNODE）;*/
	initHeadNode（）;??/*初始化頭節點*/
	//showMatrix（MAXNODE）;
	formlink（）;??/*?根據鄰接矩陣形成鄰接表*/
	debug（2）;	//
}


void?zeroMatrix（int?matrix[][MAXNODE]?int?nodeNum）
{
	int?ij;
	for（i=0;i		for（j=0;j		{
			matrix[i][j]?=?0;
		}
}

void?initHeadNode（）
{
	int?i;

	for（i=0;i	{
		vexlist[i].vexdata?=?i;
		vexlist[i].firstarc?=?NULL;
	}
}

void?debug（int?seq）
{
	if（seq?==?1）
		showMatrix（MAXNODE）;
	if（seq?==?2）
		depthlookThough（vexlist0）;??//從頂點v0開始遍歷
}

void?showMatrix（int?leng）
{
	int?ij;

	for（i=0;i	{
		for（j=0;j		printf（“?%d?“vexMatrix[i][j]）;

		printf（“\n“）;
	}	
}

struct?nodetype?*node_alloc（int?nbvex?int?arcdata）
{
	struct?nodetype?*?pnode=NULL;

	pnode?=?（struct?nodetype?*）malloc（sizeof（struct?nodetype））;
	if（pnode?==?NULL）
	{
		printf（“malloc?err?\n“）;
		return?NULL;
	}

	pnode->nbnode?=?nbvex;
	pnode->arcdata?=?arcdata;
	pnode->next?=?NULL;
	return?pnode;
}



void?formlink（）?//從矩陣形成鄰接表
{
	int?ij;
	struct?nodetype?*?pnode1?=?NULL;
	struct?nodetype?*?temp1;

	for（i=0;i	{
		for（j=0;j		{
			if（vexMatrix[i][j]?==?1）??/*?找到鄰接點*/
			{
				pnode1?=?node_alloc（j1）;
				if（pnode1?==?NULL）
					return;
				
				if（vexlist[i].firstarc?==?NULL）
				{
					vexlist[i].firstarc?=??pnode1;???//?添加i的第一個鄰接點
				}
				else???//添加到vi的鏈表中去
				{
					temp1?=?vexlist[i].firstarc;
					while（temp1->next?!=?NULL）
						temp1?=?temp1->next;
					temp1->next?=?pnode1;
				}
			}
		}
	}
}

int??visited[MAXNODE]?=?{0};??/*?頂點是否已經訪問過*/

//根據鄰接表開始深度優先搜索遍歷
void?depthlookThough（headtype?list[]int?v0）??
{
	int?w;

	visited[v0]?=?1;??
	printf（“?%d?\n“?v0）;

	w?=?first_vex（vexlistv0）;

	while（w?!=?-1）
	{
		if（visited[w]?==?0）
			depthlookThough（vexlistw）;
		w?=?next_vex（vexlist?v0w）;
	}
}

int?first_vex（headtype?list[]int?v0）??//找到v0的第一個未訪問過的鄰接點
{
	struct?nodetype?*?pnode?=?NULL;

	if（vexlist[v0].firstarc?==?NULL）
	{
		printf（“no?first?node?\n?“）;
		return?-1;
	}

	pnode?=?vexlist[v0].firstarc;
	while（pnode->next?!=?NULL）
	{
		if（visited[pnode->nbnode]?==?1）
			pnode?=?pnode->next;
		else
			return?pnode->nbnode;
	}
	if（visited[pnode->nbnode]?==?0）
		return?pnode->nbnode;
	else?
		return?-1;
}

int?next_vex（headtype?list[]?int?v0?int?vi）??//查找v0節點的下一個鄰接點
{
	struct?nodetype?*?pnode?=?NULL;

	if（vexlist[v0].firstarc?==?NULL）
		return?-1;
	
	pnode?=?vexlist[v0].firstarc;
	
	while（pnode->next?!=?NULL）
	{
		if（pnode->nbnode?!=?vi）
			pnode?=?pnode->next;
		else?

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

?????文件??????40960??2008-04-15?05:44??graph\debug\graph.exe

?????文件?????302808??2008-04-15?05:44??graph\debug\graph.ilk

?????文件?????347136??2008-04-15?05:44??graph\debug\graph.pdb

?????文件??????10032??2008-04-15?05:44??graph\graph\Debug\BuildLog.htm

?????文件????????403??2008-04-15?05:44??graph\graph\Debug\graph.exe.embed.manifest

?????文件????????468??2008-04-15?05:44??graph\graph\Debug\graph.exe.embed.manifest.res

?????文件????????385??2008-04-15?05:44??graph\graph\Debug\graph.exe.intermediate.manifest

?????文件??????13291??2008-04-15?05:43??graph\graph\Debug\graph.obj

?????文件????1048576??2008-04-15?05:43??graph\graph\Debug\graph.pch

?????文件?????????69??2008-04-15?05:44??graph\graph\Debug\mt.dep

?????文件??????10525??2008-04-15?05:43??graph\graph\Debug\stdafx.obj

?????文件??????60416??2008-04-15?05:43??graph\graph\Debug\vc80.idb

?????文件?????110592??2008-04-15?05:43??graph\graph\Debug\vc80.pdb

?????文件???????3194??2008-04-15?05:43??graph\graph\graph.cpp

?????文件????????864??2008-04-15?05:41??graph\graph\graph.h

?????文件???????4670??2008-04-14?23:39??graph\graph\graph.vcproj

?????文件???????1427??2008-04-15?05:44??graph\graph\graph.vcproj.D7FF173F3216472.Administrator.user

?????文件???????1294??2008-04-14?23:36??graph\graph\ReadMe.txt

?????文件????????292??2008-04-14?23:36??graph\graph\stdafx.cpp

?????文件????????376??2008-04-14?23:36??graph\graph\stdafx.h

?????文件?????535552??2008-04-15?05:44??graph\graph.ncb

?????文件????????885??2008-04-14?23:36??graph\graph.sln

????..A..H.??????9216??2008-04-15?05:44??graph\graph.suo

?????文件????????467??2008-04-15?05:46??說明.txt

?????目錄??????????0??2008-04-15?05:44??graph\graph\Debug

?????目錄??????????0??2008-04-15?05:44??graph\debug

?????目錄??????????0??2008-04-15?05:43??graph\graph

?????目錄??????????0??2008-04-15?05:19??graph

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

??????????????2503898????????????????????28

............此處省略1個文件信息