C语言 图的遍历(广度优先和深度优先、邻接矩阵)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
/*--------辅助广度优先遍历用的空闲单元法循环队列-----------*/
#define MaxQueuenNum 20
typedef struct queue
{
    int* array;
    int front;
    int rear;
}Queue;
/*---------------------------------------------------------*/

/*-----------------邻接矩阵的结构体类型--------------------*/
typedef char VextexType;
typedef int EdgeType;
#define MaxNum 15    //邻接矩阵的最大顶点数

typedef struct adjacency_matrix
{
    VextexType MGVexTexArray[MaxNum]; //顶点表
    EdgeType Edge[MaxNum][MaxNum];
    int VertexNum, EdgeNum;    //顶点数和边数
}MGraph;
/*---------------------------------------------------------*/


/*邻接矩阵的创建*/
void Creat_Adjacency_Matrix(MGraph* MG)
{
    int i, j, x, y;
    //先输入顶点数和边数
    printf("输入邻接矩阵的顶点数和边数:");
    scanf_s("%d %d", &MG->VertexNum, &MG->EdgeNum);
    //初始化顶点表
    printf("输入邻接矩阵各个顶点的信息:");
    for (i = 0; i < MG->VertexNum; i++)
    {
        getchar();
        scanf_s("%c", &MG->MGVexTexArray[i]);
    }
    //初始化边表
    for (x = 0; x < MG->VertexNum; x++)
    {
        for (y = 0; y < MG->VertexNum; y++)
        {
            MG->Edge[x][y] = 0;
            //初始化边表的各项为0，表示两者还没有直达的边
        }
    }
    //开始构造邻接矩阵
    for (j = 0; j < MG->EdgeNum; j++)
    {
        printf("请输入边两个顶点的下标:");
        scanf_s("%d %d", &x, &y);
        MG->Edge[x][y] = 1;
        //由于无向网和无向图是对称的所以
        MG->Edge[y][x] = MG->Edge[x][y];
    }

    printf("\n临接矩阵输出如下：\n");
    for (x = 0; x < MG->VertexNum; x++)
    {
        for (y = 0; y < MG->VertexNum; y++)
        {
            printf("%d ", MG->Edge[x][y]);
        }
        printf("\n");
    }
}

int visited[20];//全局变量标记数组,用于记录顶点有没有被访问过，访问过记为1反之为0
                //由于C没有bool或者boolean，所以用0表示False，1表示True
//深度优先算法遍历邻接矩阵
void DFS_MG(MGraph* MG, int i)
{
    int k;
    visited[i] = 1;
    printf("%c ", MG->MGVexTexArray[i]);
    for (k = 0; k < MG->VertexNum; k++)
    {
        if (MG->Edge[i][k] == 1 && !visited[k])
        {
            DFS_MG(MG, k);
        }
    }
}
void DFS_Traverse_MG(MGraph* MG)
{
    int i;
    //初始化标志数组
    for (i = 0; i < MG->VertexNum; i++)
    {
        visited[i] = 0;
    }
    //开始深度优先遍历
    for (i = 0; i < MG->VertexNum; i++)
    {
        if (!visited[i])
        {
            DFS_MG(MG, i);
        }
    }
}

//空闲单元法创建循环队列
void CreatQueue(Queue* queue)
{
    queue->array = (int*)malloc(sizeof(int) * MaxQueuenNum);
    queue->front = 0;
    queue->rear = 0;
}
//入队
void EnQueue(Queue* queue, int EnElem)
{
    if ((queue->rear + 1) % MaxQueuenNum == queue->front)
    {
        printf("无法入队,队列满");
        return;
    }
    queue->array[queue->rear] = EnElem;
    queue->rear = (queue->rear + 1) % MaxQueuenNum;
}
//出队
int DeQueue(Queue* queue)
{
    int temp;
    if (queue->rear == queue->front)
    {
        printf("队列为空,没有元素可以出队");
        return 0;
    }
    temp = queue->array[queue->front];
    queue->front = (queue->front + 1) % MaxQueuenNum;
    return temp;
}
//判断队列是否为空,空就赋1表示为空，反之为0
int Queue_isEmpty(Queue* queue)
{
    if (queue->rear == queue->front)
    {
        return 1;
    }
    return 0;
}
//广度优先算法遍历邻接矩阵
void BFS_Traverse_MG(MGraph* MG)
{
    int i, j;
    Queue q;
    CreatQueue(&q);
    //初始化标志数组
    for (i = 0; i < MG->VertexNum; i++)
        visited[i] = 0;
    //开始构建广度优先算法遍历
    for (i = 0; i < MG->VertexNum; i++)//若是连通图只执行一次即可遍历完
    {
        if (!visited[i])
        {
            EnQueue(&q, i);
            visited[i] = 1;
            while (!Queue_isEmpty(&q))  //队不为空 
            {
                i = DeQueue(&q);
                printf("%c ", MG->MGVexTexArray[i]);
                for (j = 0; j < MG->VertexNum; j++)
                {
                    if (!visited[j] && MG->Edge[i][j] == 1)
                    {
                        visited[j] = 1;
                        EnQueue(&q, j);
                    }
                }
            }
        }
    }
}

int main()
{
    int i;
    MGraph* MG = (MGraph*)malloc(sizeof(MGraph));
    printf("-----输入每个数都是用空格隔开------\n");
    Creat_Adjacency_Matrix(MG);

    printf("--------------------------------------------\n");
    printf("\n邻接矩阵的深度遍历:");
    DFS_Traverse_MG(MG);
    printf("\n");

    printf("邻接矩阵的广度遍历:");
    BFS_Traverse_MG(MG);
    printf("\n");

    printf("\n--------------------------------------------\n");
    printf("\n");
    free(MG);

    system("pause");
    return 0;
}