智能车|智能车图像处理(七)八邻域-2 算法|c++|数据结构

题外话：在上一章我们介绍了一些关于连通域的基础概念，这一章我介绍一下上一章中关于种子填充算法的一些基础算法理解，便于之后更加透彻的理解。这章主要介绍广度优先搜索（BFS），深度优先搜索（DFS）算法。说实话，这两个算法在大二学数据结构时老师讲解过，但当时只是用来应付考试，并没有想到可以用到之后的比赛中，所以希望大家在学习一些知识时，可以将该知识点发散到一些自己感兴趣的地方，或许对此会有更深的影响。
在介绍广度优先搜索（BFS），深度优先搜索（DFS）算法前，首先介绍一下数据结构的图，具体的一些基础概念就不介绍了，感兴趣的同学可以看下我的另一篇文章：数据结构笔记-图。这里简单介绍一种图，无向图。

文章图片

无向图
我们希望从图中的某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，对于这一过程我们就叫做图的遍历。
以上图为例，我们想要遍历从v0到v6的每一个顶点，且每一个顶点只能被访问一次。那么，我们需要怎么做到？简单来说，我们需要在遍历的过程中把每个访问过的顶点打上标记，用来避免我们多次访问而不知，具体的实现方法就是设置一个访问数组visited[n]，n是图中顶点的个数，数组初始化全部为0，每访问过一个顶点后设置为1。
对于图的遍历来说，我们需要科学的设计遍历方案，通常我们有两种遍历次序的方案，也就是我们今天所要讲的：广度优先搜索（BFS），深度优先搜索（DFS）算法。
广度优先遍历（BFS）：
图的广度优先遍历有些类似于树的层序遍历，我们将上面的无向图分一下层，将顶点v0放置在第一层，让与他有边的顶点v1、v2、v3为第二层，再让与v1、v2、v3有边的顶点v4、v5为第三层，最后将v6设置为第四层。
1.创建布尔类型的数组visited[n]，用来记录访问过的顶点，未访问的为FALSE，已访问的为TRUE。创建一个队列（队头出元素，队尾进元素），用来存放每一层的顶点；初始化图G。
2.初始化visited[n]，全部置为FALSE，此时队列中没有元素
3.从图中v0开始访问，将的visited[v0]数组的值设置为true，同时将v0入队。
4.只要队列不空，则重复如下操作：
(1)队头顶点u出队。
(2)依次检查u的所有邻接顶点w，若visited[w]的值为false，则访问w，并将visited[w]置为true，同时将w入队。

总结：BFS就是以v为起始点，由远及近依次访问和v有路径相通的顶点

BFS的伪代码：

bool visted[MAX_NUM]; //定义bool类型访问数组void BFS_Travel(Graph G){//对图G进行广度优先遍历(防止图为非连通域) for(int i=0; i=0; w=NextNeighbor(G,v))//检测邻接点 if(!visted[w]){//找到未被访问的邻接点 visit(w); //访问顶点w visted[w]=TRUE; Enqueue(Q,v); } } }

以上面的无向图为例我们讲解：
假设从v0开始访问，v0先入队。此时队列非空，取出对头元素v0，由于v2，v1，v3与v0连接且未被访问，依次访问这三个点，并将v2，v1，v3依次入队。此时队列非空，取出对头元素v2，并依次访问与v2连接且未被访问过的点v4，并入列。此时队列非空，访问与v1的未访问邻接点v1...........
深度优先遍历（DFS）：
深度优先遍历其实就是一个递归的过程，他类似于树的前序遍历。它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
下面我们以一张无向图为例：

文章图片

我们需要从顶点A开始遍历所有的图顶点并做上标记。首先我们从顶点A开始，做上表示走过的记号后，面前有两条路，通向B和F,我们给自己定一个原则，在没有碰到重复顶点的情况下，始终是向右手边走，于是走到了B顶点。整个行路过程，可参看图下图。此时发现有三条分支，分别通
向顶点C、I、G,右手通行原则，使得我们走到了C顶点。就这样，我们一直顺着右手通道走，一直走到F顶点。当我们依然选择右手通道走过去后，发现走回到顶点A了，因为在这里做了记号表示已经走过。此时我们退回到顶点F,走向从右数的第二条通道，到了G顶点，它有三条通道，发现B和D都已经是走过的，于是走到H,当我们面对通向H的两条通道D和E时，会发现都已经走过了。
此时我们是否已经遍历了所有顶点呢?没有。可能还有很多分支的顶点我们没有走到，所以我们按原路返回。在顶点H处,再无通道没走过，返回到G,也无未走过通道，返回到F,没有通道，返回到E,有一条通道通往H的通道，验证后也是走过的，再返回到顶点D,此时还有三条道未走过，一条条来，H走过了，G走过了，I,这是一个新顶点，没有标记，赶快记下来。继续返回，直到返回顶点A,确认你已经完成遍历任务，找到所有的9个顶点。

文章图片

bool visted[MAX_NUM]; //定义bool类型访问数组void DFS_Travel(Graph G){ for(int i=0; i=0; w=NextNeighbor(G,v,w))//检测邻接点 w为v尚未访问的邻接点 if(!visted[w]){ DFS(D,w); } }

【智能车|智能车图像处理(七)八邻域-2】其实看到这里，你可以发现，所谓的深度优先遍历与我们先前所说的种子填充法很像。介绍完这两种算法，下一章，我们就可以开始八邻域巡线了。