depth_first_search.c

这是一个在数据结构当中深度优先遍历程序

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

#define MAX_VERTEX_NUM 20                        //最大顶点个数

typedef struct ArcNode{
	int               adjvex;                    //该弧所指向的顶点的位置
	struct ArcNode    *nextarc;                  //指向下一条弧的指针
}ArcNode;

typedef struct VertexNode{
	int               vertex;                    //顶点的编号
	ArcNode           *firstarc;                 //指向第一条依附该顶点的弧的指针
}VertexNode;

typedef struct{
	VertexNode        adjlist[MAX_VERTEX_NUM];
	int               vexnum, arcnum;             //图的当前顶点数和弧数
}graph;

//从键盘输入图的顶点数，边数以及每条边所连接的顶点，创建一个图
void create_graph(graph *g)
{
	int      n, e;
	int      i, j, k;
	ArcNode  *p, *q;

	printf("创建一个图:\n");
	printf("顶点数:");
	scanf("%d",&n);
	printf("边数:");
	scanf("%d",&e);

	g->vexnum = n;
	g->arcnum = e;
	
	//初始化adjlist[i]链表
	for(i=1; i<=n; i++)
	{
		g->adjlist[i].vertex = i;
		g->adjlist[i].firstarc = NULL;
	}

	for(k=0; k<e; k++)
	{
		printf("第%d条边(每条边的节点编号从1到%d):",k+1,n);
		scanf("%d %d",&i,&j);    //若图有n顶点,则输入顶点的编号范围为1至n
		p=(ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j ;

		//将p插入到adjlist[i]链表的末尾
		p->nextarc = NULL ;
		if(g->adjlist[i].firstarc == NULL)
			g->adjlist[i].firstarc = p ;
		else
		{
			q = g->adjlist[i].firstarc ;
			while(q->nextarc)
				q = q->nextarc ;
			q->nextarc = p;
		}
	}
}

void display_graph(graph *g)                     //输出一个图          
{
	int     i, have;
	ArcNode *p;

	printf("\n输出图:\n");

	for(i=1; i<=g->vexnum; i++)
	{
		p = g->adjlist[i].firstarc ;
		have = 0 ;     //have变量是为了将同一顶点所连接的边输出到一行,也可不使用have变量
		while(p != NULL)        
		{
			printf("(%d,%d)",i,p->adjvex);
			p = p->nextarc ;
			have = 1 ;		
		}
		if(have == 1)
			printf("\n");
	}
	printf("\n");
}

//深度优先遍历图的非递归算法,调用一次dfs算法之后,可以将从开始顶点所连通的顶点都访问到
void dfs(graph g, int v)   
{       
	int     i  ;
	int     top = 0 ;
	int     stack[MAX_VERTEX_NUM];
	int     visited[MAX_VERTEX_NUM];
	ArcNode *p ;

	for(i=0; i<=g.vexnum; i++)
		visited[i] = 0 ;
	
	printf("%d ",v);             //访问初始顶点v,并修改visited[v]的值
	visited[v] = 1 ;

	top = top + 1 ;              //将顶点v进栈
	stack[top] = v ;

	while(top >= 1)               //当栈不为空时,即top>=1时
	{
		v = stack[top];          //取栈顶顶点
		p = g.adjlist[v].firstarc ;
		
		//找一个与栈顶顶点相连且未被访问的顶点
		while((p != NULL) && (visited[p->adjvex]==1))
		    p = p->nextarc ; 
		
		if(p == NULL)            //若所找的顶点已经没有邻接节点时,执行一次出栈
			top = top - 1 ;
		else                     
		{
			v = p->adjvex ;      
			printf("%d ",v);     //对所找的顶点进行访问
			visited[v] = 1 ;     //修改visited的值
			top = top + 1 ;      //并将该顶点进栈
			stack[top] = v ;
		}
	}
	printf("\n");
}

void main( )
{
	graph g;			
	create_graph(&g);                    //创建一个图
	display_graph(&g);                   //显示所创建的图
	printf("\n深度优先遍历序列为:\n");
	dfs(g,1);                            //从第1个顶点开始进行深度优先遍历图
}