C语言基于邻接表的图的深度优先、广度优先遍历

待我称王封你为后i 2022-02-14 00:27 224阅读 0赞

**目录**

1.深度优先（Depth\_First Search）

2.广度优先（Broadth\_First Search）

3.源代码示例

3.1深度优先

3.2广度优先

--------------------

![\_\{\}][gif.latex_7B_7D]假设有无向图G = （V，E），标志数组visited \[ n \]

(1)点集 V = \{ ![v\_\{1\}, v\_\{2\}, v\_\{3\}, v\_\{4\}, v\_\{5\}, v\_\{6\}, v\_\{7\}, v\_\{8\}][v_1_ v_2_ v_3_ v_4_ v_5_ v_6_ v_7_ v_8] \}

边集 E = \{  ![\\left (v\_\{1\}, v\_\{2\}\\right ), \\left (v\_\{1\}, v\_\{3\}\\right ), \\left (v\_\{2\}, v\_\{4\}\\right ), \\left (v\_\{2\}, v\_\{5\}\\right ), \\left (v\_\{3\}, v\_\{6\}\\right ), \\left (v\_\{3\}, v\_\{7\}\\right ), \\left (v\_\{4\}, v\_\{8\}\\right ), \\left (v\_\{5\}, v\_\{8\}\\right ), \\left (v\_\{6\}, v\_\{7\}\\right )][left _v_1_ v_2_right _ _left _v_1_ v_3_right _ _left _v_2_ v_4_right _ _left _v_2_ v_5_right _ _left _v_3_ v_6_right _ _left _v_3_ v_7_right _ _left _v_4_ v_8_right _ _left _v_5_ v_8_right _ _left _v_6_ v_7_right] \}

