首页 > theory > algorithm > > 正文

图的遍历——图论与图模型

发布人:zhoulujun@live.cn    点击:

2 遍历的基本概念搜索已经成为了获得信息的基本手段,其实搜索从语义上来看 是去某个地方寻找某种信息,如去书架找一本书,这就叫一种搜

2 遍历的基本概念

搜索已经成为了获得信息的基本手段,其实搜索从语义上来看 是去某个地方寻找某种信息,如去书架找一本书,这就叫一种搜索,给出了搜索对象 -- 书,也给出了一个行为范围就是整个书架。

图作为一种数据结构,也必须拥有被搜索的能力,

把这两个概念切换到图的领域,通过搜索整个图一次找到某些信息,就是图的遍历,这里面强调的遍历有一个隐含的概念,如果图中的元素(点和边)只被观察过一次就完成了整个遍历,就是一个高效的遍历,如果重复的不停的观察已经观察过的位置,就是不高效的遍历,面对节点间具有复杂关系的图,从什么地方出发,又如何选择下一步遍历的方向,将导致这个遍历办法是否高效.


2.1 遍历"点"还是遍历"边"?

图的信息在哪里? 点和点之间的关系就是信息,也就是说 点和边其实都蕴含着信息。但是根据需求,我们可以把遍历分为,遍历图中的点遍历图中的边两种。

2.1.1遍历"点"

随机选一个点A作为遍历的起始点,下一步要确定的是需要遍历的下一个点怎么选,现在我们有了一些信息,就是A的相邻节点(Adj[A]),(以A为起点的边的结尾点Adj[A]),于是我们可以选择其中个点B作为第二步,

找到第三个点的办法:

方法1:

继续上面的思路,找A的邻居点 C in adj[A];

方法 2:

找B的邻居点 C in adj[B];

好了 再找完第三个点之后 我们的思路基本就清晰了,有两种方式完成对图的遍历,一种侧重广度优先(Bread-first),先把所有的邻居遍历完再去遍历的邻居的邻居,一种侧重深度优先(Depth-first),先找邻居,然后邻居的邻居,邻居的邻居的邻居....到最深处了 才会罢休。 这是遍历的两种基本思路. 如果能把细节在完善完善就成了基本的BFS(Bread-First Search) 和DFS(Depth-First Search). 图中


2.2 BFS 

上面只是介绍了BFS的基本思路,和写出这个算法还差了很远,因为还有大量的细节问题要考虑。把需要解决的problem && solution 如下:

Problem #1:  怎么才能高效的遍历呢,在最开始说了,争取不要走回头路和绕弯弯,一条路只做过一次,就是最棒的了,但是当你面对一个新地点时,如何知道自己是否来过,人说我就是知道自己来过没有, 我有记忆力啊,但其实记忆力的本质还是信息,所以我们拿出一个变量作为这个点是否被遍历过的信息载体,称之color,没有来过的点统一是white,每到一个新地点,第一件事就先记录一下自己来过,把他的color改成black,当遇到一个新地点的时候,我们就看看他的color是什么颜色就知道自己是否来过了,(这种思想和很多人去旅游景点喜欢写个XXX到此一游的思路一样,我觉得这些人一定有宏伟的周游世界的计划,通过这样的标记技术让自己的周游世界是个高效的遍历)

Problem #2: BFS的思路是先遍历完全部的邻居,然后再遍历邻居的邻居,说起来很简单,但是把这件事具体来说,第一个任务遍历A的邻居adj[A],假设A有1000个邻居A1,A2.。。A1000,当我们遍历了A1000以后,我们该做的是遍历邻居的邻居了吧,这就要求我们从新回到A1,去看看A1的邻居有什么,这样就2了,因为说好的不走回头路呢,于是更好的办法是那个小本本记得点东西,重新来一遍刚才的过程,从A出发,遍历了adj[A],第一步去到了A1,这会拿出你的小本本记录一下A1的邻居,这样做的好处就不用重新回头去A1在看A1的邻居是谁了,把每步得到的信息量最大化,再仔细想想小本本上的记录顺序呢,更完善 的情况应该是从A出发的时候 就先把A的adj[A]都记录下来 这样记录的第一行信息就是A1,A2.。。。A1000这些都是A的邻居信息,根据这个信息 我们可以走第二步了,第二步我们根据本的提示,找到一个记录A1,去访问了A1,同时在本的最后记录下A1的全部邻居信息 A11,A12.。。。。于是在我们往后遍历的过程中,所有的顺序全部被这个本指导了,我们发现了一个很有意思的现象,先被写在本上的信息 会被先访问,访问一次后要做两件事,把这个访问过的划掉,同时往最后的记录上加上当前节点的所有邻居信息,于是从这个本insert都是插入到结尾,而pop都是从头取出,这就是一个基本的先进先出队列Q,恩 通过这个Q我们控制了访问了的顺序。

