Day-29 Depth-First-Search(DFS), 深度优先搜寻

DFS介绍

与昨天BFS不同的地方在於,BFS是给定一个节点s,接着找到s可以到达的所有节点,而DFS是遍历整张图,如果我们给定特定的节点s,我们使用BFS可能无法遍历整张图。

DFS顾名思义,就是尽量的深入遍历整张图。找到一个节点v,遍历所有v能够到达的节点,一但v能够到达的节点都已经被发现,则回朔到v的前驱节点,也就是v的父节点,接着以该节点作为出发的节点,继续寻找能够到达的节点,不断重复这样的过程,直到整张图被遍历。

和前面的BFS一样,为了方便演示,使用三种颜色来标记节点,还没被发现的节点涂上白色,节点被发现後涂成灰色,在该节点的邻接串列被遍历完成後涂成黑色。

DFS还会在每一个节点上做一个时间注记,每个节点v共有两个时间注记,第一个时间注记v.d记录节点v第一次被发现的时间,第二个时间注记v.f记录v的邻接串列被扫描完成的时间,也就是结点v被涂上黑色的时候。

下面为DFS的虚拟码,输入一张图https://chart.googleapis.com/chart?cht=tx&chl=G%3D(V%2CE),可以是有向图,也可以是无向图。time是一个全域变数,用来计算时间注记。

DFS(G)
for each vertex u ∈ G.V
  u.color = WHITE
  u.π = NULL
time = 0
for each vertex u ∈ G.V
  if u.color == WHITE
    DFS-VISIT(G, u)
    
DFS-VISIT(G, u)
time = time + 1
u.d = time
u.color = GRAY
for each v ∈ G:Adj[u]
  if v.color == WHITE
    v.π = u
    DFS-VISIT(G, v)
u.color = BLACK
time = time + 1
u.f = time

在DFS执行过程中,第1到3行遍历属於G图中V集合内的所有点u,将这些节点涂成白色,前驱节点设成NULL。

第5到7行一次对每一个节点进行检查,如果发现到结点颜色为白色,那麽呼叫DFS-VISIT进行走访。

呼叫DFS-VISIT时,会产生出以u作为根节点的树,位於原本DFS Tree当中,也就是说,当我们完成整个DFS,会产生出一棵巨大的树,每一个子节点都是一棵树,就像是森林一般。当DFS回传时,每个节点u都会被打上时间标记,被发现的时间储存到u.d,u的邻接串列被完成走访的时间储存到u.f。

在DFS-VISIT中,让time这个计时器开始推进,并将u的颜色变成灰色的这个时间点储存到u.d中,接着for回圈对节点u对应到的邻接串列中,每一个节点v进行检查,当v为白色,则不断的递回走访,不断深入整张图,直到u对应到的邻接串列都被走访完毕,这时候将u标记为黑色,并将该时间点储存到u.f中。


给定一张图 虚线表示非DFS树的边,而是图的边

  • (a) 从u节点开始,每一个节点中的数字代表两个时间注记。

  • (b) u节点递回走访走到v节点,v节点涂上灰色,且标记父节点为u节点,并将变成灰色的时间点储存到v.d。

  • (c) 接着v节点递回走访到y节点,并将y变成灰色,y的父节点为v,同时将变成灰色的时间点储存到y.d。

  • (d) 接着y递回走访到x,x的父节点为y。

  • (e) 接着x开始递回走访,发现y节点和u节点都已经走访过,而这就表示x的邻接串列中所有节点都已经被走访。

  • (f) 当x的邻接串列中所有节点都已经走访完毕,将x涂成黑色,并记住涂成黑色的时间点,储存到x.f。

  • (g) x节点开始回朔到父节点y,y的邻接串列已经走访完毕,将y涂成黑色,并记住涂成黑色的时间点,储存到y.f。

  • (h) y节点开始回朔到父节点v,v的邻接串列已经走访完毕,将v涂成黑色,并记住涂成黑色的时间点,储存到v.f中。

  • (i)(j) v节点回朔到u节点,u节点的邻接串列已经走访完毕,将u涂成黑色,并记录涂成黑色的时间点,储存到u.f中。


u点已经遍历完成,接着从v点开始,v点的邻接串列中所有节点皆已经走访完毕,故不做任何动作,接着从y点开始走访

  • (l) y节点递回走访到w节点,w节点涂成灰色,w节点的父节点为y,同时将变成灰色的时间点储存到w.f。
  • (m) w节点递回走访到z节点,z节点涂成灰色,z节点的父节点为w,同时将变成灰色的时间点储存到z.f。
  • (o) z节点发现所有节点都已经走访完毕,表示z节点的邻接串列中所有节点都已经走访完毕,故将z节点变成黑色,并记录下z节点变成黑色的时间点,储存到z.f中。
  • (p) z节点回朔到父节点w,w节点发现所有节点都已经走访完毕,表示w节点的邻接串列都已经走访完毕,故将w节点变成黑色,同时储存w节点变成黑色的时间点,储存到w.f中。
  • 接着每一个节点都发现与该节点关连的邻接串列都已经走访完毕,故DFS已经走访整张图,整个走访结束。

DFS效率

在DFS函式中,有两个for回圈,都需要跑https://chart.googleapis.com/chart?cht=tx&chl=%7CV%7C次,需要的时间为https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(V),而对於每一个位於集合https://chart.googleapis.com/chart?cht=tx&chl=V中的节点,DFS-VISIT只会被呼叫一次,原因在於要成功呼叫DFS-VISIT的条件是该节点是白色的,而只要成功呼叫到DFS-VISIT,该节点就会变成灰色的,而因此不会被二次呼叫。

