#include "iostream.h"
#include "malloc.h"
#include "stdio.h"
#define MaxVertexNum 50
bool visited[MaxVertexNum];   
typedef struct node{
    char adjvex;
    struct node *next;
 }EdgeNode;  
typedef struct vnode{
    char vertex;  
    EdgeNode *firstedge;
 }VertexNode;  
typedef VertexNode AdjList[MaxVertexNum];
typedef struct {      
    AdjList adjlist;   
     int n,e;   
} ALGraph;      
void CreatALGraph(ALGraph &G)
   {   
    int i,j,k;  
    EdgeNode *s;
    printf("请输入顶点数和边数: ");
    scanf("%d %d",&(G->n),&(G->e));  
    printf("请输入顶点的信息:");   
    for(i=0;i<G->n;i++)  
    { scanf("\n%c",&G->adjlist[i].vertex);
    G->adjlist[i].firstedge=NULL;
    }      
    printf("请输入由两个顶点构成的边:\n");     
    for(k=0;k<G->e;k++)   
    {
        scanf("\n%d %d",&i,&j);
        s=(EdgeNode *)malloc(sizeof(EdgeNode));   
        s->adjvex=j;   
        s->next=G->adjlist[i].firstedge;     
        G->adjlist[i].firstedge=s;   
        s=(EdgeNode *)malloc(sizeof(EdgeNode));   
        s->adjvex=i;        
        s->next=G->adjlist[j].firstedge;   
        G->adjlist[j].firstedge=s;  
    }  
 }  
void DFS(ALGraph G)
    {   int i;
        for(i=0;i<G->n;i++)   
    visited[i]=FALSE;
    for(int i=0;i<G->n;i++)        
        if(!visited[i])     
            DFSM(G,i);   
    }     
void DFSM(ALGraph G,int i)
{
        EdgeNode *p;      
        printf("访问结点：%c\n",G->adjlist[i].vertex);  
        visited[i]=TRUE;
        p=G->adjlist[i].firstedge;
        while(p)
        {   
                if(!visited[p->adjvex])
                    DFSM(G,p->adjvex);  
                p=p->next;  
        }  
    }
void main()
 {
   ALGraph g;
   CreatALGraph(g);
   DFS(g);
}