Skip to content

Latest commit

 

History

History
196 lines (155 loc) · 4.36 KB

6. 深度优先搜索.md

File metadata and controls

196 lines (155 loc) · 4.36 KB
Raw

Introduction

这篇笔记我们讨论深度优先搜索，也就是 DFS。

首先是 DFS 的伪代码：

DFS(v):
  if v is unmarked
    mark v
    for each edge v -> w
      DFS(w)

针对整个图的 DFS：

DFSAll(G):
  Preprocess(G)
  for all vertices v
    unmark v
  for all vertices v
    if v is unmarked
      DFS(v)

DFS(v):
  mark V
  PreVisit(v)
  for each edge vw
    if w is unmarked
      parent(w) <- v
      DFS(w)
  PostVisit(v)

Preorder and Postorder

通过使用下面的算法替换 Preprocess, PreVisit, PostVisit 的算法，我们可以获取先序以及后序：

Preprocess(G):
  clock <- 0

PreVisit(v):
  clock <- clock + 1
  v.pre <- clock

PostVisit(v):
  clock <- clock + 1
  v.post <- clock

DFSAll(G):
  clock <- 0
  for all vertices v
    unmark v
  for all vertices v
    if v is unmarked
      clock <- DFS(v, clock)

DFS(v, clock):
  mark v
  clock <- clock + 1
  v.pre <- clock
  for each edge vw
    if w is unmarked
      w.parent <- v
      clock <- DFS(w, clock)
  clock <- clock + 1
  v.post <- clock
  return clock

从小到大排列每个节点的 pre 和 post 就是图的 preordering 以及 postordering。

Detecting Cycles

有向无环图，简称 DAG，是那种有向的无环的图。

检查一个图是否包含圈是一个非常常用的操作。

我们可以使用 DFS 来检测一个图是否包含圈。

伪代码如下：

IsAcyclic(G):
  for all vertices v
    v.status <- NEW
  for all vertices v
    if v.status = NEW
      if IsAcyclicDFS(v) = False
        return False
  return True

IsAcyclicDFS(v):
  v.status <- ACTIVE
  for all edges vw
    if w.status = ACTIVE
      return False
    else if w.status = NEW
      if IsAcyclicDFS(w) = False
        return False
  v.status <- FINISHED
  return True

拓扑排序

拓扑排序指的是将节点排列成一条直线，并且所有的边从左边指向右边。

如果图包含圈，那么很明显拓扑排序就是不可能存在的，因为直线上最右边的节点肯定会有指向左边的边。

另外，在一个 DAG 中，the reversal of any postordering 就是一个拓扑排序。因为如果在 DAG 中，针对任意一条边 u -> v， u.post > v.post。

如果我们想要以反向拓扑排序的顺序处理节点，那么可以使用下面的算法：

PostProcess(G):
  for all vertices v
    v.status <- NEW
  for all vertices v
    if v.status = NEW
      PostProcessDFS(v)

PostProcessDFS(v):
  v.status <- ACTIVE
  for each edge v -> w
    if w.status = ACTIVE
      fail gracefully
    else if w.status = NEW
      PostProcessDFS(w)
  v.status <- FINISHED
  Process(v)

如果我们已经知道图是 DAG 的话，那么算法可以简化为下面这样：

PostProcessDAG(G):
  for all vertices v
    unmark v
  for all vertices v
    if v is unmarked
      PostProcessDAGDFS(v)

PostProcessDAGDFS(v):
  mark v
  for each edge v -> w
    if w is unmarked
      PostProcessDAGDFS(w)
  Process(v)

强连接组件

首先，强连接组件是针对 directed-graph 的。

强连接：如果针对两个节点 u 和 v，u 有到达 v 的路径，v 也有到达 u 的路径，那么 u 和 v 就是强连接的。

强连接组件：G 的一个强连接组件就是 G 的一个最大强连接子图。

强连接组件图：将每个强连接组件视作为一个节点，只保留强连接组件间的边。

最直接的寻找一个节点的强连接组件的方法就是获取 reach(v) 和 reach-1(v)，然后取它们的交集。我们可以在该算法的外面加上我们之前使用过的 all 包裹器来实现寻找所有的强连接组件。这个算法需要 O(VE)。存在着时间复杂度为 O(V + E) 的强连接组件算法。

线性强连接组件算法的名字是 Kosaraju and Sharir's Algorithm，下面是该算法的伪代码：

KosarajuSharir(G):
  S <- new empty stack
  for all vertices v
    unmark v
    v.root <- Null
  // phase 1: Push in postorder in rev(G)
  for all vertices v
    if v is unmarked
      PushPostRevDFS(v, S)
  // phase 2: DFS again in stack order
  while S is not empty
    v <- pop(S)
    if v.root = Null
      LabelOneDFS(v, v)

PushPostRevDFS(v, S):
  mark v
  for each edge u -> v  <<Reversed!>>
    if u is unmarked
      PushPostRevDFS(u, S)
  push(v, S)

LabelOneDFS(v, r):
  v.root <- r
  for each edge v -> w
    if w.root = Null
      LabelOneDFS(w, r)