12.cpp

用DFS算法遍历图

//图的邻接表存储结构
#include <malloc.h>
#include <stdio.h>

#define MAXVEX 30

typedef struct edgenode
{
	int adjvex;					//邻接点序号
	struct edgenode *next;		
}edgenode;

typedef struct vexnode 
{
	char data;					//节点信息
	struct edgenode *link;
}*adjlist;

int n;
//产生图的邻接表表示

void creategraph(adjlist &g)
{
	int e,i,s,d;	
	edgenode *p,*q;
	printf("请输入节点数（n）和边数（e）：");
	scanf("%d%d",&n,&e);
	g=(adjlist)malloc(n*sizeof(adjlist));
	for(i=0;i<n;i++)			//初始化
	{
		getchar();
		printf("\n请输入该节点所代表的字符:",i);
		scanf("%c",&g[i].data);
		g[i].link=0;
	}

	for(i=0;i<e;i++)
	{
		printf("\n第%d条边=>\t起点和终点",i);
		scanf("%d%d",&s,&d);

		p=(edgenode*)malloc(sizeof(edgenode));
		q=(edgenode*)malloc(sizeof(edgenode));
	    p->adjvex=d;
        q->adjvex=s;			//无向图
        
		p->next=g[s].link;
		g[s].link=p;

		q->next=g[d].link;
		g[d].link=q;
	}
}

//遍历邻接表表示的一个图
void travgraph(adjlist g)
{
	int i;
	edgenode *p;

	printf("遍历图的结果如下：\n");
	for(i=0;i<n;i++)
	{
		printf("[%d,%c]=>",i,g[i].data);
		p=g[i].link;

		while(p!=0)
		{
			printf("(%d)-->",p->adjvex);
			p=p->next;
		}
		printf("^\n");
	}

}


//实现dfs的非递归算法
int visited[MAXVEX];
void dfs(adjlist g,int v)	//隐含全局变量:int n,为顶点数
{
	edgenode *stack[MAXVEX],*p;

	int top=0;
	visited[v]=1;

	printf("%d",v);
	
	p=g[v].link;
	while((top>0)||(p!=0))
	{
		while(p!=0)			//深度遍历，直到进行不下去为止。
		{
			if(visited[p->adjvex]!=0)		//若已被访问过
			{
				p=p->next;
			}
			else							//若未被访问过，就访问
			{
				printf("%d",p->adjvex);
				visited[p->adjvex]=1;
				top++;						//将访问过的节点入栈
				stack[top]=p;
				p=g[p->adjvex].link;
			}
		}

		if(top>0)
		{
			p=stack[top];
			top--;				//退栈，回溯查找被访问过结点未被访问过的邻结点
			p=p->next;
		}
	}
}

void main()
{
	adjlist g=0;
	int i=0;
	creategraph(g);
	travgraph(g);
	for(i=0;i<n;i++)		//初始化visited
	{
		visited[i]=0;
	}
	printf("\n按照非递归算法,输出该图为：\n");
	for(i=0;i<n;i++)		//初始化visited
	{
		visited[i]=0;
	}
	dfs(g,0);
	printf("\n");
	return;
}