[数据结构]图基于邻接矩阵的BFS与DFS的C语言简单实现

爱被打了一巴掌 2022-06-04 02:07 204阅读 0赞

Github:([https://github.com/FlameCharmander/DataStructure][https_github.com_FlameCharmander_DataStructure])

上次给大家看了一下图的邻接矩阵的存储。接下来来看下图的广度优先搜索和深度优先搜索。  
![图][SouthEast]  
为了更好的展示BFS和DFS，我把上次的图改了一个边，改成上图那样。  
好了，贴代码  
由于我们的图广度遍历时需要借助一个队列来实现  
所以我们需要用到一个之前实现的队列  
把下面这个代码写成queue.c，因为我们图的源文件需要对它导入

#define MAXSIZE 100
    #define ElemType char
    #define BOOL int
    #define TRUE 1
    #define FALSE 0
    
    typedef struct{
        ElemType data[MAXSIZE];
        int front, rear;
    }Queue;
    
    static void InitQueue(Queue *queue);   //初始化队列
    static BOOL IsEmpty(Queue *queue); //判断是否为空
    static void EnQueue(Queue *queue, ElemType x); //入队
    static void DeQueue(Queue *queue, ElemType *x);    //出队
    
    void InitQueue(Queue *queue){
        queue->front = 0;
        queue->rear = 0;
    }
    
    void EnQueue(Queue *queue, ElemType e){
        queue->data[queue->rear] = e;
        queue->rear = (queue->rear + 1) % MAXSIZE;
    }
    
    void DeQueue(Queue *queue, ElemType *e){
        *e = queue->data[queue->front];
        queue->front = (queue->front + 1) % MAXSIZE;
    }
    
    BOOL IsEmpty(Queue *queue){
        if (queue->front == queue->rear) {
            return TRUE;
        } else {
            return FALSE;
        }
    }

你可以拿上面的代码跟之前的代码做个比较。其实就是声明函数的那个部分加了static，加这个可以让别的源文件访问，然后main函数去掉了而已。  
然后下面是图的代码。

#include <stdio.h>
    #include <stdlib.h>
    #define INFINTE 65535
    #define MAXSIZE 100
    #include "queue.c"
    
    typedef char VertexType;                //顶点类型应由用户定义
    typedef int EdgeType;                   //边上的权值类型应由用户定义
    
    typedef struct graph{
        VertexType vexs[MAXSIZE];            //顶点表
        EdgeType   arc[MAXSIZE][MAXSIZE];       //邻接矩阵
        int numNodes, numEdges;
    }Graph;
    
    int visited[200];
    
    void CreateGraph(Graph* graph); //创建图
    VertexType* FirstAdjVex(Graph graph, VertexType data);  //获取第一邻接点
    VertexType* NextAdjVex(Graph graph, VertexType data, VertexType adj);   //获取下一邻接点
    void DFSTraversal(Graph graph); //深度优先遍历
    void BFSTraversal(Graph graph); //广度优先遍历
    void DFS(Graph graph, VertexType data); //深度优先搜索
    void BFS(Graph graph, VertexType data); //广度优先搜索
    
    int main(){
        int i, j;
        Graph graph;
        CreateGraph(&graph);
        //打印邻接矩阵
        for (i = 0; i < graph.numNodes; ++i){
            for (j = 0; j < graph.numNodes; ++j){
                printf("%d ", graph.arc[i][j]);
            }
            printf("\n");
        }
    
        VertexType* adj = FirstAdjVex(graph, 'A');
        VertexType x = *adj;
        printf("%c ", x);
        adj = NextAdjVex(graph, 'A', x);
        x = *adj;
        printf("%c ", x);
        x = *adj;
        adj = FirstAdjVex(graph, 'D');
        printf("%c\n", *adj);
        for (i = 0; i < 200; ++i){
            visited[i] = 0;
        }
        BFSTraversal(graph);
        printf("\n");
        for (i = 0; i < 200; ++i){  //访问数组置空
            visited[i] = 0;
        }
        DFSTraversal(graph);
        return 0;
    }
    
    void CreateGraph(Graph* graph){
        int i, j;
        //先把图的邻接矩阵置为0(0表示没边，1表示有边)
        for (i = 0; i < graph->numNodes; ++i){
            for (j = 0; j < graph->numNodes; ++j){
                graph->arc[i][j] = 0;
            }
        }
        //printf("请输入顶点数, 边数：");
        //scanf("%d %d", &graph->numNodes, &graph->numEdges);
        //getchar();
        graph->numNodes = 6;
        graph->numEdges = 6;
        /*
        for (i = 0; i < graph->numNodes; ++i){
            printf("请输入顶点：");
            scanf("%c", &graph->vexs[i]);
            getchar();  //消除空白符
        }
        */
        graph->vexs[0] = 'A';
        graph->vexs[1] = 'B';
        graph->vexs[2] = 'C';
        graph->vexs[3] = 'D';
        graph->vexs[4] = 'E';
        graph->vexs[5] = 'F';
        VertexType start, end;
        /*
        for (i = 0; i < graph->numEdges; ++i){
            printf("请输入起点， 终点：");
            scanf("%c %c", &start, &end);
            getchar();  //消除空白符
            int startIndex, endIndex;
            for (j = 0; j < graph->numNodes; ++j){  //找到起始点,终点
                if (start == graph->vexs[j]){
                    startIndex = j;
                }
                if (end == graph->vexs[j]){
                    endIndex = j;
                }
            }
            graph->arc[startIndex][endIndex] = 1;
            //如果是无向图，需要双向保存
            graph->arc[endIndex][startIndex] = 1;
        }
        */
        graph->arc[0][2] = 1;
        graph->arc[0][3] = 1;
        graph->arc[3][1] = 1;
        graph->arc[2][4] = 1;
        graph->arc[3][5] = 1;
        graph->arc[4][5] = 1;
        //如果是无向图，需要保存两个边
        /*
        graph->arc[2][0] = 1;
        graph->arc[3][0] = 1;
        graph->arc[1][3] = 1;
        graph->arc[4][2] = 1;
        graph->arc[5][3] = 1;
        graph->arc[5][4] = 1;
        */
    
    }
    
    
    VertexType* FirstAdjVex(Graph graph, VertexType vex){
        //先找到data这个结点
        int i, j;
        for (i = 0; i < graph.numNodes; ++i){
            if (graph.vexs[i] == vex){
                for (j = 0; j < graph.numNodes; ++j){
                    if (graph.arc[i][j] == 1){  //找到第一个邻接点
                        return &(graph.vexs[j]);
                    }
                }
            }
        }
        return NULL;    //这步说明没找到
    }
    
    
    VertexType* NextAdjVex(Graph graph, VertexType vex, VertexType adj){
        int vexIndex, adjIndex, i;
        for (i = 0; i < graph.numNodes; ++i){
            if (graph.vexs[i] == vex){
                vexIndex = i;
            }
            if (graph.vexs[i] == adj){
                adjIndex = i;
            }
        }
        for (i = adjIndex + 1; i < graph.numNodes; ++i){  //从当前邻接点的后面寻找
            if (graph.arc[vexIndex][i] == 1){
                return &(graph.vexs[i]);
            }
        }
        return NULL;    //这步说明没找到
    }
    
    /* 深度优先遍历 */
    void DFSTraversal(Graph graph){
        int i;
        for (i = 0; i < graph.numNodes; ++i){
            if (visited[graph.vexs[i]] != 1) {
                DFS(graph, graph.vexs[i]);
            }
        }
    }
    
    /* 广度优先遍历 */
    void BFSTraversal(Graph graph){
        int i;
        for (i = 0; i < graph.numNodes; ++i){
            if (visited[graph.vexs[i]] != 1) {
                DFS(graph, graph.vexs[i]);
            }
        }
    }
    
    /*
        广度优先搜索
    */
    void BFS(Graph graph, VertexType vetex){
        Queue queue;
        InitQueue(&queue);
        EnQueue(&queue, vetex);
        VertexType adj;
        VertexType *p;
        visited[vetex] = 1;
        while (!IsEmpty(&queue)){
            DeQueue(&queue, &vetex);
            printf("%c ", vetex);
            for (p = FirstAdjVex(graph, vetex); p != NULL; p=NextAdjVex(graph, vetex, adj)){
                adj = *p; //应该可以写成*p，但是不行
                if (visited[adj] != 1){
                    EnQueue(&queue, adj);
                    visited[adj] = 1;
                }
            }
        }
    }
    
    /*
        深度优先搜索
    */
    void DFS(Graph graph, VertexType vex){
        visited[vex] = 1;
        printf("%c ", vex);
        VertexType *p;
        VertexType x;
        for (p = FirstAdjVex(graph, vex); p != NULL; p=NextAdjVex(graph, vex, x)){
            x = *p;
            if (visited[x] != 1){    //没访问过
                DFS(graph, x);
            }
        }
    }

[https_github.com_FlameCharmander_DataStructure]: https://github.com/FlameCharmander/DataStructure
[SouthEast]: /images/20220604/3bcb9eb66d794782ad146d9a2077528f.png