dfs.cpp

用dfs非递归算法遍历图。创 建图是用链表来实现。

// DFS.cpp : Defines the entry point for the console application.
//

#include <iostream.h>
#include <malloc.h>
#define Vnum 20
typedef struct arcnode          //边结构
{
	int adjvex;
	struct arcnode *nextarc;
}arcnode;
typedef struct vexnode           //顶点
{
	int vertex;  //编号
	arcnode *firstarc; 
}adjlist[Vnum];
typedef struct graphs
{
	adjlist adj;
	int vexn,arcn;
}graph;
void creat(graph *g)
{
	int n,e,i,j,k;
	arcnode *p;
	cout<<"请输入顶点数：";
	cin>>n;
	cout<<"请输入边数：";
	cin>>e;
	g->vexn=n;g->arcn=e;
	for(i=0;i<n;i++)
	{
		g->adj[i].vertex=i;   //编号
		g->adj[i].firstarc=NULL;
	}
	for(k=0;k<e;k++)
	{
		cout<<"第"<<k+1<<"条边：(边的尾结点号，头结点号)";
		cin>>i>>j;
		p=(arcnode *)malloc(sizeof (arcnode));
		p->adjvex=j;
		p->nextarc=g->adj[i].firstarc;
		g->adj[i].firstarc=p;          //将p插在链表的最前边
	}
}



void dfs(graph *g,int v)
{
	int i;
	arcnode *p;
	int visited[Vnum],top=-1,stack[Vnum];
	for(i=0;i<g->vexn;i++)
	{
		visited[i]=0;
	}//初始化标志数组
	cout<<v<<" ";
	top++;
	stack[top]=v;
	visited[v]=1;//将v压入堆栈，标志位置1
	while(top>=0)
	{
		v=stack[top];
		top--;//取栈顶顶点
		p=g->adj[v].firstarc;
		while(p!=NULL && visited[p->adjvex]==1)
		  p=p->nextarc;
		if(p==NULL)
			top--;
		else
		{
			v=p->adjvex;
			cout<<v<<" ";
			visited[v]=1;
			top++;
			stack[top]=v;
		}
	}
}
	void main()
	{
		graph *g;
		g=(graph*)malloc(sizeof (graph));
		creat(g);
		cout<<"深度优先搜索顺序："<<endl;
		dfs(g,0);
	}