#include<stdio.h>
#include<stdlib.h>
#define N 5
typedef struct aa
{
    char vexs[N];//顶点数组
    int arcs[N][N];//邻接矩阵
}graph;
//图的两种存储方法的结构体
typedef struct bb
{
    int adjvex;
    struct bb *next;
}edgenode;
typedef struct cc
{
    char vertex;
    edgenode *link;
}vexnode;
//队列的结构体
typedef struct node
{
    int data;
    struct node *next;
}linklist;
typedef struct
{
    linklist *front,*rear;
}linkqueue;
//void DFS_matrix(graph g,int i,int visited[N]);//图按照邻接矩阵存储时的深度优先搜索遍历
//void DFS_AdjTable(vexnode ga[N],int i,int visited[N]);//图按照邻接矩表存储时的深度优先搜索遍历
void SetNull(linkqueue *q)//置空
{
    q->front=(linklist *)malloc(sizeof(linklist));
    q->front->next=NULL;
    q->rear=q->front;
}
int Empty(linkqueue *q)//判空
{
    if(q->front==q->rear)
        return 1;
    else
        return 0;
}
int Front(linkqueue *q)//取队头元素
{
    if(Empty(q))
    {
        printf("queue is empty!");
        return -1;
    }
    else
        return q->front->next->data;
}
void ENqueue(linkqueue *q,int x)//入队
{
    linklist * newnode=(linklist *)malloc(sizeof(linklist));
    q->rear->next=newnode;
    q->rear=newnode;
    q->rear->data=x;
    q->rear->next=NULL;
}
int DEqueue(linkqueue *q)//出队
{
    int temp;
    linklist *s;
    if(Empty(q))
    {
        printf("queue is empty!");
        return -1;
    }
    else
    {
        s=q->front->next;
        if(s->next==NULL)
        {
            q->front->next=NULL;
            q->rear=q->front;
        }
        else
            q->front->next=s->next;
        temp=s->data;
        return temp;
    }
}
void CreateAdjTable(vexnode ga[N],int e)//创建邻接表
{
    int i,j,k;
    edgenode *s;
    printf("\n输入顶点的内容：");
    for(i=0;i<N;i++)
    {
        //scanf("\n%c",ga[i].vertex);
        ga[i].vertex=getchar();
        ga[i].link=NULL;//初始化
    }
    printf("\n");
    for(k=0;k<e;k++)
    {
        printf("输入边的两个顶点的序号:");
        scanf("%d%d",&i,&j);//读入边的两个顶点的序号
        s=(edgenode *)malloc(sizeof(edgenode));
        s->adjvex=j;
        s->next=ga[i].link;
        ga[i].link=s;
        s=(edgenode *)malloc(sizeof(edgenode));
        s->adjvex=i;
        s->next=ga[j].link;
        ga[j].link=s;
    }
}
void DFS_matrix(graph g,int i,int visited[N])
{
    printf("%c\n",g.vexs[i]);
    visited[i]=1;
    for(int j=0;j<N;j++)
        if(g.arcs[i][j]==1&&visited[j]==0)//是否有未被访问的邻接点
            DFS_matrix(g,j,visited);//递归
}
void DFS_AdjTable(vexnode ga[N],int i,int visited[N])
{
    edgenode *p;
    printf("%c\n",ga[i].vertex);
    visited[i]=1;
    p=ga[i].link;
    while(p!=NULL)//p是否为空
    {
        if(visited[p->adjvex]==0)
            DFS_AdjTable(ga,p->adjvex,visited);
        p=p->next;
    }
}
int main()
{
    graph g;
    int visited[5]={0};//初始化
    int visited1[5]={0};
    g.vexs[0]='A';
    g.vexs[1]='B';
    g.vexs[2]='C';
    g.vexs[3]='D';
    g.vexs[4]='E';
    int a[5][5]={{0,1,0,1,1},{ 1,0,1,0,1},{ 0,1,0,0,0},{ 1,0,0,0,0},{ 1,1,0,0,0}};
    for(int i=0;i<5;i++)
        for(int j=0;j<5;j++)
            g.arcs[i][j]=a[i][j];
    printf("图按照邻接矩阵存储时的深度优先搜索遍历：\n");
    DFS_matrix(g,0,visited);
    vexnode ga[N];
    CreateAdjTable(ga,5);//5为边的条数
        printf("图按照邻接表存储时的深度优先搜索遍历：\n");
    DFS_AdjTable(ga,0,visited1);//0为开始的顶点的序号
    return 0;
}
//运行没有结果，不知道为什么，求大神指导