//深度遍历搜索图
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 3
typedef enum {DG,DN,UDG,UDN} GraphKind;//图的类型
typedef int OtherInfo; //弧的信息，如权
typedef char VertexData;//图结点的内容为char
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
    OtherInfo info;
}ArcNode;//弧结点
typedef struct VertexNode
{
    VertexData data;
    ArcNode *firstarc;

}VertexNode;//表头结点
typedef struct
{
    VertexNode vertex[MAX_VERTEX_NUM];
    int arcnum;
    int vexnum;
    GraphKind kind;
}AdjList;//邻接表（图）

int visited[MAX_VERTEX_NUM];//全局变量：访问标志数组
void CreateAdjList(AdjList *G);
int Locate(AdjList *G, char v);
void TraverseGraph(AdjList *G);
void DepthFirstSearch(AdjList*G,int v0);

void CreateAdjList(AdjList *G)//建立邻接表
{
   
    char v1;char v2;//v1,v2为一条弧上的两个端点，一个为起始端点，一个为尾端点
    ArcNode *s;
    int i,j,k;
    char ch;
    printf(" 输入图结点：");
    for(i=0;i<G->vexnum;i++)//表头结点初始化
    {
        
        
        scanf("%c",&ch);
        G->vertex[i].data=ch;
        G->vertex[i].firstarc=NULL;
        fflush(stdin);
        
        
    }
   

    for(k=0;k<G->arcnum;k++)
    {
        printf("输入连接弧端点值,如“A,B”");
        scanf("%c,%c",&v1 ,&v2 );
        //v1=getchar();
        //v2=getchar();
        
        i=Locate(G,v1);printf("%d",i);//定位v1在表头结点里的数组下标，即第几个
        j=Locate(G,v2);printf("#");
        s=(ArcNode*)malloc(sizeof(ArcNode));
        s->adjvex=j;
        s->nextarc=G->vertex[i].firstarc;
        G->vertex[i].firstarc=s;//头结点插入法
        s=(ArcNode*)malloc(sizeof(ArcNode));
        s->adjvex=i;
        s->nextarc=G->vertex[j].firstarc;
        G->vertex[j].firstarc=s;
    }
}
//定位，查找v1,v2的相应数组下标
int Locate(AdjList *G,char v)
{
    for(int i=0;i<G->vexnum;i++)
   
        if(G->vertex[i].data==v)
            return i;
        else
            return 0;

}
//深度优先搜索邻接表



void TraverseGraph(AdjList *G)
{
    int vi=0;//没访问过的置0，访问过的置1；
    for(vi=0;vi<G->vexnum;vi++)
        visited[vi]=0;
    for(vi=0;vi<G->vexnum;vi++)
        if(visited[vi]==0)
            DepthFirstSearch(G,vi);
}
void DepthFirstSearch(AdjList*G,int v0)//DFS
{
    ArcNode*p;
    printf("%c",v0);
    visited[v0]=1;//访问过后标志数组置为1；
    p=G->vertex[v0].firstarc;
    while(p!=NULL)
    {
        if(visited[p->adjvex]==0)
            DepthFirstSearch(G,p->adjvex);
        p=p->nextarc;
    }
}

int main()
{
    AdjList * G;

    G=(AdjList*)malloc(sizeof(AdjList));
    printf("输入图结点数目，弧数目，如“4,3”\n");
    scanf("%d,%d",&G->vexnum,&G->arcnum );
   
    CreateAdjList(G);
    TraverseGraph(G);
    free(G);
    return 0;

}