DFS & BFS

June 12, 2025 6 分钟阅读

0. VocabularyPermalink

Topological Sort: refers to the result of ordering, i.e. the order
Topological Sorting: refers to the precedure/algorithm of sorting
Topological Space: See Topology / Topological Space
Simple Graph: refers to graphs with no loops nor parallel edges. See Basic Graph Algorithms
DAG: Directed Acyclic Graph. See Basic Graph Algorithms
Strict Partial Order, Strict Weak Order, Strict Total Order: See Relation (Math) and Asymptotic Notations

1.Digression: What does “topological” mean in topological sorting?Permalink

ChatGPT 给我的一个答案是：

It’s an unfortunate naming overlap. The term “topology” in graph theory means “the layout or structure of connections,” which is different from its meaning in topology as a branch of math.

这个 “the layout or structure of connections” 的意思，按某些网友的说法，应该是 Network topology 的研究领域 (参考 Why is “topological sorting” topological?)

但如果我硬要把 topological sorting 和 topological space 扯上关系呢？也不是不行。实际上，从 graph 可以 induce 出多种类型的 topological spaces，比如：

这篇 Kilicman, Adem, and Khalid Abdulkalek. “Topological spaces associated with simple graphs.” Journal of Mathematical Analysis 9.4 (2018): 44-52. 讲的就是从 simple graph 的 vertex set $V$ 出发构建一个 topological space
DeepSeek 给我的一个例子是：
- $\forall v_{i}, v_{j} \in V$ such that edge $e = (v_{i} \to v_{j}) \in E$ , define $(e, t)$ as a point somewhere between $v_{i}$ and $v_{j}$ on the edge, where $t \in (0, 1)$
  - $t \to 0$ 就是 approaching $v_{i}$
  - $t \to 1$ 就是 approaching $v_{j}$
  - 然后你任意的 edge 就可以映射到一个独立的 $[0, 1]$ 区间上，这些区间不在一个坐标系内，但 endpoint 是可以重叠的
  - 这么一来，只要有 edge $e = (v_{i} \to v_{j})$ ，那么在这条 edge 对应的 $[0, 1]$ 区间上，就有 $v_{i} < v_{j}$
- $X = V \cup {(e, t) ∣ e \in E, t \in (0, 1)}$ 构成 topological space 的 set
- topology $τ$ 太复杂这里就不写了

DeepSeek 这个例子有点绕，但你从它这个角度去理解 topological sort，也不是不行……

我这里讨论这个问题，主要是为了引出 “A graph is naturally a 1-dimensional topological space (sort of)” 这个观点，i.e. graph theory 和 topology space 的研究是可以联动的。

2. Is topological sort (on DAG) a relation (math)?Permalink

快速回顾一下 topological sort。它其实只要求：

Input: $G = (V, E)$
Output: A sequence of vertices $s = \overset{―}{v^{(1)} \dots v^{(n)}}$
如果存在 edge $v_{i} \to v_{j}$ ，那么 $v_{i}$ 一定要排在 $v_{j}$ 前面，i.e. 必须是 $s = \overset{―}{\dots v_{i} \dots v_{j} \dots}$ 这样的形式

2.1 DAG Reachability is a Strict Partial OrderPermalink

我们先考虑这个和 topological sort 相关的 relation: Reachable.

Definition: If there is an path $v_{i} \to \dots \to v_{j}$ , we say $v_{j}$ is reachable from $v_{i}$ , denoted by $v_{i} ⇝ v_{j}$

Claim: DAG Reachability is a Strict Partial Order. (Just like strict “subset” $\subset$ relation)

Proof:

(✅ Irreflexive) Obviously, $\forall v \in V$ , $v ⇝̸ v$ . Otherwise there would be a self loop $v \to \dots \to v$ , which contradicts the fact of DAG.

(✅ Asymmetric) Obviously, $\forall v_{i}, v_{j} \in V$ , $v_{i} ⇝ v_{j} \Rightarrow v_{j} ⇝̸ v_{i}$ . Otherwise there would be loop $v_{i} ⇌ v_{j}$ , which contradicts the fact of DAG.

