图-深度优先(DFS)

约束

此处讨论无向、无重复边、无自环、无权重的联通图。

图-深度优先搜索(DFS)

在图中尽可能 “深入”。

概念: 优先搜索总是对最近发现结点v的出发边进行探索，直到该结点的所有出发边都被发现为止。

深度优先搜索的前驱子图形成的可能是多棵树(森林)。

算法伪码

ADD-SET(e): 将元素 e 加入不重复元素集合中。
PUSH(S, e): 把元素 e 压入栈 S。
POP(S): 出栈，弹出栈顶元素。

Depth-first search

#1     S={} //Empty
#2     PUSH(S, e)
#3     ADD-SET(e)
#4     while S is not empty
#5         u = POP(S)
#6         for each vertex(v) in G.Adj[u] //遍历 u 的孩子节点
#7             if v in FIND-SET(v)
#8                 continue; //已发现
#9             else 
#10                PUSH(S, v)
#11                ADD-SET(v)
#12        print u

举例

比如，有图Graph=G(V, E)如下：

其邻接链表(Adjacency List) 表示为：

A -- B -- C
B -- A -- C
C -- A -- B -- D -- E
D -- C -- F -- G
E -- C
F -- D -- G

领接矩阵(Adjacency Matrix) 表示为：

-	A	B	C	D	E	F	G
A	-	1	1	-	-	-	-
B	1	-	1	-	-	-	-
C	1	1	-	1	1	-	-
D	-	-	1	-	-	1	1
E	-	-	1	-	-	-	-
F	-	-	-	1	-	-	1
G	-	-	-	1	-	1	-

算法流程：

以 A 为源点。初始化时(#1 ~ #3)，将节点 A 压入栈(#2 执行后)，加入不重复元素集合(#3 执行后)。

此时栈是：S{A}，不重复元素集合是： SET{A}。

while 循环次数	栈顶(#5执行前)	出栈后(#5执行后)	入栈(#6 ~ #11 执行后)	不重复元素集合(#6 ~ #11 执行后)
1	A	S{}	S{C, B}	SET{A, B, C}
2	C	S{B}	S{E, D, B}	SET{A, B, C, D, E}
3	E	S{D, B}	S{D, B}	SET{A, B, C, D, E}
4	D	S{B}	S{G, F, B}	SET{A, B, C, D, E, F, G}
5	G	S{F, B}	S{F, B}	SET{A, B, C, D, E, F, G}
6	F	S{B}	S{B}	SET{A, B, C, D, E, F, G}
7	B	S{}	S{}	SET{A, B, C, D, E, F, G}

注：入栈的顺序影响了后续出栈的顺序。算法伪码中具有相同深度孩子节点的入栈(#10) 会影响到后续的出栈(#5)。 不同节点入栈顺序(#10) 会影响出栈顺序(#5)。

此例中，构造出的树如下所示：

L0 -----  A  -------- L0
         / \
L1 ---  B   C  ------ L1
           / \
L2 -----  D   E  ---- L2
         / \
L3 ---  F   G  ------ L3

其深度度优先遍历的顺序是，A -> C -> E -> D -> G -> F -> B，也可是 A -> B -> C -> E -> D -> F -> G, A -> B -> C -> D -> F -> G -> E 等其他符合“深度优先”的顺序。

要点

• 从源点出发，按照 “深度” 先发现距离源点深度为 1 的节点 v ，再发现距离节点 v 深度为 1 的节点 u，直到u不能发现为止，如此反复遍历所有节点。
• 重要定理：广度优先搜索计算出来的即是最短路径。

其它

• 与广度优先搜索原理类似，此处采用了 “栈” 的 “先进后出” 特性来完成 “深度” 的遍历。

参考

[1] Thomars H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms.