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

作者：Monodyee | 2024-04-29 20:34:40

踩

邻接表的深度优先遍历和广度优先遍历

1 深度优先（Depth_First Search）

2 广度优先（Broadth_First Search）

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

(1)点集 V = { $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 )$ }

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

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

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 基于邻接表的深度优先、广度优先遍历

关于图的邻接表存储，可参考我的博客C语言图的邻接表存储

以上图为例，其邻接表结构如下所示：


顶点 1 ：[ 2 ] -> [ 3 ] -> NULL
顶点 2 ：[ 1 ] -> [ 4 ] -> [ 5 ] -> NULL
顶点 3 ：[ 1 ] -> [ 6 ] -> [ 7 ] -> NULL
顶点 4 ：[ 2 ] -> [ 8 ] -> NULL
顶点 5 ：[ 2 ] -> [ 8 ] -> NULL
顶点 6 ：[ 3 ] -> [ 7 ] -> NULL
顶点 7 ：[ 3 ] -> [ 6 ] -> NULL
顶点 8 ：[ 4 ] -> [ 5 ] -> NULL

深度遍历

对所有节点（1、2……8），假设从1开始访问，每访问一个节点，便将其标志数组（visited）对应位置置1，然后访问其第一个未被访问的邻接点，接着对当前访问的顶点执行同样操作。若所有邻接点都被访问，则遍历标志数组，找到第一个未被访问的节点开始访问。

如上表：1开始；然后2；2第一个未被访问的邻接点4；4第一个未被访问的邻接点8；8第一个未被访问的邻接点5；5的所有邻接点都被访问、则遍历标志数组、找到第一个未被访问的3；3第一个未被访问的邻接点6；6第一个未被访问的邻接点7；结束。

广度遍历

对所有节点（1、2……8），假设从1开始访问，每访问一个节点，便将其标志数组（visited）对应位置置1，然后访问其所有未被访问的邻接点，接着对节点所有邻接点按顺序重复同样操作。若节点邻接点都被访问，则遍历标志数组，找到第一个未被访问的节点开始访问。

如上表：1开始；访问2、3；然后从1的第一个邻接点2开始、访问2的邻接点4、5；3开始、访问6、7；4开始、访问8；5开始、其所有邻接点都被访问、跳过；……

4 源代码示例

4.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");
    }
}
// 深度优先遍历以邻接表存储的图ALG
void DFSTraverseALG(ALGraph ALG)
{
    int i;
 
    // 初始化标志数组
    for (i = 0; i < ALG.vexnum; i++) {
        visited[i] = 0;
    }
 
    printf("图的深度优先遍历序列：");
    // 从第一个节点开始DFS搜索
    for (i = 0; i < ALG.vexnum; i++) {
        if (!visited[i]) {
            DFSALG(ALG, i);
        }
    }
}
// 以下标为i的节点为出发点对图ALG开始DFS搜索
void DFSALG(ALGraph ALG, int i)
{
    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;
        }
    }
}


C:\WINDOWS\system32\cmd.exe /c (gcc -fexec-charset=gbk 1.c -o 1 ^&^& 1 ^&^& del 1.exe)
请输入图的顶点：12345678
请输入顶点 1 的邻接顶点：32
请输入顶点 2 的邻接顶点：541
请输入顶点 3 的邻接顶点：761
请输入顶点 4 的邻接顶点：82
请输入顶点 5 的邻接顶点：82
请输入顶点 6 的邻接顶点：73
请输入顶点 7 的邻接顶点：63
请输入顶点 8 的邻接顶点：54
------------------------------
vexnum = 8 ; edgenum = 9
------------------------------
顶点 1 ：[ 2 ] -> [ 3 ] -> NULL
顶点 2 ：[ 1 ] -> [ 4 ] -> [ 5 ] -> NULL
顶点 3 ：[ 1 ] -> [ 6 ] -> [ 7 ] -> NULL
顶点 4 ：[ 2 ] -> [ 8 ] -> NULL
顶点 5 ：[ 2 ] -> [ 8 ] -> NULL
顶点 6 ：[ 3 ] -> [ 7 ] -> NULL
顶点 7 ：[ 3 ] -> [ 6 ] -> NULL
顶点 8 ：[ 4 ] -> [ 5 ] -> NULL
------------------------------
图的深度优先遍历序列：1, 2, 4, 8, 5, 3, 6, 7, Hit any key to close this window...

4.2广度优先

广度优先遍历时，需要用队列辅助操作，关于队列的实现，可参考我的博客C语言实现顺序队列、循环队列、链式队列。


#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：邻接表
 
int visited[MAX_VERTEX_NUM]; // 标志数组
 
void CreateALG(ALGraph* ALG);     // 邻接表法创建图
void TraverseALG(ALGraph ALG);    // 输出图ALG的邻接表
void BFSTraverseALG(ALGraph ALG); // 广度优先遍历以邻接表存储的图ALG
// 定位节点vertex，并将其下标赋给index
void LocateVex(ALGraph ALG, VertexType vertex, int* index);
 
