广度优先搜索
引言
在求解 leetcode 17 时，我遇到了BFS（广度优先搜索）这个概念。在深入了解后发现，BFS是图（graph）的一个知识点，我对这一知识点进行展开学习，并将找到的资料汇总起来。本文主要整理了图和广度优先搜索的相关知识点。
图的存储方式
研究图就需要使用计算机语言对其进行描述。图的存储结构除了要存储图中各个顶点的本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息）。因此，图的结构比较复杂，很难以数据元素在存储区中的物理位置来表示元素之间的关系，但也正是由于其任意的特性，故物理表示方法很多。常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。
相邻矩阵（adjacency martix）
对于一个具有 n 个顶点的图，可以使用 n*n 的矩阵（二维数组）来表示它们间的邻接关系。下图中，矩阵 A(i，j)=1 表示图中存在一条边 (Vi，Vj) ，而 A(i，j)=0 表示图中不存在边 (Vi，Vj) 。实际编程时，当图为不带权图时，可以在二维数组中存放bool值， A(i，j)=true 表示存在边 (Vi，Vj) ， A(i，j)=false 表示不存在边 (Vi，Vj) ；当图带权值时，则可以直接在二维数组中存放权值， A(i，j)=null 表示不存在边 (Vi，Vj) 。
左图所示的是无向图的邻接矩阵表示法，可以观察到，矩阵延对角线对称，即 A(i，j)=A(j，i) 。无向图邻接矩阵的第 i 行或第 i 列非零元素的个数其实就是第 i 个顶点的度。这表示无向图邻接矩阵存在一定的数据冗余。
右图所示的是有向图邻接矩阵表示法，矩阵并不延对角线对称， A(i，j)=1 表示顶点 Vi 邻接到顶点 Vj ； A(j，i)=1 则表示顶点 Vi 邻接自顶点 Vj 。两者并不象无向图邻接矩阵那样表示相同的意思。有向图邻接矩阵的第 i 行非零元素的个数其实就是第 i 个顶点的出度，而第 i 列非零元素的个数是第 i 个顶点的入度，即第 i 个顶点的度是第 i 行和第 i 列非零元素个数之和。
由于存在 n 个顶点的图需要 n^2 个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将出现大量零元素，照成极大地空间浪费，这时应该使用邻接表表示法存储图中的数据。
邻接表（adjacency list）
邻接表（adjacency list）是一种常用的表示图的数据结构。邻接表是许多链表的集合，每个链表描述了一个顶点（ vectex ）的相邻元素（ Neighbor ）。更形象地讲，邻接表是一个二维容器，第一维描述某个点，第二维描述这个点所对应的边集们。
图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如下图所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点 A 所指链表中存在一个指向 C 的表结点的同时，表头结点 C 所指链表也会存在一个指向 A 的表结点。
有向图的邻接表有出边表和入边表（又称逆邻接表）之分。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点；入边表的表结点存放的则是指向表头结点的某个头顶点。如下图所示，图(b)和(c)分别为有向图(a)的出边表和入边表。
以上所讨论的邻接表所表示的都是不带权的图，如果要表示带权图，可以在表结点中增加一个存放权的字段，其效果如下图所示。
观察上图可以发现，当删除存储表头结点的数组中的某一元素，有可能使部分表头结点索引号的改变，从而导致大面积修改表结点的情况发生。可以在表结点中直接存放指向表头结点的指针以解决这个问题（在链表中存放类实例即是存放指针，但必须要保证表头结点是类而不是结构体）。在实际创建邻接表时，甚至可以使用链表代替数组存放表头结点或使用顺序表存代替链表存放表结点。
本节所有的图片摘自 cnblogs.com - abatei
图的遍历
和树的遍历类似，在此，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(traversing graph)。如果只访问图的顶点而不关注边的信息，那么图的遍历十分简单，使用一个 foreach 语句遍历存放顶点信息的数组即可。但如果为了实现特定算法，就需要根据边的信息按照一定顺序进行遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
图的遍历要比树的遍历复杂得多，由于图的任一顶点都可能和其余顶点相邻接，故在访问了某顶点之后，可能顺着某条边又访问到了已访问过的顶点，因此，在图的遍历过程中，必须记下每个访问过的顶点，以免同一个顶点被访问多次。为此给顶点附设访问标志 visited ，其初值为 false ，一旦某个顶点被访问，则其 visited 标志置为 true 。
图的遍历方法有两种：一种是深度优先搜索遍历（depth first search 简称DFS），另一种是广度优先搜索遍历（breadth first search 简称BFS）。
广度优先搜索（breadth first search）
图的广度优先搜索遍历算法是一个分层遍历的过程，和二叉树的广度优先搜索遍历类同。它从图的某一顶点 Vi 出发，访问此顶点后，依次访问 Vi 的各个未曾访问过的邻接点，然后分别从这些邻接点出发，直至图中所有已有已被访问的顶点的邻接点都被访问到。对于无向连通图，若顶点 Vi 为初始访问的顶点，则广度优先搜索遍历顺序如下所示。
广度优先搜索的伪代码如下：
BFS (G, s) // Where G is the graph and s is the source node
let Q be queue.
Q.enqueue( s ) // Inserting s in queue until all its neighbour vertices are marked.
mark s as visited.
while ( Q is not empty )
// Removing that vertex from queue, whose neighbour will be visited now
v = Q.dequeue( )
// processing all the neighbours of v
for all neighbours w of v in Graph G
if w is not visited
Q.enqueue( w ) // Stores w in Q to further visit its neighbour
mark w as visited.
时间复杂度
BFS的时间复杂度为 O(V+E) ，其中 V 是节点的数量， E 是边的数量。
BFS的应用场景
- 最短路径问题
- P2P网络，网络广播
- GPS导航系统
- 搜索引擎的网络爬虫