图遍历之广度优先搜索

喜欢ヅ旅行 2022-12-15 14:08 241阅读 0赞

## 一 概述 ##

图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以视为一种特殊的图的遍历。图的遍历时求解图的连通性问题，拓扑排序和求关键字路径等算法的基础。

图的遍历比数的遍历要复杂的多，因为图的任一顶点都可能和其余顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已经访问的顶点，为此可以设一个辅助数组Visied\[\]来标记顶点是否被访问过。图的遍历算法主要分为广度优先搜索和深度优先搜索。

## 二 广度优先搜索 ##

广度优先搜索(Breadth-First-Search，BFS)类似于二叉树的层序遍历算法。

基本思想是：

1.  首先访问起始顶点v；
2.  接着从v出发，依次访问v的各个未访问过的邻接顶点w1，w2，w3...wi；
3.  然后依次访问w1，w2，...，wi的所有未被访问过的邻接顶点；
4.  再从这些未被访问过多的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止；
5.  若此图中尚存在顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述步骤，直至图中所有顶点都被访问到为止。

这种思想在Dijksra单源最短路径算法和Prim最小生成树算法中也应用了类似的思想。

广度优先搜索是一种分层的查找过程，每向前执行一步可能访问一些顶点，不像深度优先那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

## 三 广度优先搜索算法与树的层序遍历 ##

广度优先搜索算法类似于树的层序遍历算法，到那时也会存在差异。

如图所示：

![20201130201727431.png][]

广度优先搜索算法的实现同树的遍历是一致的，但是图发生变化时：

![20201130201857942.png][]

如图会存在一个由结点2，4，5组成的环，执行图的广度优先搜索算法：

1.  先访问顶点1；
2.  然后访问它所有的邻接顶点2和3；
3.  接着从顶点2出发，访问其邻接顶点4和5；
4.  接着访问顶点3的邻接顶点6；
5.  继续从顶点4出发，访问顶点4的邻接顶点，得到会访问到顶点5和7。

此时就违背了图遍历中所有顶点访问一次且访问一次的原则，同时也不满足树的层次遍历情形。

在树的层序遍历过程中需要借助于队列来实现，而图的广度优先搜索算法除了需要借助于**队列**以外，还需要借助**辅助标记数组**来标记已经被访问的结点。

## 四 图的广度优先搜索算法的实现 ##

如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70][]

需要借助一个队列和一个辅助标记数组，该数组容量为图中结点的个数，同时图中某结点被访问后，其在数组中对应的值为1，未被访问时数组对应的值为0；或者被访问过的结点对应的值为true，未被访问过的结点对应的值为false。

**初始状态下的队列状态和辅助标记数组状态：**

**队列初始状态：**

**辅助标记数组初始状态：（注：此处图中顶点在数组中的位置，按1~7对应数组的0~6位置）**

**首先时访问顶点1，将1入队，同时将辅助标记数组中对应的值改为1。**

**队列：**

**辅助标记数组：**

**接着将队列中的顶点1出队，并将其所有的邻接顶点入队，并它们标记为访问状态：**

**队列：**

**辅助标记数组：**

接着使得顶点2出队，并将其所有的邻接顶点入队，并将它们标记为访问状态，由图可知，顶点2的邻接顶点包括1，4和5。因为顶点1已经被访问过来，所以先有一个判断顶点是否已经被访问的过程。所以只会将未被访问的顶点4和顶点5入队，并将其标记为已经被访问状态。

**队列：**

**辅助标记数组：**

按照上述步骤，继续对图中的后续顶点未被访问过多顶点进行访问。

## 四 图广度优先搜索遍历的算法代码 ##

bool visited[MAX_TREE_SIZE]
    //对非连通图进行各个顶点访问
    void BFSTraverse(Graph G){
    	//初始化visited数组
    	for(int i = 0; i < G.vexnum; ++i){
    		visited[i] = FALSE;
    	}
    	//初始化辅助的队列
    	InitQueue(Q);
    	//实现非连通图的广度优先搜索的一个循环
    	for(int i = 0; i < G.vexnum; ++i){
    		if(!visited[i]){
    			BFS(G,i);
    		}
    	}
    }
    
    //G表示连通图，v表示搜索顶点的编号
    void BFS(Graph G,int v){
    	//访问顶点
    	visit(v);
    	//将改顶点在辅助标记数组中的值设置为TRUE，表示该顶点已经被访问且入队
    	visited[v] = TRUE;
    	//将该顶点入队
    	EnQueue(Q,v);
    	while(!isEmpty(Q)){
    		//出队队首元素，并将其赋值到v当中
    		Dequeue(Q,v);
    		//找到所有符合要求的邻接顶点
    		//FirstNeighbor求某个顶点的第一个邻接顶点，当此时的w为-1表示无邻接顶点，当w>0成立时，该w为邻接顶点的编号
    		//NextNeighbor求某个顶点的其他邻接顶点。
    		for(w = FirstNeighbor(G,v);w >= 0;w = NextNeighbor(G,v,w))
    			if(!visited[w]){
    				//访问未被访问过的顶点
    				visit[w];
    				//将当被访问过的顶点标记为访问过
    				visited[w] = TRUE;
    				//将该顶点入队
    				EnQueue(Q,w);
    			}//if
    	}//while
    }

## **五 BFS算法的性能分析** ##

**空间复杂度：**O(|V|)，即图中顶点的数量。

**时间复杂度：**

**BFS算法的时间复杂度：**

**通过邻接矩阵法的图：**

**BFS的时间复杂度为O(|V|\*|V|)。**

**原因：**我们在BFS中访问某个顶点时，我们需要一个循环来寻找某个顶点的所有邻接顶点，在邻接矩阵法中找寻某顶点的所有邻接顶点即为找到该顶点在矩阵中对应的行。当矩阵中某值为1的时候，该值对应的顶点即为要寻找的邻接顶点。当在邻接矩阵法的图中通过BFS算法找到所有顶点的邻接顶点的时间复杂度为O(|V| \* |V|)。

**通过邻接表法的图：**

**BFS的时间复杂度为O(|V| + |E|)。**

**原因：**我们在访问所有顶点的邻接顶点时，需要通过访问其边进行访问。所以当在邻接表法的图中通过BFS算法找到所有顶点的邻接顶点的时间复杂度为O(|V| + |E|)。

[20201130201727431.png]: /images/20221123/59778befba74439ca9e3a77afc8efa39.png
[20201130201857942.png]: /images/20221123/f8a0934850864f91b599aab931fd6639.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70]: /images/20221123/d86fa4a34bea456a8dd2e76720bfd079.png