(✅ Transitive) Suppose $v_{i} ⇝ v_{j}$ and $v_{j} ⇝ v_{k}$ , transitivity holds obviously.

$◼$

Claim: DAG Reachability is NOT a Strict Weak Order.

Proof: We reduce the problem to showing that the incomparable relation $⊘_{⇝}$ is NOT an equivalence relation.

Note that $v_{i} ⊘_{⇝} v_{j} ⟺ v_{i} ⇝̸ v_{j} \land v_{j} ⇝̸ v_{i}$ , i.e. the two vertices are not connected by any path. E.g.

(✅ Reflexive) Obviously, $\forall v \in V$ , $v ⊘_{⇝} v$ (any vertex is not reachable from itself)

(✅ Symmetric) Obviously, $\forall v_{i}, v_{j} \in V$ , $v_{i} ⊘_{⇝} v_{j} \Rightarrow v_{j} ⊘_{⇝} v_{i}$ (by definition of $⊘_{⇝}$ )

(❌ Transitive) Suppose $v_{i} ⊘_{⇝} v_{j}$ and $v_{j} ⊘_{⇝} v_{k}$ . It’s still possible that there is a $v_{i} \to \dots \to v_{k}$ or $v_{k} \to \dots \to v_{i}$ path.

flowchart LR
    v0(($$v_0$$)) --> vi(($$v_i$$))
    v0 --> vj(($$v_j$$))
    vi -.-> vk(($$v_k$$))

$◼$

Claim: DAG Reachability is NOT a Strict Total Order.

Proof: We reduce the problem to showing that relation $⇝$ is NOT connected.

(❌ Connected) $\forall v_{i}, v_{j} \in V$ , it’s possible that $v_{i} ⇝̸ v_{j}$ and $v_{j} ⇝̸ v_{i}$ , so $⇝$ is NOT connected.

$◼$

2.2 Digression: Visualize the reachability relation to recover the DAG (kind of)Permalink

如果 $\forall v_{i} ⇝ v_{j}$ , 我们都画一条 edge $v_{i} \to v_{j}$ ，我们最终能得到一个新的 graph $G^{'} = (V, E^{'})$ ，它不一定就是原来的 $G = (V, E)$ ，因为它可能有冗余的 edges。这里又引入了一个新的课题：Minimum Equivalent Graph (MEG).

MEG Problem: Given a DiGraph, find a smallest subset of $E$ that maintains all reachability relations between vertices.

