智能车|智能车图像处理(七)八邻域-2

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

无向图
我们希望从图中的某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,对于这一过程我们就叫做图的遍历。
以上图为例,我们想要遍历从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有路径相通的顶点都被访问到。
下面我们以一张无向图为例:
智能车|智能车图像处理(七)八邻域-2
文章图片

我们需要从顶点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个顶点。
智能车|智能车图像处理(七)八邻域-2
文章图片

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】其实看到这里,你可以发现,所谓的深度优先遍历与我们先前所说的种子填充法很像。介绍完这两种算法,下一章,我们就可以开始八邻域巡线了。

    推荐阅读