Skip to main content

Depth-First Search

Using recursion/stack.

Color​

  • white: 未被发现/访问
  • gray: 已被发现, 未二次访问
  • black: 已被发现, 二次访问(比其深的所有结点皆被发现)

当第一个访问 edge(u,v) 时:

  • v.color == white: 树边
  • v.color == gray : 后向边(v 为 深度优先森林的祖父结点)
  • v.color == black: 前向边/横向边(v 为较深的结点/子结点)
  • 无向图深度优先遍历不会出现 前向边/横向边

Parent​

比 v 浅的结点(比 v 更早被发现的结点)

Distance​

  • v.d = ++time: 被发现的时间戳(入栈)
  • v.f = ++time: 被二次访问的时间戳(出栈)
  • time<v.d, white; v.d<time<v.f, gray: time>v.f, black

Mark and Recursion​

Using mark array, mark stack, and recursion:

  • Longest Paths.