数据结构与算法-图的广度优先遍历【十六】

r囧r小猫 2022-11-27 15:59 160阅读 0赞

图的广度优先遍历与树的[广度优先遍历][Link 1]类似，用队列来实现。

节点出队，节点的所有邻接点入队。如此循环，直到队列为空。

还是以邻接矩阵表示图，咱们用下面这个图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70_pic_center]

用邻接矩阵去表示这个图，邻接表的广度优先遍历思路是一致的，只是去找邻接点的时候邻接表会更快。

图的定义：

function Graph(vexs = [], arcs = []) { 
          this.vexs = vexs
          this.arcs = arcs
      }

vexs 存储了4个顶点：

const vexs= [ 'A', 'B', 'C', 'D', 'E', 'F', 'G']

arcs是一个二维数组，长这样：

const arcs=
       [
           [0, 1, 0, 0, 1, 1, 0],
           [1, 0, 1, 1, 0, 0, 0],
           [0, 1, 0, 0, 0, 0, 1],
           [0, 1, 0, 0, 0, 0, 1],
           [1, 0, 0, 0, 0, 1, 0],
           [1, 0, 0, 0, 1, 0, 0],
           [0, 0, 1, 1, 0, 0, 0],
     ]

初始化这个图：

var graph = new Graph(vexs, arcs);

广度优先遍历的时间复杂度分析：

邻接矩阵来说需要遍历矩阵里面的每一个元素，时间复杂度为`O(n^2)`  
邻接表来说时间复杂度为`O(n+e)`

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

> bfs（广度优先遍历）与dfs（深度优先遍历）比较：

时间复杂度只与存储结构相关，如果是矩阵那么时间复杂度为`O(n^2)`  
空间复杂度都为O(n) ，dfs的递归用到了栈，bfs是用到了队列。

[Link 1]: https://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E1NTM0Nzg5_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/754e242417e349bdbfc4b1ef6da4e541.png