(2)visited \[ n \] (n为图中顶点个数，初始元素都为0）

若相应节点被访问过，则visited \[ i \] 为 1；否则visited \[ i \] 为 0

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

## 1 深度优先（Depth\_First Search） ##

选定一个节点并遍历后，遍历该节点的第一个未被遍历邻接点；从刚遍历的节点开始，遍历该节点第一个未被遍历邻接点；

如此重复（深度含义由此可知）。若顶点的所有邻接点都被遍历，则检测visited\[\]数组，从元素值为0的节点开始遍历。

以上图为例：

从顶点V1开始遍历，然后遍历V1的第一个未被遍历邻接点V2；

从V2开始，遍历V2的第一个未被遍历邻接点V4；

从V4开始，遍历V4的第一个未被遍历邻接点V8；

从V8开始，遍历V8的第一个未被遍历邻接点V5；

从V5开始，发现V5所有邻接点都被遍历，则检测visited\[\]数组，发现数组中第一个未被遍历邻接点V3；

从V3开始，遍历V3的第一个未被遍历邻接点V6；

从V6开始，遍历V6的第一个未被遍历邻接点V7；

结束。

综上，深度优先序列：1,2,4,8,5,3,6,7。

## 2 广度优先（Broadth\_First Search） ##

假设从顶点V1开始遍历，则遍历完V1的所有未被遍历邻接点，然后从所有邻接点中挑选出（按顺序从小到大）下标第一小的节点，再遍历该节点所有未被遍历邻接点；第二小……；第三小……。如此循环（广度含义由此可知）。若顶点的所有邻接点都被遍历，则检测visited\[\]数组，从元素值为0（未遍历）的节点开始遍历。

以上图为例：

从顶点V1开始遍历，然后遍历V1的所有未被遍历邻接点V2，V3；

从V2开始，遍历V2所有未被遍历邻接点V4，V5；

从V3开始，遍历V3所有未被遍历邻接点V6，V7；

从V4开始，遍历V4所有未被遍历邻接点V8。结束

综上，广度优先序列：1,2,3,4,5,6,7,8。

## 3 源代码示例 ##

### 3.1 深度优先 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VERTEX_NUM 100 // 图中最大节点数
    typedef char VertexType;
    typedef struct node // 边表节点
    {
        VertexType adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)
        struct node* next; // 指向顶点的下一个邻接点
    } EdgeNode;
    
    typedef struct vnode // 顶点结构
    {
        VertexType vex;      // 存储顶点名
        EdgeNode* firstedge; // 边表头指针，指向顶点第一个邻接点
    } VertexNode, AdjList[MAX_VERTEX_NUM];
    
    typedef struct {
        AdjList adjlist; // 描述图结构的邻接表
        int vexnum;      // 节点的数目
        int edgenum;     // 边的数目
    } ALGraph;           // adjacency list：邻接表
    
    void CreateALG(ALGraph* ALG);     // 邻接表法创建图
    void TraverseALG(ALGraph ALG);    // 遍历图ALG
    void DFSTraverseALG(ALGraph ALG); // 深度优先遍历以邻接表存储的图ALG
    void DFSALG(ALGraph ALG, int i);  // 以Vi为出发点对邻接表存储的图ALG开始DFS搜索
    // 定位节点vertex，并将其下标赋给index
    void LocateVex(ALGraph ALG, VertexType vertex, int* index);
    int visited[MAX_VERTEX_NUM]; // 标志数组
    
    int main(void)
    {
        ALGraph g;
    
        CreateALG(&g);
        printf("------------------------------\n");
        printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
        printf("------------------------------\n");
        TraverseALG(g);
        printf("------------------------------\n");
        DFSTraverseALG(g);
    
        return 0;
    }
    void CreateALG(ALGraph* ALG)
    {
        VertexType ch;
        int i = 0, count = 0;
        EdgeNode* temp;
    
        printf("请输入图的顶点：");
        while ((ch = getchar()) != '\n') // 建立顶点表
        {
            ALG->adjlist[i].vex = ch;
            ALG->adjlist[i].firstedge = NULL;
            i++;
        }
        ALG->vexnum = i; // 顶点数
    
        for (i = 0; i < ALG->vexnum; i++) // 头插法建立顶点的邻接边表
        {
            printf("请输入顶点 %c 的邻接顶点：", ALG->adjlist[i].vex);
            while ((ch = getchar()) != '\n') // 按下回车结束邻接点的创建
            {
                temp = (EdgeNode*)malloc(sizeof(EdgeNode));
                temp->adjvex = ch;
                temp->next = ALG->adjlist[i].firstedge;
                ALG->adjlist[i].firstedge = temp;
                count++;
            }
        }
        // 无向图中每条边连接两个顶点，故：节点总度数 = 边数 * 2
        ALG->edgenum = count / 2;
    }
    void TraverseALG(ALGraph ALG)
    {
        int i;
        EdgeNode* temp;
    
        if (ALG.vexnum == 0) {
            printf("图为空\n");
            return;
        }
    
        for (i = 0; i < ALG.vexnum; i++) // 遍历图
        {
            printf("顶点 %c ：", ALG.adjlist[i].vex);
            temp = ALG.adjlist[i].firstedge;
            while (temp) // 输出图的信息
            {
                printf("[ %c ] -> ", temp->adjvex);
                temp = temp->next;
            }
            printf("NULL\n");
        }
    }
    void DFSTraverseALG(ALGraph ALG) // 深度优先遍历以邻接表存储的图ALG
    {
        int i;
    
        for (i = 0; i < ALG.vexnum; i++) // 初始化标志数组
            visited[i] = 0;
    
        printf("图的深度优先遍历序列：");
        for (i = 0; i < ALG.vexnum; i++) // 从第一个节点开始DFS搜索
            if (!visited[i])
                DFSALG(ALG, i);
    }
    void DFSALG(ALGraph ALG, int i) // 以下标为i的节点为出发点对图ALG开始DFS搜索
    {
        EdgeNode* temp;
        int index;
    
        printf("%c, ", ALG.adjlist[i].vex);
        visited[i] = 1; // 标记节点i已被访问
    
        temp = ALG.adjlist[i].firstedge;
        while (temp) {
            LocateVex(ALG, temp->adjvex, &index);
            // 若以index为下标的节点未被遍历，则遍历。并从该节点开始进行下一轮DFS搜索
            if (!visited[index])
                DFSALG(ALG, index);
            // 若以index为下标的节点被遍历，则寻找节点的下一个邻接点
            temp = temp->next;
        }
    }
    void LocateVex(ALGraph ALG, VertexType vertex, int* index)
    {
        int i;
    
        for (i = 0; i < ALG.vexnum; i++) {
            if (ALG.adjlist[i].vex == vertex) {
                *index = i; // 将节点vertex的下标赋给index
                return;
            }
        }
    }

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][] ###

