与昨天BFS不同的地方在於,BFS是给定一个节点s,接着找到s可以到达的所有节点,而DFS是遍历整张图,如果我们给定特定的节点s,我们使用BFS可能无法遍历整张图。
DFS顾名思义,就是尽量的深入遍历整张图。找到一个节点v,遍历所有v能够到达的节点,一但v能够到达的节点都已经被发现,则回朔到v的前驱节点,也就是v的父节点,接着以该节点作为出发的节点,继续寻找能够到达的节点,不断重复这样的过程,直到整张图被遍历。
和前面的BFS一样,为了方便演示,使用三种颜色来标记节点,还没被发现的节点涂上白色,节点被发现後涂成灰色,在该节点的邻接串列被遍历完成後涂成黑色。
DFS还会在每一个节点上做一个时间注记,每个节点v共有两个时间注记,第一个时间注记v.d记录节点v第一次被发现的时间,第二个时间注记v.f记录v的邻接串列被扫描完成的时间,也就是结点v被涂上黑色的时候。
下面为DFS的虚拟码,输入一张图,可以是有向图,也可以是无向图。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点开始走访
在DFS函式中,有两个for回圈,都需要跑次,需要的时间为,而对於每一个位於集合中的节点,DFS-VISIT只会被呼叫一次,原因在於要成功呼叫DFS-VISIT的条件是该节点是白色的,而只要成功呼叫到DFS-VISIT,该节点就会变成灰色的,而因此不会被二次呼叫。
在DFS-VISIT中,for回圈的迭代次数取决於u节点关连到的邻接串列的长度,也就是。而无论我们给定的是有向图,还是无向图,他们边的数量皆为,因此在DFS-VISIT中,需要的时间为,因此,整体时间需要。
在上面图中,我们使用了F, B, C来区分一些边,下面将说明这些边的性质
而节点的颜色,可以告诉我们一些边的讯息
如果给定的图是一张无向图,则只会存在Tree edge和Backward edge
说明:
有了这一些边的性质,我们可以应用在一些方面,像是侦测一个图中是否有环产生。
只要有Back edge 那麽就表示图中有环产生,在有向图和无向图皆是如此,以下证明有向图的两种情况
我们知道会在之前完成DFS递回走访,也就是会在之前变成黑色,最先变成灰色的点,会最晚变成黑色,也就是Stack的概念,本质上是递回呼叫,我们可以拓展这个概念,通过归纳法,可以得知会比还要早变成黑色,再拓展,可以知道会在之前变成黑色,那麽我们就找到为Back edge了,递回过程看起来大致上如下。
我们会发现这是一个十分平衡的过程,如果将上面那张图的DFS过程换一种形式表达
可以发现到这个有趣的性质,并且如果有两个时间区间出现重叠,则表示较小区间的较大大区间的後代。
参考资料:Introduction to algorithms 3rd
<<: Day 25 : 插件篇 04 — 如何让 Obsidian 自动推荐关联笔记 (下)?介绍我的笔记架构与 Breadcrumbs 实战应用
>>: Flutter基础介绍与实作-Day26 旅游笔记的实作(7)
小测验 我们在上一章的最开始,示范了元组上的 <*>,其中有一条是这样写的: pure ...
单一子元素元件包含Container、Padding、Center、Align、FittedBox、...
以下内容同步更新於 https://kevinyay945.com/smart-home-tutor...
接下来Day4-6的用法,都是由Ruby的Enumerable。Enumerable 是Ruby相当...
前言 昨天讲过了远古时代的记忆体管理,跟後续为了解决最古老的记忆体管理所引发的问题而接着有的分段管理...