/*----------------定义一个循环队列-------------------*/
#define CQ_INIT_SIZE 100 // 队列初始容量
typedef int dataType;
typedef struct {
    dataType* data; //存储队列元素
    int front;      //指向队列中第一个元素
    int rear;       //指向队列中最后一个元素下一位置
    int cqCapacity; //最多能容纳的元素个数(队列容量)
} CQueue;
 
CQueue* initCQueue();            //创建一个空循环队列
int push(CQueue* Q, dataType x); //将元素x入队。操作成功返回1，失败返回0
int pop(CQueue* Q, dataType* x); //队首元素出队，并将其值赋给x。操作成功返回1，失败返回0
int isEmpty(CQueue* Q);          //队列空返回1，否则返回0
int isFull(CQueue* Q);           //队列满返回1，否则返回0
 
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");
    }
}
 
// 广度优先遍历以邻接表存储的图ALG
void BFSTraverseALG(ALGraph ALG)
{
    int i, index; // index为当前访问节点的索引
    char ch;      // 从节点ch开始对图进行BFS搜索
    EdgeNode* temp;
    CQueue* que = initCQueue();
 
    // 初始化标志数组
    for (i = 0; i < ALG.vexnum; i++) {
        visited[i] = 0;
    }
 
    printf("请输入开始节点：");
    scanf("%c", &ch);
    LocateVex(ALG, ch, &index); // 将开始节点ch的下标赋给index
 
    printf("图的广度优先遍历序列：");
    if (!visited[index]) {
        push(que, index); // 开始节点入队，并修改visited数组
        visited[index] = 1;
 
        // 当队列不空时
        while (!isEmpty(que)) {
            pop(que, &index); // 队首元素出队并访问
            printf("%c, ", ALG.adjlist[index].vex);
 
            temp = ALG.adjlist[index].firstedge;
            // 将节点的所有邻接点入队
            while (temp) {
                LocateVex(ALG, temp->adjvex, &index);
                // 若节点未被遍历，则入队并修改visited数组
                if (!visited[index]) {
                    push(que, 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);
}
 
// 建立空队列
CQueue* initCQueue()
{
    CQueue* Q = (CQueue*)malloc(sizeof(CQueue));
    Q->data = (dataType*)malloc(CQ_INIT_SIZE * sizeof(dataType));
    Q->front = 0;
    Q->rear = 0;
    Q->cqCapacity = CQ_INIT_SIZE;
 
    return Q;
}
int isFull(CQueue* Q)
{
    return (Q->rear + 1) % Q->cqCapacity == Q->front ? 1 : 0;
}
 
int isEmpty(CQueue* Q)
{
    return Q->front == Q->rear ? 1 : 0;
}
// 入队
int push(CQueue* Q, dataType x)
{
    if (isFull(Q)) {
        // 若达到最大容量，则将新容量扩大至旧容量 1.5 倍
        int increment = Q->cqCapacity / 2;
        Q->data = (dataType*)realloc(Q->data,
            (Q->cqCapacity + increment) * sizeof(dataType));
 
        if (!Q->data) {
            return 0;
        }
        Q->cqCapacity += increment;
    }
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % Q->cqCapacity;
    return 1;
}
// 出队
int pop(CQueue* Q, dataType* x)
{
    if (isEmpty(Q)) {
        return 0;
    } else {
        *x = Q->data[Q->front];
        Q->front = (Q->front + 1) % Q->cqCapacity;
        return 1;
    }
}


C:\WINDOWS\system32\cmd.exe /c (gcc -fexec-charset=gbk 1.c -o 1 ^&^& 1 ^&^& del 1.exe)
请输入图的顶点：12345678
请输入顶点 1 的邻接顶点：32
请输入顶点 2 的邻接顶点：541
请输入顶点 3 的邻接顶点：761
请输入顶点 4 的邻接顶点：82
请输入顶点 5 的邻接顶点：82
请输入顶点 6 的邻接顶点：73
请输入顶点 7 的邻接顶点：63
请输入顶点 8 的邻接顶点：54
------------------------------
vexnum = 8 ; edgenum = 9
------------------------------
顶点 1 ：[ 2 ] -> [ 3 ] -> NULL
顶点 2 ：[ 1 ] -> [ 4 ] -> [ 5 ] -> NULL
顶点 3 ：[ 1 ] -> [ 6 ] -> [ 7 ] -> NULL
顶点 4 ：[ 2 ] -> [ 8 ] -> NULL
顶点 5 ：[ 2 ] -> [ 8 ] -> NULL
顶点 6 ：[ 3 ] -> [ 7 ] -> NULL
顶点 7 ：[ 3 ] -> [ 6 ] -> NULL
顶点 8 ：[ 4 ] -> [ 5 ] -> NULL
------------------------------
请输入开始节点：1
图的广度优先遍历序列：1, 2, 3, 4, 5, 6, 7, 8, Hit any key to close this window...

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/509663