Problem #3 考虑一下初始条件,一开始除了我们的出发点,其他所有的点都是没有见过的吧,所以初始点s是black,V-{s}的点都是white。我们在加上两个信息,这样遍历之后我们就能通过这两个信息完成对这个G的一些了解了。 第一个信息是u.π 这个代表了一个节点的父节点,所谓父节点就是如果存在一条边(u,v),如果u先被访问了,v又通过u被访问了,u就是v的父节点。 第二个信息是v.d,v.d = u.d +1;这代表了每个节点到咱们初始点的一个评估距离,这个距离在BFS里是u到s的最小边数,好,那这两个值在初始化的时候怎么设定呢,显然,一步为走的时候,咱们觉得每个点(除了初始点s)都不可达,因为没走呢,不知道啊所以所有的v.d = +∞,所有的v.π (除了初始点s)都不知道 设置为NIL 表示为不知道,初始点s的s.d =0,因为s到s 不需要边对吧,s.π =NIL,既然没有边了,既然也没有父节点,这种问题,就好比问爸爸的爸爸的爸爸的。。。爸爸。。最后关于初始的那个男人他的父亲不好判定吧。


基本问题确定之后开始写伪代码

BFS_OneSource(G,s){//G为图,s为随机的一个起点

//开始初始化

for(v in G.V)

{

v.color =WHITE;

v.d=+∞;

v.π =NIL;

}

//初始化s

s.d =0

s.color =BLACK;

//初始化Q

Q=0;

ENQUEUE(Q,s);

//开始遍历

while(QØ) //小本本上还要你要去看的地方啊!

{

u = DEQUEQUE(Q,S) //看看第一行是什么

for each v in u.adj

{

if (v.color == WHITE) // 这个点还没去过,记住要高效的遍历,拒绝回头路

{

v.color = BLACK //老子到此一游

v.d=u.d+1

v.π =u //认爸爸

ENQUEUE(Q,v) //记录小本本

}

}

}

}




但是等看了DFS之后就看明白一个事,这个给出的BFS只能是One_Source 的算法,而不是G的基本BFS算法,写的不是很好,因为这个BFS 最后只是建立了一颗以s为roote的tree,如果G是互联的 当然就是一颗树,但是如图也有可能存在单独的点,单独的线, 不相关的很多树,这个算发只能发现一颗,就呵呵了吧,所以要是有时间我会尝试修改一下这个BFS_OneSource to 真BFS,虽然这个只能发现一棵树的BFS在算法导论里被直接成为BFS了吧,但是就是那样,解决的是特定问题。

又看了一遍,发现这个BFS解决的是无向图问题,所以不存在说的上面的问题。。。又naive了


算法复杂度分析

1.初始化V个点 需要时间o(V);

2.遍历的控制是由Q决定的,每个V进出Q一次,所以while的次数是V次 而while内部的for循环,虽然很难计算每一个次数,但是总体上看for就是把E遍历了一遍,所以while这部分的时间是O(V+E),整体是O(V+V+E),最后是O(V+E)


算法理解

1.从成果来看,BFS一次得到了两个信息,一个是v.d,还有一个是v.π,至于为什么要得到这两个信息,可不可以得到其他的 当然可以了,取决你想要什么。BFS只是一个遍历的思路,至于再遍历过程中你想获得什么信息,自己设定信息位,然后又BFS控制遍历顺序和保证高效遍历获得。BFS只是给出了你一种环游世界的走法,至于你环游世界过后获得了什么,也许有人收集了很多这个世界过程中的美食或者美景的照片,这取决于一开始使用BFS的目的,取决于环游世界的目的,当然也有人什么都不记录,就是遍历了一次,这就是最朴素的遍历思想了。所以BFS才是一个基本工具,提供你一个高效的遍历方法,让你通过这样高效的遍历获得你需要的信息。

2.最近在看NP problem中的broadcasting问题,隐约觉得很多问题抽象出来都是集合的扩张问题,难点是扩张方向的判定,BFS给了一种朴素的解决办法,因为他的边权值就是0或者1,可以扩张和不可以扩张,但是如果权值是正实数,怎么是最优高效的扩张就不是一件这么好判定的事了。


3.BFS和Shortest Path。SPF问题就是上面说的那种问题,权值不在限于0,1了但是BFS确实是只有0,1权值时求SPF的一种办法,因为如果按动态规划DP的思想去考虑BFS,BFS 和DP的核心都是按stage 前进, 确定出每个stage都是最优的走法,BFS把stage看成了是距离s的层数。完全符合DP的思路,即最优子结构。