#include<stdio.h>
#include<math.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 100
#define MAX		1000
#include<string.h>

typedef struct ArcCell // 弧的定義
 { int  adj;     // 用1或0表示相鄰否；
   int  quan;  // 該弧相關信息的指針
 }   AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM],Adj;

typedef struct // 圖的定義
{        
      char     vexs[MAX_VERTEX_NUM];  // 頂點信息
      AdjMatrix    arcs;      // 弧的信息                     
      int    n, e;   // 頂點數，弧數             
  } MGraph;


void createMGraph(MGraph *G)
{  int i,j,k,w = 0;
   printf("\n請輸入此無向圖的頂點數和弧數：");
   scanf("%d %d",&(G->n),&(G->e));
   printf("\n請輸入此圖的各個結點的名稱: ");
   for(i=1; i<=G->n; i++) 
   {getchar();
   scanf("%c",&(G->vexs[i]));
   }
   for(i=1; i<=G->n; i++)
       for(j=1; j<=G->n; j++)  
	   {
		   G->arcs[i][j].adj = 0;
           G->arcs[i][j].quan = (i==j?0:MAX);
	   }
   printf("\n 請依次輸入這%d條弧的起點，終點(用鄰接矩陣表示):",G->e);
      for(k=1; k<=G->e; k++)
        { 
		   printf("\n 第%d條弧:",k);
		   

		  scanf("%d %d",&i,&j);
 
		   G->arcs[i][j].adj = 1;
	
		   G->arcs[j][i].adj = 1;
	  }
}     //建無向網的鄰接矩陣表示
int visited[MAX_VERTEX_NUM];
int FirstAdjVex(MGraph G,int v)
{
	int i;
	for(i=1;i<=G.n;i++)
	{
		if(G.arcs[v][i].adj == 1)
			return i;
	}
	return -1;
}
int NextAdiVex(MGraph G,int v,int w)
{
	int i;
	for(i=1;i<=G.n;i++)
	{
		if((G.arcs[v][i].adj == 1)&&(i!=w))
			return i;
	}
	return -1;
}


void DFS(MGraph G,int v)
{
    int top,w,stack[100];
    top = 1;
    stack[top]=v;
	while(top!=0)
	{
		while((visited[stack[top]]==0)&&(stack[top]!=-1))
		{
            w = stack[top];
			printf(" %c ",G.vexs[w]);
	        visited[w]=1;
			top++;
			stack[top]=NextAdiVex(G,w,stack[top - 2]);
		}
		top--;
		stack[top]=NextAdiVex(G,stack[top-1],stack[top]);
       	
	}

}
void DFSTravers(MGraph G)
{
    int i,v;
	for(i=1;i<=G.n;i++)
		visited[i]=0;
	for(v=1;v<=G.n;v++)
		if(!visited[v])
			DFS(G,v);
}
void main()
{
    MGraph G;
 	createMGraph(&G);
	printf("\nDFS深度優先搜索此圖的結果為：");
    DFSTravers(G);
	printf("\n");
}