#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define MAX_VERTEX_NUM 20
typedef enum{D,U}kind;
typedef struct ArcNode
{
   int adjvex;     //該弧指向的頂點的位置
   struct ArcNode *nextarc;    //指向下一條弧的指針
   int  *info;    //該弧相關信息的指針
}ArcNode;
typedef struct VNode
{
	char data;   //頂點信息
	ArcNode *firstarc;   //指向第一條依附于該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct 
{
	AdjList vertices;
	int vexnum,arcnum;  //圖的當前頂點數和弧數
    int kind;    //圖的種類標志
}ALGraph;
int visited[MAX_VERTEX_NUM];
int vexnum,arcnum;
void CreateDG(ALGraph &G)    //采用鄰接表存儲表示，構造有向圖
{
	ArcNode *p;
	printf("請輸入當前圖的頂點數！\n");
    scanf("%d",&G.vexnum);
	fflush(stdin);
    printf("請輸入當前圖的弧數！\n");
	scanf("%d",&G.arcnum);
	fflush(stdin);
	for(int i=0;i<G.vexnum;i++)
   {  
	   printf("請輸入頂點\n");
	   scanf("%c",&G.vertices[i].data);
	   fflush(stdin);
	   G.vertices[i].firstarc=NULL;
   }
	for(int k=0;k<G.arcnum;++k)
    {
	   int i,j;
	   printf("請輸入弧的信息!\n");
	   scanf("%d,%d",&i,&j);
	   p=(ArcNode*)malloc (sizeof(ArcNode));
	   p->adjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;
    }
}
void print(ALGraph &G)
 {
	printf("請輸出圖中的結點\n");
	for(int i=0;i<G.vexnum;i++)
	{
		printf("%c\n",G.vertices[i].data);
	}
 }

int FirstAdjVex(ALGraph &G,int v)
{
	if(G.vertices[v].firstarc) 
	{
		return G.vertices[v].firstarc->adjvex;
	}
	else 
	{
		return -1;
	}
}
int NextAdjVex(ALGraph &G,int v,int w)
{
	w=G.vertices[v].firstarc->adjvex;
	if(G.vertices[w].firstarc) 
	{
		return G.vertices[w].firstarc->nextarc->adjvex;
	}
	else
	{
		return -1;
	}
}
void DFS(ALGraph &G,int v)
{   
	visited[v] = 1;
	
	printf("%c\n",G.vertices[v].data);
	int w=0;
    for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
	{
		if(visited[w]==0)
		{
			DFS(G,w);
		}
	}
}
void DFSTraverse(ALGraph &G)
{
	
	for(int v=0;v<G.vexnum;++v)
	{
		visited[v]=0;
	}
    for(v=0;v<G.vexnum;++v)
	{	
		if(visited[v]==0) 
		{
			DFS(G,v);
		}
	}
}



void main()
{
	ALGraph S;
	printf("請您輸入要創建的圖的種類！\n");
	char c;

    scanf("%c",&c);
	switch(c)
	{
	case 'D':  CreateDG(S);   //構造有向圖D
	//case U: CreateUDG(S); break;;//構造無向圖G
	}
	print(S);
    printf("進行深度優先探索:\n");
	printf("深度遍歷結點為\n");
	DFSTraverse(S);
	printf("\n");

	

}