广度优先遍历(Breath First Search)

前言

深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath First Search)是图论中两种非常重要的算法,生产上广泛用于拓扑排序,寻路(走迷宫),搜索引擎,爬虫等,也频繁出现在 leetcode,高频面试题中。

广度优先遍历简介

广度优先遍历

广度优先遍历，指的是从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。

上文所述树的广度优先遍历动图如下，每个节点的值即为它们的遍历顺序。所以广度优先遍历也叫层序遍历，先遍历第一层(节点 1)，再遍历第二层(节点 2，3，4)，第三层(5，6，7，8)，第四层(9，10)。

深度优先遍历用的是栈，而广度优先遍历要用队列来实现，我们以下图二叉树为例来看看如何用队列来实现广度优先遍历。

#define MAXV 50
#define INF 32767
#include <stdio.h>
#define MaxSize 100
#include <stdlib.h>
typedef struct ANode {
    int adjvex;                 //该边的邻接点编号
    struct ANode *nextarc;      //指向下一条边的指针
    int weight;                 //该边的相关信息，如权值（这里用整型表示）
} ArcNode;                      //边结点类型
typedef struct Vnode {
    //InfoType info             //顶点的其他信息
    ArcNode *firstarc;          //指向第一个边结点
} VNode;
typedef struct {
    VNode adjlist[MAXV];        //邻接表的头结点数组
    int n, e;                   //图中的顶点数n和边数e
} AdjGraph ;                    //完整的图邻接表类型
void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e) { //创建图的邻接表
    int i, j;
    ArcNode *p;
    G = (AdjGraph *)malloc(sizeof(AdjGraph));

    for(i = 0; i < n; i++) {                                //给邻接表的头元素的指针域置初值
        G->adjlist[i].firstarc = NULL;
    }

    for(i = 0; i < n; i++) {                                //检查邻接表的每个元素
        for(j = n - 1; j >= 0; j--) {
            if(A[i][j] != 0 && A[i][j] != INF) {            //存在一条边
                p = (ArcNode *)malloc(sizeof(ArcNode));     //创建一个结点p
                p->adjvex = j;                              //存放邻接点
                p->weight = A[i][j];                        //存放权
                p->nextarc = G->adjlist[i].firstarc;        //采用头插法插入结点p
                G->adjlist[i].firstarc = p;
            }
        }
    }

    G->n = n;
    G->e = e;
}
void DispAdj(AdjGraph *G) {
    int i;
    ArcNode *p;

    for(i = 0; i < G->n; i++) {
        p = G->adjlist[i].firstarc;
        printf("%3d: ", i);

        while(p != NULL) {
            printf("%d[%d]→", p->adjvex, p->weight);
            p = p->nextarc;
        }

        printf("^\n");
    }
}
void DestroyAdj(AdjGraph *&G) {
    int i;
    ArcNode *pre, *p;

    for(i = 0; i < G->n; i++) {         //扫描所有单链表
        pre = G->adjlist[i].firstarc;   //p指向第i个单链表的头结点

        if(pre != NULL) {
            p = pre->nextarc;

            while(p != NULL) {          //释放第i个单链表的所有结点
                free(pre);
                pre = p;
                p = p->nextarc;
            }

            free(pre);
        }
    }

    free(G);
}
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];
    int front, rear;        //队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q) {
    q = (SqQueue *)malloc(sizeof(SqQueue));
    q->front = q->rear = 0;
}
void DestroyQueue(SqQueue *&q) {
    free(q);
}
bool QueueEmpty(SqQueue *q) {
    return(q->front == q->rear);
}
bool enQueue(SqQueue *&q, ElemType e) {
    if((q->rear + 1) % MaxSize == q->front)   //队满上溢出
        return false;

    q->rear = (q->rear + 1) % MaxSize;
    q->data[q->rear] = e;
    return true;
}
bool deQueue(SqQueue *&q, ElemType &e) {
    if(q->front == q->rear)               //队空下溢出
        return false;

    q->front = (q->front + 1) % MaxSize;
    e = q->data[q->front];
    return true;
}
//广度优先遍历
void BFS(AdjGraph *G, int v) {
    /********** Begin **********/
    int w, i;
    ArcNode *p;
    SqQueue *qu;                            //定义环形队列指针
    InitQueue(qu);                          //初始化队列
    int visited[MAXV];                      //定义顶点访问标志数组

    for(i = 0; i < G->n; i++) visited[i] = 0;     //访问标志数组初始化

    printf("%2d", v);                         //输出被访问顶点的编号
    visited[v] = 1;                             //置已访问标记
    enQueue(qu, v);

    while(!QueueEmpty(qu)) {                //队不空循环
        deQueue(qu, w);                     //出队一个顶点w
        p = G->adjlist[w].firstarc;          //指向w的第一个邻接点

        while(p != NULL) {                  //查找w的所有邻接点
            if(visited[p->adjvex] == 0) {    //若当前邻接点未被访问
                printf("%2d", p->adjvex);      //访问该邻接点
                visited[p->adjvex] = 1;      //置已访问标记
                enQueue(qu, p->adjvex);      //该顶点进队
            }

            p = p->nextarc;                      //找下一个邻接点
        }
    }

    printf("\n");
    /********** End **********/
}

• 结论：对于无向图，调⽤BFS函数的次数=连通分量数