DFS如何适用于非树？

Question

我理解深度优先搜索在遍历树时的概念。但是我很难在其他数据结构（数组，二维数组等）上执行dfs。想想这个最好的方法是什么？

Answer 1

深度优先搜索（DFS）通常在树上进行演示。现在，你如何实施树木是你的呼召。您可以实现使用数组，链表，邻接矩阵，等明白最好的办法是实现一个，这里有几个实现，可以帮助：

1. DFS on an array
2. DFS and BFS using Linked List

Answer 2

的DFS将在您应用它的每个结构上创建一个虚拟树。这棵树被称为结构的spanning tree。它们存在于图形，二元图，甚至数组或DFS可访问的其他结构中。

当然会有很多的边缘，将不会在那棵树。在无向图和结构中，它们始终是“后沿”（从子节点到祖先节点），但在边界可能具有特定方向的结构中，它们可以是前向边（即指向未访问的后代节点）或交叉边（交叉不同的子树）。