#include<stdio.h>
#include<stdlib.h>
#define maxvertexnum 20  //設最大頂點數為20
typedef struct node    //定義表結點結構
{
  int adjvex;
  struct node *next;
}node;
typedef int vertextype;
typedef struct frontnode    //定義表頭結點結構
{
  vertextype vertex;          
  node *firstedge;
}frontnode;
typedef frontnode AdjList[maxvertexnum];
typedef struct ALGraph
{ 
  AdjList adjlist;
  int n,e;
}adjlist;


int visited[maxvertexnum];
void GreatALGraph(ALGraph *G);
void DFSTraverseAL(ALGraph *G);
void DFSAL(ALGraph *G,int i);


void GreatALGraph(adjlist *G)       //建立有向圖的鄰接表存儲
{
   int i,j,k;
   node *s;
   printf("請輸入頂點數和邊數:\n");
   scanf("%d,%d",&(G->n),&(G->e));  //讀入頂點數和邊數
   printf("請輸入頂點信息:\n");
   for(i=0;i<G->n;i++)      //建立有n個頂點的頂點表
   {
     scanf("\n%c",&(G->adjlist[i].vertex));
     G->adjlist[i].firstedge=NULL;
   }
   printf("請輸入邊的信息(i,j):\n");
   for(k=0;k<G->e;k++)   //建立邊表
   {
	 scanf("%d,%d",&i,&j);  //讀入邊<Vi,Vj>的頂點對應序號
     s=(node*)malloc(sizeof(node));
	 s->adjvex=j;         //鄰接點序號為j
	 s->next=G->adjlist[i].firstedge;
	 G->adjlist[i].firstedge=s; 
     s=(node*)malloc(sizeof(node));
	 s->adjvex=i;         //鄰接點序號為i
	 s->next=G->adjlist[j].firstedge;
	 G->adjlist[j].firstedge=s; 
   }
}//GrateALGraph

void DFSAL(adjlist *G,int i)  //以Vi為出發點對圖G進行DFS搜索
{
  node *p;  
  printf("visit vertex:V%c\n",G->adjlist[i].vertex);
  visited[i]=1;   //標記Vi已訪問
  p=G->adjlist[i].firstedge;   //取Vi邊表的頭指針
  while(p)  //依次搜索Vi的鄰接點Vj,j=p->adjva
  {
     if(!visited[p->adjvex])
		 DFSAL(G,p->adjvex);
	 p=p->next;   //找Vi的下一個鄰接點  
  }
}//DFSAL
void DFSTraverseAL(adjlist *G)    //深度優先遍歷圖G
{
  int i;
  for(i=0;i<G->n;i++)
	  visited[i]=0;
  for(i=0;i<G->n;i++)
	  if(!visited[i])
		  DFSAL(G,i);   //Vi未被訪問過，從Vi開始DFS搜索
}//DFS

void main()
{
  adjlist Great;
  GreatALGraph(&Great);
  DFSTraverseAL(&Great);
}