### 3.2广度优先 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_VERTEX_NUM 100 // 图中最大节点数
    typedef char VertexType;   // 定义节点名为char型
    typedef struct node        // 边表节点
    {
        VertexType adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)
        struct node *next; // 指向顶点的下一个邻接点
    } EdgeNode;
    
    typedef struct vnode // 顶点结构
    {
        VertexType vex;      // 存储顶点名
        EdgeNode *firstedge; // 边表头指针，指向顶点第一个邻接点
    } VertexNode, AdjList[MAX_VERTEX_NUM];
    
    typedef struct // 描述图结构的邻接表
    {
        AdjList adjlist;
        int vexnum;  // 节点的数目
        int edgenum; // 边的数目
    } ALGraph;       // adjacency list：邻接表
    
    #define MAXSIZE 100 // 队列最大元素个数
    typedef struct      // 循环顺序队列
    {
        int data[MAXSIZE]; // 存储图中节点下标
       /*
        * front:指向队列中第一个元素
        * rear:指向队列中最后一个元素下一位置
        */
        int front, rear;
    } Queue;
    void InitQueue(Queue *Q);            // 建立一个空循环队列
    void InQueue(Queue *Q, int index);   // 入队
    void OutQueue(Queue *Q, int *index); // 出队
    
    void CreateALG(ALGraph *ALG);     // 邻接表法创建图
    void TraverseALG(ALGraph ALG);    // 遍历图ALG
    void BFSTraverseALG(ALGraph ALG); // 广度优先遍历以邻接表存储的图ALG
    void LocateVex(ALGraph ALG, VertexType vertex,
                   int *index);  // 定位节点vertex，并将其下标赋给index
    int visited[MAX_VERTEX_NUM]; // 标志数组
    
    int main(void)
    {
        ALGraph g;
    
        CreateALG(&g);
        printf("------------------------------\n");
        printf("vexnum = %d ; edgenum = %d\n", g.vexnum, g.edgenum);
        printf("------------------------------\n");
        TraverseALG(g);
        printf("------------------------------\n");
        BFSTraverseALG(g);
    
        return 0;
    }
    void CreateALG(ALGraph *ALG)
    {
        VertexType ch;
        int i = 0, count = 0;
        EdgeNode *temp;
    
        printf("请输入图的顶点：");
        // 建立顶点表
        while ((ch = getchar()) != '\n') {
            ALG->adjlist[i].vex = ch;
            ALG->adjlist[i].firstedge = NULL;
            i++;
        }
        ALG->vexnum = i; // 顶点数
    
        // 头插法建立顶点的邻接边表
        for (i = 0; i < ALG->vexnum; i++) {
            printf("请输入顶点 %c 的邻接顶点：", ALG->adjlist[i].vex);
            // 按下回车结束邻接点的创建
            while ((ch = getchar()) != '\n') {
                temp = (EdgeNode *)malloc(sizeof(EdgeNode));
                temp->adjvex = ch;
                temp->next = ALG->adjlist[i].firstedge;
                ALG->adjlist[i].firstedge = temp;
                count++;
            }
        }
        ALG->edgenum = count / 2;
        // 无向图中每条边连接两个顶点，故：节点总度数 = 边数 * 2
    }
    void TraverseALG(ALGraph ALG)
    {
        int i;
        EdgeNode *index;
    
        // 若图为空，则停止遍历
        if (ALG.vexnum == 0) {
            printf("图为空\n");
            return;
        }
    
        // 遍历图
        for (i = 0; i < ALG.vexnum; i++) {
            printf("顶点 %c ：", ALG.adjlist[i].vex);
            index = ALG.adjlist[i].firstedge;
            // 以邻接表形式输出图的信息
            while (index) {
                printf("[ %c ] -> ", index->adjvex);
                index = index->next;
            }
            printf("NULL\n");
        }
    }
    void BFSTraverseALG(ALGraph ALG) // 广度优先遍历以邻接表存储的图ALG
    {
        int i, index;
        char ch; // 从节点ch开始对图进行BFS搜索
        EdgeNode *temp;
        Queue Q;
    
        // 初始化标志数组
        for (i = 0; i < ALG.vexnum; i++)
            visited[i] = 0;
    
        printf("请输入开始节点：");
        scanf("%c", &ch);
        LocateVex(ALG, ch, &index); // 将开始节点ch的下标赋给index
    
        printf("图的广度优先遍历序列：");
        InitQueue(&Q); // 建立一个空循环队列
        if (!visited[index]) {
            InQueue(&Q, index); // 开始节点入队，并修改visited数组
            visited[index] = 1;
    
            // 当队列不空时
            while (Q.rear != Q.front) {
                OutQueue(&Q, &index); // 队首元素出队并访问
                printf("%c, ", ALG.adjlist[index].vex);
    
                temp = ALG.adjlist[index].firstedge;
                // 将节点的所有邻接点入队
                while (temp) {
                    LocateVex(ALG, temp->adjvex, &index);
                    // 若节点未被遍历，则入队并修改visited数组
                    if (!visited[index]) {
                        InQueue(&Q, index);
                        visited[index] = 1;
                    }
                    temp = temp->next;
                }
            }
        }
    }
    void LocateVex(ALGraph ALG, VertexType vertex, int *index)
    {
        int i;
    
        for (i = 0; i < ALG.vexnum; i++) {
            if (ALG.adjlist[i].vex == vertex) {
                *index = i; // 将节点vertex的下标赋给index
                return;
            }
        }
        printf("节点 %c 定位失败！\n", vertex);
    }
    void InitQueue(Queue *Q) // 建立一个空队列
    {
        Q = (Queue *)malloc(sizeof(Queue));
        Q->front = Q->rear = 0;
    }
    void InQueue(Queue *Q, int index) // 入队
    {
        if ((Q->rear + 1) % MAXSIZE == Q->front) {
            printf("队列满，入队失败！\n");
            return;
        }
        Q->data[Q->rear] = index;
        Q->rear = (Q->rear + 1) % MAXSIZE;
    }
    void OutQueue(Queue *Q, int *index) // 出队
    {
        if (Q->rear == Q->front) {
            printf("队列空，出队失败！\n");
            return;
        }
        *index = Q->data[Q->front];
        Q->front = (Q->front + 1) % MAXSIZE;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2][]

