3.「图」的深度优先搜索算法

在前面的「并查集」数据结构中，大家已经知道如何检查两个顶点之间的连通性。那如果给你一个「图」，你该如何找出它所有的顶点呢？以及你又如何找出它两个顶点之间的所有路径呢？此时，「深度优先搜索」算法就可以登场了。如「图6. 无向图」所示，它的所有顶点分别为[A, C, D, B, E]。给定顶点 A 和 B， 它们之间有两条路径，一条路径为[A, C, D, B]，另一条路径为[A, E, B]。

「深度优先搜索」（又称「Depth First Search」，简称「DFS」）算法在「图」中主要用途：

• 遍历「图」中所有顶点；
• 遍历「图」中任意两点之间的所有路径。