// 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);
	}