[gif.latex_7B_7D]: https://private.codecogs.com/gif.latex?_%7B%7D
[v_1_ v_2_ v_3_ v_4_ v_5_ v_6_ v_7_ v_8]: https://private.codecogs.com/gif.latex?v_%7B1%7D%2C%20v_%7B2%7D%2C%20v_%7B3%7D%2C%20v_%7B4%7D%2C%20v_%7B5%7D%2C%20v_%7B6%7D%2C%20v_%7B7%7D%2C%20v_%7B8%7D
[left _v_1_ v_2_right _ _left _v_1_ v_3_right _ _left _v_2_ v_4_right _ _left _v_2_ v_5_right _ _left _v_3_ v_6_right _ _left _v_3_ v_7_right _ _left _v_4_ v_8_right _ _left _v_5_ v_8_right _ _left _v_6_ v_7_right]: https://private.codecogs.com/gif.latex?%5Cleft%20%28v_%7B1%7D%2C%20v_%7B2%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B1%7D%2C%20v_%7B3%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B2%7D%2C%20v_%7B4%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B2%7D%2C%20v_%7B5%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B3%7D%2C%20v_%7B6%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B3%7D%2C%20v_%7B7%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B4%7D%2C%20v_%7B8%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B5%7D%2C%20v_%7B8%7D%5Cright%20%29%2C%20%5Cleft%20%28v_%7B6%7D%2C%20v_%7B7%7D%5Cright%20%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220214/efe8ab71f525489a97020f2fd505403f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220214/886ee17d1d42484fa41f7bd697e1380d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: /images/20220214/c4e945c82fc8479c91706ca9073b3b11.png