7.3.2　广度优先遍历

所谓广度优先搜索是指按照广度方向搜索，它类似于树的按层次遍历，是树的按层次遍历的推广。

广度优先搜索的基本思想是：

（1）从图中某个顶点v0出发，首先访问v0。

（2）依次访问v0的各个未被访问的邻接点。

（3）分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。访问时应保证：如果vi和vk为当前端结点，且vi在vk之前被访问，则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前访问。重复（3），直到所有端结点均没有未被访问的邻接点为止。

若此时还有顶点未被访问，则选一个未被访问的顶点作为起始点，重复上述过程，直至所有顶点均被访问过为止。

对于图7－23（a）所示的无向连通图，若顶点v1为初始访问的顶点，则广度优先搜索遍历顶点访问顺序是：v1→v2→v3→v4→v5→v6→v7→v8。遍历过程如图7－23（b）所示，虚线为遍历过程。

图7－23 广度优先搜索

在遍历过程中需要设立一个访问标志数组visited［n］，其初值为“False”，一旦某个顶点被访问，则置相应的分量为“True”。同时，需要辅助队列Q，以便实现要求：如果vi和vk为当前端结点，且vi在vk之前被访问，则vi的所有未被访问的邻接点应在vk的所有未被访问的邻接点之前访问。

将图用邻接表的方法存储，如图7－24所示，广度优先搜索的算法如下。

图7－24 通过邻接表广度遍历无向图

算法7.5 广度优先搜索

分析上述算法，图中每个顶点至多入队一次，因此外循环次数为n。若图g采用邻接表方式存储，则当结点v出队后，内循环次数等于结点v的度。对访问所有顶点的邻接点的总的时间复杂度为O（d0＋d1＋d2＋…＋dn－1）＝O（e），因此图采用邻接表方式存储，广度优先搜索算法的时间复杂度为O（n＋e）；当图g采用邻接矩阵方式存储，由于找每个顶点的邻接点时，内循环次数等于for循环（1－n）次数，因此邻接矩阵存储图时，广度优先搜索算法的时间复杂度为O（n2）。