#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define INFINITY 65535

typedef struct MGragh
{
    char Vexs[MAXSIZE];//定义顶点表
    int Edge[MAXSIZE][MAXSIZE];//定义边数组
    int VexsNum;
    int EdgeNum;
}MGraph;
typedef struct QNode//结点结构
{
    int data;
    struct QNode *next;
}QNode, *QueuePtr;//定义了链队列中的结点类型
typedef struct LinkQueue//队列的链表结构
{
    QueuePtr front, rear;
}LinkQueue;//将头指针和尾指针封装在一起的队列类型

void CreatMGragh(MGragh *);//创建无向网图
void  DispMGraph(MGraph *);//在屏幕显示邻接矩阵
int InitQueue(LinkQueue *);//初始化队列
int EnQueue(LinkQueue *, int);//插入队尾元素e
int DeQueue(LinkQueue *, int*);//删除队头元素e
int EmptyQueue(LinkQueue*);//判断队列是否为空
int visited[MAXSIZE];
void DFS(MGragh, int);//邻接矩阵的是深度优先递归算法
void DFSTraverse(MGragh);//邻接矩阵的深度遍历
void BFSTraverse(MGragh);//邻接矩阵的广度遍历

int main(void)
{
    MGragh G;
    CreatMGragh(&G);
    DispMGraph(&G);
    printf("\n深度遍历：");
    DFSTraverse(G);
    printf("\n广度遍历：");
    BFSTraverse(G);
    return 0;
}
void CreatMGragh(MGragh *G)
{
    int i = 0, j = 0, k = 0, wet = 0;
    char ch;
    printf("请输入顶点数和边数：\n");
    scanf_s("%d %d", &G->VexsNum, &G->EdgeNum);
    ch = getchar();//吸收Enter键
    for (i = 0; i < G->VexsNum; i++)
    {
        for (j = 0; j< G->VexsNum; j++)
            G->Edge[i][j] = INFINITY;//对边数组初始化
    }
    printf("请输入顶点信息(char类型)\n");
    for (i = 0; i < G->VexsNum; i++)
    {
        scanf_s("%c", &G->Vexs[i]);//输入顶点信息
        ch = getchar();
    }
    for (k = 0; k < G->EdgeNum; k++)
    {
        printf("请输入(Vi,Vj)边的下标i,j和权值wet:");
        scanf_s("%d %d %d", &i, &j, &wet);
        ch = getchar();
        G->Edge[i][j] = wet;
        G->Edge[j][i] = G->Edge[i][j];
    }
}
void DispMGraph(MGraph *G)
{
    int i, j;
    printf("G含有%d个顶点%d个边\n", G->VexsNum, G->EdgeNum);
    printf("打印顶点信息：\n");
    for (i = 0; i < G->VexsNum; i++)
        printf("%c", G->Vexs[i]);
    printf("各顶点相连情况:\n");
    for (i = 0; i <G->VexsNum; i++)
    {
        printf("[%d]\t", i);
        for (j = 0; j < G->VexsNum; j++)
        {
            if (G->Edge[i][j] == INFINITY)
                printf("0\t");
            else
                printf("%d\t", G->Edge[i][j]);
        }
        printf("\n");
    }
}
int InitQueue(LinkQueue *q)
{
    q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));//产生一个头结点并将地址填入头指针域，尾指针也指向头结点
    if (!q->front) return FALSE;
    q->front->next = NULL;//填头结点的指针域为空
    return TRUE;
}
int EnQueue(LinkQueue *q, int e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s)
        return FALSE;
    s->data = e;
    s->next = NULL;
    q->rear->next = s;
    q->rear = s;
    return TRUE;
}
int DeQueue(LinkQueue *q, int *e)
{
    QueuePtr p;
    if (q->front == q->rear) return FALSE;//空队列，返回空
    p = q->front->next;
    *e = p->data;
    q->front->next = p->next;
    if (q->rear == p) q->rear = q->front;//若队头是队尾，则删除后将队尾指针指向头结点
    free(p);
    return TRUE;
}
int EmptyQueue(LinkQueue *q)
{
    if (q->front == q->rear)
        return 1;
    return 0;
}
void DFS(MGragh G, int i)
{
    int j;
    visited[i] = TRUE;
    printf("%c", G.Vexs[i]);
    for (j = 0; j < G.VexsNum; j++)
    if (G.Edge[i][j] != 0 && !visited[j])
        DFS(G, j);//对未被访问过的邻接顶点递归调用
}
void DFSTraverse(MGragh G)
{
    int i;
    for (i = 0; i < G.VexsNum; i++)
        visited[i] = FALSE;//初始所有顶点都是未被访问过
    for (i = 0; i < G.VexsNum; i++)
    if (!visited[i])
        DFS(G, i);
}
void BFSTraverse(MGragh G)
{
    int i, j;
    LinkQueue Q;
    for (i = 0; i < G.VexsNum; i++)
    {
        visited[i] = FALSE;
    }
    InitQueue(&Q);
    for (i = 0; i < G.VexsNum; i++)
    {
        if (!visited[i])
        {
            visited[i] = TRUE;
            printf("%c", G.Vexs[i]);
            EnQueue(&Q, i);
            while (!EmptyQueue(&Q))
            {
                DeQueue(&Q, &i);
                for (j = 0; j < G.VexsNum; j++)
                {
                    if (G.Edge[i][j] != 0 && !visited[j])
                    {
                        visited[j] = TRUE;
                        printf("%c", G.Vexs[j]);
                        EnQueue(&Q, j);
                    }
                }
            }
        }
    }

}