#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 20
#define INT_MAX 
typedef struct ArcNode{
	int adjvex;int inf;
	struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
	char data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct ALGraph{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;
int visited[MAX_VERTEX_NUM];

int LocateVex(ALGraph G,char u)
{int i;
for(i=0;i<G.vexnum;i++){
	if(u==G.vertices[i].data)return i;
	if(i==G.vexnum){
		printf("Error\n");}
	
}return -1;
}


void createALGraph_AdjList(ALGraph &G)
{int i,j,k,w;char v1,v2;ArcNode *p;
 cout<<"請輸入頂點數和邊數如：8 9"<<endl;
 
 scanf("%d %d",&G.vexnum,&G.arcnum);
 cout<<"請輸入頂點如"<<":"<<"abcdefgh"<<endl;
 for(i=0;i<G.vexnum;i++){
	 cin>>G.vertices[i].data;
	 G.vertices[i].firstarc=NULL;}

 cout<<"請輸入邊結點如：ab bd dh..."<<endl;
 for(k=0;k<G.arcnum;k++){
	 cin>>v1;cin>>v2;
	 i=LocateVex(G,v1);j=LocateVex(G,v2);
	 p=(ArcNode *)malloc(sizeof(ArcNode));
	 p->adjvex=j;
	 p->nextarc=G.vertices[i].firstarc;
	 G.vertices[i].firstarc=p;
	 p=(ArcNode *)malloc(sizeof(ArcNode));
	 p->adjvex=i;
	 p->nextarc=G.vertices[j].firstarc;
	 G.vertices[j].firstarc=p;}
 cout<<"頂點的鄰接表如下：adjvex,data"<<endl;
 for(i=0;i<G.vexnum;i++){
	 p=G.vertices[i].firstarc;cout<<i<<","<<G.vertices[i].data<<",";
	 while(p){
		 cout<<p->adjvex<<","<<G.vertices[p->adjvex].data<<",";
		 p=p->nextarc;}
	 cout<<endl;}
 return;
}

void DFS(ALGraph G,int v)
{ArcNode *p;
 printf("%5c",G.vertices[v].data);
 visited[v]=1;
 p=G.vertices[v].firstarc;
 while(p){
	 if(!visited[p->adjvex])DFS(G,p->adjvex);
	 p=p->nextarc;}
}

void DFSTraverse(ALGraph G)
{int v;
 for(v=0;v<G.vexnum;v++)visited[v]=0;
 cout<<"深度遍歷序列："<<endl;
 for(v=0;v<G.vexnum;v++){
	if(!visited[v])DFS(G,v);
}
}
void main(void)
{ALGraph G;
 createALGraph_AdjList(G);DFSTraverse(G);
}