DFS 深度优先搜索

  • 方法简述
  • 伪代码
  • 应用
  • BFS与DFS比较

和广度优先搜索一样,深度优先搜索是最简便的图搜索算法之一,也是一种在开发爬虫早期使用较多的方法。

方法简述

它的思想是从一个顶点开始,沿着一条路一直走到底,如果发现不能到达目标解,那就返回到上一个节点,然后从另一条路开始走到底,这种尽量往深处走的概念即是深度优先的概念。这里面也有递归的思想。

在储存节点上可以采用堆栈,为后进先出(LIFO)。深度优先搜索有这几步:

  1. 取出堆栈栈顶节点x。
  2. 遍历图中与x相连接的节点。如果该节点未被探索过(unexplored),标记为探索过(explored),并将其加入到堆栈。
  3. 当堆栈为空时,结束。

伪代码

while S:               # 当堆栈S不为空
    x = S.pop(-1)      # 取出S的栈顶(最后一个节点),称为x
    for y in edge(x):  # 遍历每个和x连接的点y
        if y unexplored:
            标记y为explored
            S.append(y)# 将y加入到S

应用

  1. 拓扑排序(Topological Sort)
  2. 寻找强连通分量(Strongly Connected Components)
  • 拓扑排序(Topological Sort)

对于一个有向无环图(DAG, Directed Acyclic Graph)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>\in E(G),则u在线性序列中出现在v之前。

拓扑排序通常用来“排序”具有依赖关系的任务。比如,如果用一个DAG图来表示一个工程,其中每个顶点表示工程中的一个任务,用有向边表示在做任务B之前必须先完成任务A。故在这个工程中,任意两个任务要么具有确定的先后关系,要么是没有关系,绝对不存在互相矛盾的关系(即环路)。

示例:

伪代码:

DFS-Loop(graph G):
    标记所有节点为unexplored
    current_label = n    # n为节点数
    for each vertex x:   # 对每个节点x
        if x unexplored: # 判断是否被探索
            DFS(G, x)    # 以x为起始节点进行深度优先搜索
        label(x) = current_label
        current_label -= 1

这里的label即为顺序,也有的例子中采用倒序排finishing time来实现,label从1开始排即可,本质是一样的,可以参考寻找强连通分量部分。

DFS部分的伪代码与第二部分伪代码虽有不同,但思想一样:

DFS(graph G, start vertex x):
    for every edge (x,y):
        if y unexplored:
            标记y为explored
            DFS(G, y)
  • 寻找强连通分量(Strongly Connected Components)

在一个有向图中,如果节点u到节点v有通路,并且节点v到节点u也有通路,那么称u和v强连通,它们组成强连通分量(SCC)。

在寻找图中的强连通分量时,可以采用Kosoraju’s Two-Pass算法。这个算法操作简单,但是证明部分有些繁琐,在此不以证明。该算法主要有以下几步:

  1. 得到G的反向图GT。(G中的边反向)
  2. 对GT进行DFS-Loop。这一步是为了确定节点的特定顺序,得到每个节点的finishing time。
  3. 对G进行DFS-Loop。这一步是为了一个个找出SCC,倒序finishing time遍历unexplored节点。

值得注意的是,有些地方会先对G进行DFS-Loop,再对GT进行。这两个是可以互换的,最终都能得到图中的SCC。

伪代码:

DFS-Loop(graph G):
    标记所有节点为unexplored
    t = 1
    s = null
    for i=n down to 1: # 假设每个节点有一个编号
        if i unexplored:
            s = i
            DFS(G, i)    # 以i为起始节点进行深度优先搜索
        label(x) = t
        t += 1

这一部分与拓扑排序一样,只是改用finishing time。

示例:

首先对图G中节点进行编号(任意)。

对反向图GT进行DFS-Loop,计算finishing time。

对finishing time在G上进行倒序遍历。

BFS与DFS比较

  1. 数据结构:BFS用队列,先进先出;DFS用堆栈,后进先出。
  2. 复杂度:BFS牺牲空间复杂度换取时间复杂度;DFS牺牲时间复杂度换取空间复杂度。
  3. 思想:均为穷举。

参考资料

  1. 【算法入门】 深度优先算法
  2. Stanford算法课
  3. 拓扑排序(Topological Sort)
  4. 知乎 搜索思想——DFS & BFS(基础基础篇)

You May Also Like

About the Author: 雪球

一个在读的工科研究生 一个努力追赶时代脚步的人 Github: https://github.com/xueqiwang0v0 LinkedIn: https://www.linkedin.com/in/xueqi-wang-0939b51a6/

发表评论

邮箱地址不会被公开。 必填项已用*标注