深度遍历有向图

问题：用标记来记录是否访问过，这个是个关键点。当然也可以用栈，思想是每访问一个顶点就入栈，接着访问这个顶点的下一个顶点，最后出栈，看出栈的顶点有没有下一个顶点，如果有就继续访问。如此重复，直到栈空。

还有一点就是用到了递归思想。很像二叉树的前序遍历。

代码：

#include <iostream>
#include <cstdlib>
using namespace std;

#define MAXV 20

typedef struct edgeNode
{
	int data;
	struct edgeNode *next;
}edgeList;

typedef struct headNode
{
	char vex;
	edgeList *firstNode;
}headList;

typedef struct graph           //定义邻接表结构
{
	headList arr[MAXV];
	int v,e;
}*adjGraph;


void createAdjGraph(adjGraph &ag)
{
	char c;
	int p,q;
	edgeList *s;
	cout<<"please input the num of v and e:";
	cin>>ag->v>>ag->e;

	for(int i=0;i<ag->v;i++)             //初始化头节点
	{
		cout<<"please input vex:";
		cin>>c;
		ag->arr[i].vex=c;
		ag->arr[i].firstNode=NULL;
	}

	for(int j=0;j<ag->e;j++)
	{
		cout<<"please input two vexs:";
		cin>>p>>q;
		s=(edgeList *)malloc(sizeof(struct edgeNode));
		s->data=p;
		s->next=ag->arr[q].firstNode;
		ag->arr[q].firstNode=s;
	}
}

void showAdjGraph(adjGraph ag)
 {
	for(int i=0;i<ag->v;i++)
	{
		cout<<ag->arr[i].vex<<"  ";
		while(ag->arr[i].firstNode!=NULL)
		{
			cout<<ag->arr[i].firstNode->data<<" ";
			ag->arr[i].firstNode=ag->arr[i].firstNode->next;
		}
		cout<<endl;
	}
}

void DFS(adjGraph ag,int v,int *visited)
{
	 edgeList *s;
	 int w;
	 visited[v]=1;
	 s=ag->arr[v].firstNode;
	 cout<<ag->arr[v].vex<<"->";
	 while(s!=NULL)
	 {
		 w=s->data;
		 if(visited[w]==0)
			 DFS(ag,w,visited);
		 s=s->next;
	 }
	 
}
void DFSTraversal(adjGraph ag)
{
	int visited[MAXV];

	for(int i=0;i<ag->v;i++)
	{
		visited[i]=0;
	}

	for(int j=0;j<ag->v;j++)
	{
		if(visited[j]==0)
		   DFS(ag,j,visited);
	}
	cout<<endl;
}
int main()
{
	adjGraph ag;
	ag=(adjGraph)malloc(sizeof(struct graph));
	cout<<"创建图:"<<endl;
	createAdjGraph(ag);
	cout<<"输出图"<<endl;
	showAdjGraph(ag);
	cout<<"深度遍历图:"<<endl;
	DFSTraversal(ag);
	return 0;
}

 运行结果：