这个问题我们就不展开了。但 $G^{'}$ 与 $G$ 肯定是能 reduce 到同一个 MEG.

2.3 Any FIXED Topological Sort is a Strict Total OrderPermalink

我们先不考虑 topological sorting 的不确定性 (即同一个 graph 可能有不同的 topological sort 结果).

但如果是一个特定的 topological sort，它本质就是个 sequence，所以一定是 Strict Total Order，类似 relation $<$ 和 sequence $1 < 2 < 3 \dots < n$ .

证明很直接，我们就略过了。

2.4 Topological Sorting is to construct a Linear Extension on DAG ReachabilityPermalink

我找了两个 Linear Extension 的定义，可以对比一下：

Definition: Given a partial order $\subseteq$ on a set $X$ , a linear extension is total order (a.k.a. linear order) $\leq$ on the same set $X$ such that identity function $I :\subseteq \to \leq$ is order preserving. $◼$

是不是有点没看懂？我们看下一个：

Definition: Given a partial order $\subseteq$ on a set $X$ , a linear extension is total order (a.k.a. linear order) $\leq$ on the same set $X$ such that:

$\forall a, b \in X$ such that $a \subseteq b$ , $a \leq b$
$\forall a, b \in X$ , either $a \leq b$ , or $b \leq a$ , or $a = b$

$◼$

换言之，linear extension on $\subseteq$ 做了两件事：

preserving of the old partial order
- i.e. $\forall (a, b) \in\subseteq$ , there must be $(a, b) \in\leq$
- 我们也称：total order $\leq$ preserves the partial order of $\subseteq$
augmentation to the new total order
- i.e. $\forall (a, b) \in ⊘_{\subseteq}$ , we add $(a, b)$ or $(b, a)$ to $\leq$
- i.e. reduce $⊘_{\subseteq}$ to empty set $\emptyset$ ; make $\leq$ connected
- augmentation 存在 arbitrariness，即我在 augmentation 的过程中并不 care 到底是 $a \leq b$ 还是 $b \leq a$

Any FIXED topological sort $≺$ is a linear extension on DAG Reachability $⇝$ . Augmentation 的 arbitrariness 也正是 topological sorting 结果的不确定性的原因。E.g.

flowchart LR
    v0(($$v_0$$)) --> vi(($$v_i$$))
    v0 --> vj(($$v_j$$))

对 $v_{i} ⊘_{⇝} v_{j}$ ，我们可以 augment 成 $v_{i} ≺ v_{j}$ (i.e. $s = \overset{―}{v_{0} v_{i} v_{j}}$ )，也可以 augment 成 $v_{j} ≺ v_{i}$ (i.e. $s = \overset{―}{v_{0} v_{j} v_{i}}$ )

Counting the number of linear extensions of a partial order is $# P$ -complete (and well studied).

3. How algorithms of DFS & BFS eliminate the arbitrarinessPermalink

如果我们处理的不是 graph $G$ 而是一棵 tree $T$ ，那么 DFS & BFS 本质上都是 $T$ 上的 topological sorting。进一步细分：

topological sorting on $T$
- DFS
  - pre-order (yields prefix notation)
  - in-order (yields infix notation)
  - post-order (yields postfix notation)
- BFS == level-order

3.1 Pre-order ( $\in$ DFS)Permalink

假设我们有这么一个简单的 tree $T$ :

flowchart TD
    r(($$r$$))
    l1(($$l_1$$))
    l2(($$l_2$$))

    r --- l1
    r --- l2

pre-order 相当于把 $T$ 改造成了 DAG $G_{1}$ :

flowchart TD
    r(($$r$$))
    l1(($$l_1$$))
    l2(($$l_2$$))

    r --> l1
    r --> l2

有 $r ⇝ l_{1}$ 和 $r ⇝ l_{2}$ ；对于 $l_{1} ⊘_{⇝} v_{2}$ ，我们人为选择 augment 成 $l_{1} ≺ l_{2}$ ；最终有 $r ≺ l_{1} ≺ l_{2}$ .

3.2 In-order ( $\in$ DFS)Permalink

in-order 相当于把 $T$ 改造成了 DAG $G$ :

flowchart TD
    r(($$r$$))
    l1(($$l_1$$))
    l2(($$l_2$$))

    r ~~~ l1 --> r
    l2 ~~~ r --> l2

我们人为选择了从 $l_{1}$ 开始而不是从 $l_{2}$ 开始。这已经是一个 linear order 了，所以 $l_{1} ≺ r ≺ l_{2}$ .

3.3 Post-order ( $\in$ DFS)Permalink

post-order 相当于把 $T$ 改造成了 DAG $G_{3}$ :

flowchart TD
    r(($$r$$))
    l1(($$l_1$$))
    l2(($$l_2$$))

    r ~~~ l1 --> r
    r ~~~ l2 --> r
    l1 ~~~ r
    l2 ~~~ r

有 $l_{1} ⇝ r$ 和 $l_{2} ⇝ r$ ；对于 $l_{1} ⊘_{⇝} v_{2}$ ，我们人为选择 augment 成 $l_{1} ≺ l_{2}$ ；最终有 $l_{1} ≺ l_{2} ≺ r$ .

3.4 Level-order (i.e. BFS)Permalink

与 pre-order 类似，但对 $l_{1}$ -subtree 和 $l_{2}$ -subtree 的处理有不同。

flowchart TD
    r(($$r$$))
    l1(($$l_1$$))
    l2(($$l_2$$))

    r --> l1
    r --> l2

    l1 -.-> v(($$v$$))

pre-order 中，我们相当于是人为 augment 了 $\forall v \in l_{1} -subtree, v ≺ l_{2}$ ；同时又因为 $l_{1} ≺ v$ (by definition of pre-order) 且 $l_{1} ≺ l_{2}$ (人为限定)，所以相当于是有:

pre-order := r ≺ l_{1} ≺ \underset{pre-order of l_{1} -subtree except l_{1}}{\underset{⏟}{\dots \dots \dots \dots \dots \dots}} ≺ l_{2} ≺ \underset{pre-order of l_{2} -subtree except l_{2}}{\underset{⏟}{\dots \dots \dots \dots \dots \dots}}

level-order 中，我们同样人为 augment 了 $l_{1} ≺ l_{2}$ ；但 more generally，我们限定了：

$\forall v_{k}^{(1)}, \dots v_{k}^{(2^{k - 1})} \in vertices on level k$ ，按从左至右排成 $v_{k}^{(1)} ≺ \dots ≺ v_{k}^{(2^{k - 1})}$
$\forall v_{k} on level k$ and $\forall v_{x} on level x$ , if $k < x$ , then $v_{k} ≺ v_{x}$

于是最后的结果是：

level-order := r ≺ \underset{level-order of level 2}{\underset{⏟}{l_{1} ≺ l_{2}}} ≺ \underset{level-order of level 3}{\underset{⏟}{\dots \dots \dots \dots}} ≺ \underset{level-order of level 4}{\underset{⏟}{\dots \dots \dots \dots}} ≺ \dots

X Facebook LinkedIn Bluesky

Topological Sort as a Relation (Math) / Linear Extension / DFS & BFS

0. VocabularyPermalink

1.Digression: What does “topological” mean in topological sorting?Permalink

2. Is topological sort (on DAG) a relation (math)?Permalink

2.1 DAG Reachability is a Strict Partial OrderPermalink

2.2 Digression: Visualize the reachability relation to recover the DAG (kind of)Permalink

2.3 Any FIXED Topological Sort is a Strict Total OrderPermalink

2.4 Topological Sorting is to construct a Linear Extension on DAG ReachabilityPermalink

3. How algorithms of DFS & BFS eliminate the arbitrarinessPermalink

3.1 Pre-order ( $\in$ DFS)Permalink

3.2 In-order ( $\in$ DFS)Permalink

3.3 Post-order ( $\in$ DFS)Permalink

3.4 Level-order (i.e. BFS)Permalink

分享

留下评论

猜您还喜欢

LL(1) Parsing

Top-Down Parsers: Recursive Descent, Predictive, and More

Appetizers Before Parsing: Serving Order

Appetizer #4 Before Parsing: Left Factoring

0. VocabularyPermalink

1.Digression: What does “topological” mean in topological sorting?Permalink

2. Is topological sort (on DAG) a relation (math)?Permalink

2.1 DAG Reachability is a Strict Partial OrderPermalink

2.2 Digression: Visualize the reachability relation to recover the DAG (kind of)Permalink

2.3 Any FIXED Topological Sort is a Strict Total OrderPermalink

2.4 Topological Sorting is to construct a Linear Extension on DAG ReachabilityPermalink

3. How algorithms of DFS & BFS eliminate the arbitrarinessPermalink

3.1 Pre-order (∈ DFS)Permalink

3.2 In-order (∈ DFS)Permalink

3.3 Post-order (∈ DFS)Permalink

3.4 Level-order (i.e. BFS)Permalink

分享

留下评论

猜您还喜欢

LL(1) Parsing

Top-Down Parsers: Recursive Descent, Predictive, and More

Appetizers Before Parsing: Serving Order

Appetizer #4 Before Parsing: Left Factoring

3.1 Pre-order ( $\in$ DFS)Permalink

3.2 In-order ( $\in$ DFS)Permalink

3.3 Post-order ( $\in$ DFS)Permalink