#include<stdio.h>
#include<stdlib.h>

//表结点
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;

//头结点
typedef struct Vnode
{
  char data;
  ArcNode *firstarc;
}Vnode;
bool visit[20];

//图结构
typedef struct Graph
{
	int point;
	int link;
	Vnode *VeArray;
	int flag;
}AlGraph;

//初始化图
void InitGraph(AlGraph *p,int ve,int arc)
{
 p->point=ve;
 p->link=arc;
 p->flag=0;
 p->VeArray=(Vnode *)malloc(sizeof(Vnode)*ve);
}
//用邻接表存储图
void CreateGraph(AlGraph *p)
{
	int i,j;
	char index;
	ArcNode	*Q,*S;
	printf("请依次输入各顶点:\n");
	for(i=0;i<p->point;i++)
	{
	    getchar();
		scanf("%c",&index);
		p->VeArray[i].data=index;
		p->VeArray[i].firstarc=NULL;
	}
	for(i=0;i<p->point;i++)
	{
	    getchar();
		S=(ArcNode *)malloc(sizeof(ArcNode));
		printf("依次输入与顶点 %c  相邻的顶点并以#结束：",p->VeArray[i].data);
		scanf("%c",&index);
		if(index)
		{
		j=0;
	    while(index!=p->VeArray[j].data)
			j++;
		 S->adjvex=j;
         p->VeArray[i].firstarc=S;
		 Q=S;
       	}
		else
		continue;
		scanf("%c",&index);
		while(index!='#')
		{
		   S=(ArcNode *)malloc(sizeof(ArcNode));
		   j=0;
		   while(index!=p->VeArray[j].data)
			   j++;
		    S->adjvex=j;
		    Q->nextarc=S;
		    Q=S;
			scanf("%c",&index);
		}
		Q->nextarc=NULL;
	}
}
//输出邻接表
void  showGraph(AlGraph *p)
{
	int i;
	ArcNode *temp;
	printf("顶点位置\t顶点名称\t邻接顶点的位置\n");
	for(i=0;i<p->point;i++)
	{
		printf("%4d\t\t %c  ->\t\t",i,p->VeArray[i].data);
		temp=p->VeArray[i].firstarc;
		while(temp)
		{
			printf("%d->\t",temp->adjvex);
			temp=temp->nextarc;
		}
		printf("\n");
	}
}

void DFS(AlGraph &p,int i)
{
   visit[i]=true;
   printf("%c->",p.VeArray[i].data);
   ArcNode *nextNode=p.VeArray[i].firstarc;
   while(nextNode)
{
    if(!visit[nextNode->adjvex])
        DFS(p,nextNode->adjvex);
        nextNode=nextNode->nextarc;
}
}
void DFStraverse(AlGraph &p)
{
    for(int i=0;i<p.point;i++)
       visit[i]=false;
   for(int i=0;i<p.point;i++)
   {
        if(!visit[i])
          DFS(p,i);
   }
}
int main ()
{
	int ve,arc;
	AlGraph p;
	printf("请输入无向图的顶点数和边数：\n");
	scanf("%d%d",&ve,&arc);
    InitGraph(&p,ve,arc);
	CreateGraph(&p);
	printf("\n无向图的邻接表存储结构如下：\n");
	showGraph(&p);
	printf("深度优先搜索无向图序列如下:\n");
	DFStraverse(p);
}