图的广度优先搜索算法并生成BFS树

超、凢脫俗 2022-06-04 04:05 172阅读 0赞

笔者在前面的两篇文章中介绍了图的两种实现方法：

>  *  [图的邻接表的实现][Link 1]
>  *  [图的邻接矩阵的实现][Link 2]

接下来笔者将介绍图遍历算法，与树的遍历类似，图的遍历也需要访问所有顶点一次且仅一次；此外，图遍历同时还需要访问所有的弧一次且仅一次。

#### 图的遍历概述 ####

图的遍历都可理解为，**将非线性结构转化为半线性结构的过程。经遍历而确定的弧类型中，最重要的一类即所谓的树边，它们与所有顶点共同构成了原图的一棵支撑树（森林），称作遍历树（traversal tree）本文要介绍的BFS将是其中的一种。**以遍历树为背景，其余各种类型的边，也能提供关于原图的重要信息，比如其中所含的环路等。

图中顶点之间可能存在多条通路，故为避免对顶点的重复访问，在遍历的过程中，通常还要动态地设置各顶点不同的状态，并随着遍历的进程不断地转换状态，直至最后的“访问完毕”。图的遍历更加强调对处于特定状态顶点的甄别与查找，故也称作图搜索（graph search）。

与树遍历一样，作为图算法基石的图搜索，本身也必须能够高效地实现，如深度优先、广度优先、最佳优先等基本而典型的图搜索，都可以在线性时间内完成。若顶点数和边数分别为 n 和 e，则这些算法自身仅需 0 (n + e）时间。

#### 图的广度优先搜索概述 ####

各种图搜索之间的区别，体现为边分类结果的不同，以及所得遍历树（森林）的结构差异。其决定因素在于，搜索过程中的每一步迭代，将依照何种策略来选取下一接受访问的顶点。

通常，都是选取某个已访问到的顶点的邻居。同一顶点所有邻居之间的优先级，在多数遍历中不必讲究。因此，实质的差异应体现在，**当有多个顶点已被访问到，应该优先从谁的邻居中选取下一顶点。**比如，广度优先搜索（breadth-first search, BFS）采用的策略，可概括为：**越早被访问到的顶点，其邻居越优先被选用**

于是，始自图中顶点s的BFS搜索，将首先访问顶点s；再依次访问s所有尚未访问到的邻居；再按后者被访问的先后次序，逐个访问它们的邻居；…；如此不断。由于每一步迭代都有一个顶点被访问，故至多迭代 O (n）步。另一方面，因为不会遗漏每个刚被访问顶点的任何邻居，故对于无向图必能覆盖 s 所属的连通分量（connected component），对于有向图必能覆盖以 s 为起点的可达分量（reachable component）。倘若还有来自其它连通分量或可达分量的顶点，则再从该顶点出发，重复上述过程。

#### 图的广度优先搜索的代码实现 ####

首先来看看再遍历算法中节点和弧使用到的属性：  
**节点：**

private int status = 0;  //状态 0 undiscovered "未发现"  1 discovered "已发现"   2 visited "已完成"
        private int parent = -1;

**弧：**

private int type;  
        //弧类型：0 CROSS 跨边  1 TREE（支撑树）

**遍历代码**

//广度优先，并生成bfs树
      public void bfsTree(int index) {
          this.reload();//复位所有节点和弧的状态
          int v = index;
          do {
              if(allNodes[v].getStatus() == 0) {
                  this.bfs(v);
              }
          }while(index !=(v = (++v%size)));
      }
    
      public void bfs(int v) {
          Queue<Integer> list = new LinkedList<Integer>();
          list.add(v);
          allNodes[v].setStatus(1);
    
          while(!list.isEmpty()) {
              v = list.poll();
              //枚举v的所有邻居 u
              for(int u=0; u<size; u++) {
                  if(getEdge(v, u)!=null) {
                      //如果节点i尚未被发现
                      if(allNodes[u].getStatus() == 0) {
                          //发现该节点
                          allNodes[u].setStatus(1);
                          //并设置支撑树(index为i的parent)
                          nodeGraphs[v][u].setType(1);
                          allNodes[u].setParent(v);
                          list.add(u);
                      }else {
                       //如果节点i已被发现，则将边index->i 归为跨边
                       nodeGraphs[v][u].setType(0);
                      }
                  }
              }
              //至此，v节点访问完毕
              allNodes[v].setStatus(2);
          }
      }
    
      //获取与节点node的相链接的弧，不存在返回false
      public Edge getEdge(int start, int end) {
        return nodeGraphs[start][end];
      }

算法的实质功能，由子算法 bfs（）完成。对该函数的反复调用，即可遍历所有连通或可达域。仿照树的层次遍历，这里也借助队列 list，来保存已被发现，但尚未访问完毕的顶点。因此，任何顶点在进入该队列的同时，都被随即标为”已发现”状态。

bfs（）的每一步迭代，都先从 list 中取出当前的首顶点 v；再逐一核对其各邻居 u 的状态并做相应处理；最后将顶点 v 置为 “访问完毕” 状态，即可进入下一步迭代。

若顶点 u 尚处于”未发现”状态，则令其转为”已发现” 状态，并随即加入队列 list。实际上，每次发现一个这样的顶点 u，都意味着遍历树可从 v 到 u 拓展一条边。于是，将边（v, u）标记为树边（tree edge），并按照遍历树中的承袭关系，将 v 记作 u 的父节点。

若顶点 u 已处于 “已发现” 状态（无向图），或者甚至处于“已完成“ 状态（有向图），则意味着边（v, u）不属于遍历树，于是将该边归类为跨边（cross edge)

bfs（）遍历结束后，所有访问过的顶点通过 parent指针依次联接，从整体上给出了原图某一连通或可达域的一棵遍历树，称作广度优先搜索树，或简称 BFS 树（BFS tree）。

#### 实例给出了一个 ####

下图展示了一个含8个顶点和11条边的有向图，起始于顶点S的BFS搜索过程。注意观察辅助队列（下方）的演变，顶点状态的变化，边的分类与结果，以及BFS树的生长过程

![这里写图片描述][SouthEast]  
![这里写图片描述][SouthEast 1]  
![这里写图片描述][SouthEast 2]

不难看出，bfs (s）将覆盖起始项点 s 所属的连通分量或可达分量，但无法抵达此外的顶点。而上层主函数 bfsTree（）的作用，正在于处理多个连通分量或可达分量并存的情况。具体地，在逐个检查顶点的过程中，只要发现某一顶点尚未被发现，则意味着其所属的连通分量或可达分量尚未触及，故可从该顶点出发再次启动 bfs (），以遍历其所属的连通分量或可达分量。如此，各次 bfs（）周用所得的 BFS 树构成一个森林，称作 BFS 森林。

#### 复杂度 ####

除作为输入的图本身外，BFS 搜索所使用的空间，主要消耗在用于维护顶点访问次序的辅助队列、用于记录顶点和边状态的标识位向量，累计 O (n) + O (n) + O (e) = O (n + e）。

时间方面，首先需花费 0 (n + e）时间复位所有顶点和边的状态。不计对子函数 bfs（）的调用，bfsTree（）本身对所有项点的枚举共需 0 (n）时间。而在对 bfs（）的所有调用中，每个顶点、每条边均只耗费 0 (1）时间，累计 O (n + e）。综合起来，BFS 搜索总体仅需 0 (n + e）时间。

[Link 1]: http://blog.csdn.net/canot/article/details/78704828
[Link 2]: http://blog.csdn.net/canot/article/details/78703184
[SouthEast]: /images/20220604/249c15ae9e514b82b0bd6d6443024577.png
[SouthEast 1]: /images/20220604/83ab1f52d25543a097c2790b82779fd1.png
[SouthEast 2]: /images/20220604/2abcd2bef87a4585a8408e8f201ed8bf.png