深度优先搜索 (DFS)

从图中的一个顶点开始，在回溯之前，尽可能多地访问图中的所有顶点。 图片的深度优先搜索类似于树遍历，树遍历中讨论的树的深度优先搜索。对于树来说，搜索从根开始。在图片中，搜索可以从任何顶点开始。

深度优先搜索树首先访问根，然后递归到访问根的子树。类似地，图片的深度优先搜索首先访问顶点，然后递归地访问与顶点相邻的所有顶点。不同之处在于，图片可能包含循环，这可能导致无限递归。为了避免这个问题，您需要跟踪已访问的顶点。

这个搜索被称为深度优先，因为它在图片中尽可能地搜索“更深”。从顶点搜索。 v 开始。完成访问 v 之后，它会访问 v 未访问的邻居。如果 v 如果没有未访问的邻居，搜索可以追溯到达 v 顶点。假设图片是连接的，搜索可以从任何顶点到达所有顶点。

深度优先搜索算法

在下面的代码中描述了深度优先搜索算法。

输入：g = (v, e) 和起始顶点 v 输出：一棵以 v 为根的 dfs 树 1 树 dfs（顶点 v）{ 2 访问 v； v 的每个邻居 w 为 3 个 4 if (w 尚未被访问) { 5 将 v 设置为树中 w 的父级； 6 dfs(w)； 7 } 8 }您可以使用名称

isvisited

数组表示一个顶点是否已被访问。一开始，对于每个顶点 i，isvisited[i] 对于false。一旦访问了某个顶点(例如) v），isvisited[v] 就会设置为 true. 考虑下图 (a) 中的图表。假设我们从顶点开始 0 开始深度优先搜索。首先访问 然后访问它的任何邻居，比如 1。现在访问 1，如下图 (b) 所示。顶点 1 有三个邻居：0、2 和 4。由于 0 你已经被访问过了，所以你会访问的 2 或 4。让我们选择 2。现在 2 被访问，如下图所示 (c) 所示。顶点 2 有 3 个邻居：0、1 和 3。由于 0 和 1 我被采访过，所以我选择了 3。现在访问 3，如下图 (d) 所示。到目前为止，顶点已按以下顺序被访问：

0

、1、2、3 由于 3 所有的邻居都被采访过，所以可以追溯到 2。由于 2 所有的顶点都被访问过，因此可以追溯到 1。4 与 1 相邻，但 4 还没有被访问。因此，访问4，如下图所示(e)所示。由于 4 所有的邻居都参观过，所以可以追溯到 1。

由于 1 所有的邻居都访问过，所以可以追溯到 0。由于 0 所有的邻居都访问过，所以搜索结束了。

因为每个边缘和顶点只被访问一次，所以

dfs

方法的时间复杂度为o(|e| + |v|)，其中|e|表示边数，|v | 顶点数量。 实现深度优先搜索

上述代码中的dfs算法使用递归。自然地使用递归来实现它。或者，您可以使用堆栈。

dfs(int v)

方法在 abstractgraph.java 中的第 164-193 行实现。它返回 tree 以顶点为例 v 作为根。该方法将搜索到的顶点存储在列表searchorder(第165行)中，将每个顶点的父级存储在数组parent(第166行)中，并使用isvisited数组指示一个顶点是否已被访问(第166行) 171）。它调用辅助方法 dfs(v,parent, searchorder, isvisited) 执行深度优先搜索(第) 174 行）。 在递归辅助方法中，从顶点搜索

u

开始。 u 在第 184 行添加到 searchorder 并标记为已访问(第一) 185 行)。对于u未访问的每个邻居，递归调用此方法进行深度优先搜索。当访问顶点e时.v时，e.parenttt存储在v的父顶点[e.v]中间(第189行)。当访问连通图或连通组件中的所有顶点时，该方法将返回。

下面的代码给出了一个从芝加哥开始的测试程序 dfs。从芝加哥出发的dfs示意图如下图所示

public class TestDFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<string> graph = new UnweightedGraph(vertices, edges);
        AbstractGraph<string>.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS order:");
        for(int i = 0; i 



<br>在此 dfs 顺序中搜索 12 个顶点：
 芝加哥 西雅图 旧金山 洛杉矶 丹佛<p>
 堪萨斯城 纽约 波士顿 亚特兰大 迈阿密 休斯顿 达拉斯<br>
芝加哥的父母是芝加哥<br>
西雅图是旧金山的父母<br>
洛杉矶的父母是旧金山<br>
洛杉矶是丹佛的父母<br>
丹佛是堪萨斯城的父母<br>
波士顿的父母是纽约<br>
纽约的父母是堪萨斯城<br>
亚特兰大的父母是纽约<br>
亚特兰大是迈阿密的父母<br>
休斯顿是休斯顿的父母<br>
迈阿密是迈阿密的父母<br><br></p>
<p>

<img src="https://img.php.cn/upload/article/000/000/164/172325881386227.png" alt="深度优先搜索 (DFS)">
  
  
  dfs的应用
</p>

<h2>深度优先搜索可以用来解决许多问题，例如：</h2>

<p>
</p>检测图是否连接。搜索图片从任何顶点开始。从任何顶点开始搜索图。如果搜索到的顶点数与图中的顶点数相同，则图是连接的。否则，图形不会连接。<ul>
<li>检查两个顶点之间是否有路径。</li>
<li>在两个顶点之间寻找路径。</li>
<li>找到所有连接的组件。连接分量是最大的连接子图，每对顶点都通过路径连接。</li>
<li>检测图中是否存在环路。</li>
<li>在图中找到一个循环。</li>
<li>找到哈密顿路径/循环。图中的</li>哈密尔顿路径<li>只访问图中每个顶点一次的路径。 <em>哈密尔顿循环</em> 只访问图中的每个顶点一次，然后返回到起始顶点。<em>
</em>

</li>abstractgraph可用于前六个问题.java中的dfs方法很容易解决。要找到哈密顿路径/循环，你必须探索所有可能的东西 dfs，找到通向最长路径的路径。哈密顿路径/循环有很多应用，包括解决著名骑士之旅的问题。</ul>
<p>

            
        </p></integer></string></string>

以上是深度优先搜索 (DFS)详情请关注图灵教育的其他相关文章！