Luna Tech

Tutorials For Dummies.

Graph: General Depth First Search

2021-05-05


0. 前言

Reference: 8.15-8.16

上一篇的 DFS 是一种特殊的 DFS,因为它的目标是找到一条路径,这条路径不包含任何的重复访问(也就是 create the deepest depth tree without any branches)。


1. General Depth First Search

General DFS 难还是特殊 DFS 难?

General 的 DFS 比特殊的 DFS 要容易一些,因为它的目标是尽可能深入地找、尽可能连接更多的node,需要的时候就分叉:

只能找到一条路径吗?

这种 DFS 可以找到不止一条路径,假如它找到了多于一条的路径,那么我们就把这些路径叫做 depth first forest(深度优先森林 - 好文艺的名字)。

如何构造 search tree?

DFS 和 BFS 一样,也会利用 predecessor 的信息来构造 tree。

DFS 的 Node 还需要额外的两个变量,一个是 discovery time,一个是 finish time。

Discovery time 用来记录这个 node 第一次被访问时我们一共走了多少步。

Finish time 就是一个 node 被标记为黑色(访问结束)之前我们一共走了多少步。


2. General DFS Code

# pip3 install pythonds
from pythonds.graphs import Graph
class DFSGraph(Graph):
    def __init__(self):
        super().__init__() # inherit from Graph
        self.time = 0 # extra field
    
    # extra method
    def dfs(self):
        for aVertex in self:
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)
                
    # extra method, helper
    def dfsvisit(self,startVertex):
        startVertex.setColor('gray')
        self.time += 1
        startVertex.setDiscovery(self.time)
        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setPred(startVertex)
                self.dfsvisit(nextVertex)
        startVertex.setColor('black')
        self.time += 1
        startVertex.setFinish(self.time)

3. 图解 DFS 步骤

1. 构造 DFS tree,从 A 开始,A 变灰色

A 的 Discovery time = 1

2. A 到 B

A 有两个 child,B 和 D,我们根据字母顺序选 - B

B 的 Discovery time = 2

3. B 到 C (继续深入)

B 有两个 child,C 和 D,我们根据字母顺序选 - C

C 的 Discovery time = 3

4. C 没有 child,所以变成黑色(访问结束)

C 是这个 branch 里面的最后一个 node,所以C 的 finish time = 4(注意这里即使没有访问新的 node,也要在 Discovery time 上 + 1)。

5. 回到 B,访问它的另一个 child - D

6. 继续访问 D 的 child - E

7. 继续访问 E 的 child - F

E 有两个 child - B 和 F,因为 B 已经是灰色了,所以我们不能继续访问 B(会陷入死循环)。

8. F 的 child 是 C,C 是黑色,所以 F 开始返回起点

F 也被标记成黑色,这个 branch 访问结束。

9. 从 F 返回 E,E 的两个 child 都被访问过,所以 E 变黑

10. 从 E 返回 D,D 变黑

11. 从 D 返回 B,B 变黑

12. 从 B 回到 A,整条路径完成

A - B - D - E - F - C

parenthesis property 括号属性

每个 node 的 discovery time 和 finish time 被称为括号属性。

它表示在 DFS tree 里面的任何一个 node 的所有 children 都有:

The starting and finishing times for each node display a property called the parenthesis property. This property means that all the children of a particular node in the depth first tree have a later discovery time and an earlier finish time than their parent.

Breadth First Forest

我们也可以创建一个 breadth first forest,代表所有graph中两个node的最短距离。

Although our implementation of bfs was only interested in considering nodes for which there was a path leading back to the start, it is possible to create a breadth first forest that represents the shortest path between all pairs of nodes in the graph.


4. DFS 效率分析

Main Method

def dfs(self):
  for aVertex in self:
    aVertex.setColor('white')
    aVertex.setPred(-1)
  for aVertex in self:
     if aVertex.getColor() == 'white':
        self.dfsvisit(aVertex)

时间复杂度: O(n)

Helper Method

def dfsvisit(self,startVertex):
    startVertex.setColor('gray')
    self.time += 1
    startVertex.setDiscovery(self.time)
    for nextVertex in startVertex.getConnections():
        if nextVertex.getColor() == 'white':
            nextVertex.setPred(startVertex)
            self.dfsvisit(nextVertex)
    startVertex.setColor('black')
    self.time += 1
    startVertex.setFinish(self.time)

helper method 的时间复杂度等于一个 node 的 edge 数量,就是 O(m)。

DFS

总的时间复杂度=O(n+m)


5. 结语

这篇感觉教程只写了一半?引入了 start time 和 finish time,却没有用到这两个变量……

逻辑很清楚,图解也看懂了,但是实际的使用可能还要再查一下其他的资料。

下一篇讲的就是实际的应用 - Topological Sorting。