#include<stdio.h>
#include<stdlib.h>
#define MAXE 100
struct edgenode
{ int adjvex ; /*邻接点域*/
struct edgenode *next ; /*链域*/
};
struct vexnode
{ char data; /*顶点信息*/
struct edgenode *link;
};
typedef struct vexnode adjlist[MAXE];

/*ALGraph是以邻接表方式存储的图类型*/

/*建立有向图的邻接表存储*/
void creategraph (adjlist g)
{ int e,i,s,d,n;
struct edgenode *p;
printf("请输入结点数(n)和边数(e): ");
scanf("%d,%d",&n,&e);

for(i=1;i<=n;i++)
{

printf("请输入第%d个顶点信息:",i);
scanf("%c",&g[i].data);
g[i].link=NULL;
}
for(i=1;i<=e;i++)
{
printf("\n请输入第%d条边起点序号，终点序号:",i);
scanf("%d,%d",&s,&d);
p=(struct edgenode *)malloc(sizeof(edgenode));
p->adjvex=d; /*邻接点序号为d*/
p->next=g[s].link;
g[s].link=p; /*将新结点插入顶点Vs边表的头部*/
p=(struct edgenode *)malloc(sizeof(edgenode));
p->adjvex=s; /*邻接点序号为s*/
p->next=g[d].link;
g[d].link=p; /*将新结点插入顶点Vd边表的头部*/
}
}
void print(adjlist g,int n)
{
struct edgenode *p;
int i;
for(i=1;i<=n;i++)
{
printf("%d ",i);
printf("%c -->",g[i].data);
p=g[i].link;
while(p)
{ printf("%d-->",p->adjvex);
p=p->next;
}
printf("\n");
}
}

int visited[MAXE];
void dfs(adjlist adj,int v)
{
struct edgenode *p;
visited[v]=1;
printf("%d",v);
p=adj->link;
while(p!=NULL)
{ if(visited[p->adjvex]==0)
dfs(adj,p->adjvex);
/*从v未访问的邻接点出发进行DFS*/
p=p->next;
}
}

void dfsgraph(adjlist adj, int n)
{ int i;
for(i=1;i<=n;i++)
visited[i]=0; /*给visited数组赋初值*/
for(i=1;i<=n;i++)
if(!visited[i])
dfs(adj, i);

}

void main()
{
int n,v;
adjlist g,adj;
creategraph ( g);
dfsgraph( adj,n);
print( g, n);
printf("\n");
}