在DFS-VISIT中,for回圈的迭代次数取决於u节点关连到的邻接串列的长度,也就是https://chart.googleapis.com/chart?cht=tx&chl=%7CAdj%5Bu%5D%7C。而无论我们给定的是有向图,还是无向图,他们边的数量皆为https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(E),因此在DFS-VISIT中,需要的时间为https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(E),因此,整体时间需要https://chart.googleapis.com/chart?cht=tx&chl=%5CTheta(V%20%2B%20E)

边的分类(Edge classification)

在上面图中,我们使用了F, B, C来区分一些边,下面将说明这些边的性质

  • Tree edge 若可以经由一条边走访到新的节点,则称该边为Tree edge,在上图中,实心线皆是Tree edge,而那些虚线的部分,我们可以分为三个种类
    • Forward edge : 可以直接存取到子孙的边,像是x为u的子孙,因此u和x之间的边为Forward edge
    • Backward edge : 可以直接存取到祖父的边,像是v为x的祖父,因此v和x之间的边为Backward edge
    • Cross edge : 如果将图表示成DFS Tree,可以发现Cross连接了两棵子树。

而节点的颜色,可以告诉我们一些边的讯息

  • 节点为白色,表示https://chart.googleapis.com/chart?cht=tx&chl=(u%2Cv)为Tree edge
  • 节点为灰色,表示https://chart.googleapis.com/chart?cht=tx&chl=(u%2Cv)为Back edge
  • 节点为黑色,表示https://chart.googleapis.com/chart?cht=tx&chl=(u%2Cv)为Forward edge或是Cross edge

如果给定的图是一张无向图,则只会存在Tree edge和Backward edge

说明:

  1. 不存在Forward edge
    给定一张有向图,A走访到B,再走到C,C回朔到A(这个回朔是递回的关系导致,不是直接往回走),然後A走到C,在有向图中,是可能存在的。

    如果上面这是一张无向图,则A走到B,B走到C,C是可以走到A的,因为没有方向限制,所以会变成往回走,就无法形成Forward edge了,而是变成Backward edge。
  2. 不存在Cross edge
    给定一张有向图,A走访到B,接着回朔到A,A是B的父节点,A接着走访到C,A是C的父节点,C接着走访到B,等於是从一个子树,走到另外一个子树,因此这是Cross edge

    但如果这是一张无向图,则A走到B,B走到C,C走到A,A是B的父节点,B是C的父节点,就无法形成Cross edge,而是每一条边都是Tree edge。

有了这一些边的性质,我们可以应用在一些方面,像是侦测一个图中是否有环产生。

环(Cycle)的侦测与DFS性质

只要有Back edge https://chart.googleapis.com/chart?cht=tx&chl=%5CLongleftrightarrow那麽就表示图中有环产生,在有向图和无向图皆是如此,以下证明有向图的两种情况

  1. 证明只要有Back edge https://chart.googleapis.com/chart?cht=tx&chl=%5Cleftarrow 就有环产生

    这张图就是一个环,D是E的父亲,A是E的祖父,存在Back edge。
  2. 证明只要有Back edge https://chart.googleapis.com/chart?cht=tx&chl=%5Crightarrow 就有环产生

    这个情况比较麻烦,我们必须先做出一些假设:
    假设https://chart.googleapis.com/chart?cht=tx&chl=V_0是第一个被DFS发现的节点,也就是第一个变成灰色的,我们要证明的是https://chart.googleapis.com/chart?cht=tx&chl=(V_k%2CV_0)会是Back edge。

我们知道https://chart.googleapis.com/chart?cht=tx&chl=V_1会在https://chart.googleapis.com/chart?cht=tx&chl=V_0之前完成DFS递回走访,也就是https://chart.googleapis.com/chart?cht=tx&chl=V_1会在https://chart.googleapis.com/chart?cht=tx&chl=V_0之前变成黑色,最先变成灰色的点,会最晚变成黑色,也就是Stack的概念,本质上是递回呼叫,我们可以拓展这个概念,通过归纳法,可以得知https://chart.googleapis.com/chart?cht=tx&chl=V_i会比https://chart.googleapis.com/chart?cht=tx&chl=V_%7Bi-1%7D还要早变成黑色,再拓展,可以知道https://chart.googleapis.com/chart?cht=tx&chl=V_k会在https://chart.googleapis.com/chart?cht=tx&chl=V_0之前变成黑色,那麽我们就找到https://chart.googleapis.com/chart?cht=tx&chl=(V_k%2CV_0)为Back edge了,递回过程看起来大致上如下。

我们会发现这是一个十分平衡的过程,如果将上面那张图的DFS过程换一种形式表达

可以发现到这个有趣的性质,并且如果有两个时间区间出现重叠,则表示较小区间的较大大区间的後代。

参考资料:Introduction to algorithms 3rd


<<:  Day 25 : 插件篇 04 — 如何让 Obsidian 自动推荐关联笔记 (下)?介绍我的笔记架构与 Breadcrumbs 实战应用

>>:  Flutter基础介绍与实作-Day26 旅游笔记的实作(7)

mostly:functional 第二十八章的试炼: Applicative 的证明

小测验 我们在上一章的最开始,示范了元组上的 <*>,其中有一条是这样写的: pure ...

Day 12单一子元素元件Single-child

单一子元素元件包含Container、Padding、Center、Align、FittedBox、...

撰写http request 的复杂一点的测试(Day26)

以下内容同步更新於 https://kevinyay945.com/smart-home-tutor...

Day4. 一起精通 Rails Array,处理更复杂的问题

接下来Day4-6的用法,都是由Ruby的Enumerable。Enumerable 是Ruby相当...

Day11 Buddy, slab 记忆体管理大将

前言 昨天讲过了远古时代的记忆体管理,跟後续为了解决最古老的记忆体管理所引发的问题而接着有的分段管理...