图的深度优先搜索遍历c代码实现

这是一个图的深度优先搜索遍历的C代码的具体实现，详细情况请参见 压缩包中的“说明.txt”

// 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个文件信息