”工欲善其事,必先利其器。“—孔子《论语.录灵公》
首页 > 编程 > 深度优先搜索 (DFS)

深度优先搜索 (DFS)

发布于2024-08-19
浏览:449

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

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

该搜索被称为深度优先,因为它尽可能在图中搜索“更深”。搜索从某个顶点 v 开始。访问完 v 后,它会访问 v 的未访问的邻居。如果 v 没有未访问的邻居,则搜索回溯到到达 v 的顶点。我们假设图是连通的,并且搜索开始从任意顶点出发都可以到达所有顶点。

深度优先搜索算法

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

输入:G = (V, E) 和起始顶点 v
输出:以 v
为根的 DFS 树 1 树 dfs(顶点 v) {
2 访问 v;
3 对于 v
的每个邻居 w 4 if (w尚未被访问过) {
5 将 v 设置为树中 w 的父级;
6 dfs(w);
7 }
8 }

可以使用名为isVisited的数组来表示某个顶点是否已被访问。最初,对于每个顶点 i,isVisited[i]false。一旦访问了某个顶点(例如 v),isVisited[v] 就会设置为 true

考虑下图 (a) 中的图表。假设我们从顶点 0 开始深度优先搜索。首先访问 0,然后访问它的任何邻居,比如 1。现在访问 1,如下图 (b) 所示。顶点 1 有 3 个邻居:0、2 和 4。由于 0 已经被访问过,因此您将访问 2 或 4。让我们选择 2。现在 2 被访问,如下图 (c) 所示。顶点 2 有 3 个邻居:0、1 和 3。由于 0 和 1 已经被访问过,所以选择 3。现在访问 3,如下图 (d) 所示。至此,顶点已按以下顺序被访问过:

0123

由于3的所有邻居都被访问过,所以回溯到2。由于2的所有顶点都被访问过,所以回溯到1。4与1相邻,但4还没有被访问过。因此,访问4,如下图(e)所示。由于 4 的所有邻居都已访问过,因此回溯到 1。
由于1的所有邻居都被访问过,所以回溯到0。因为0的所有邻居都被访问过,所以搜索结束。

Depth-First Search (DFS)

由于每条边和每个顶点仅被访问一次,因此dfs方法的时间复杂度为O(|E| |V|),其中|E | 表示边数,|V| 表示顶点数。

深度优先搜索的实现

上面代码中的DFS算法使用了递归。很自然地使用递归来实现它。或者,您可以使用堆栈。

dfs(int v)方法在AbstractGraph.java的第164-193行实现。它返回 Tree 类的实例,以顶点 v 作为根。该方法将搜索到的顶点存储在列表 searchOrder(第 165 行)中,每个顶点的父级存储在数组 parent(第 166 行)中,并使用 isVisited 数组来指示是否已访问顶点(第 171 行)。它调用辅助方法 dfs(v, Parent, searchOrder, isVisited) 执行深度优先搜索(第 174 行)。

在递归辅助方法中,搜索从顶点u开始。 u 被添加到第 184 行的 searchOrder 中,并被标记为已访问(第 185 行)。对于 u 的每个未访问的邻居,递归调用该方法来执行深度优先搜索。当访问顶点 e.v 时,e.v 的父顶点存储在 parent[e.v] 中(第 189 行)。当访问连通图或连通组件中的所有顶点时,该方法返回。

Depth-First Search (DFS)

下面的代码给出了一个测试程序,该程序显示上图中从芝加哥开始的图形的 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 graph = new UnweightedGraph(vertices, edges);
        AbstractGraph.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

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



按此 DFS 顺序搜索 12 个顶点:
芝加哥 西雅图 旧金山 洛杉矶 丹佛
堪萨斯城 纽约 波士顿 亚特兰大 迈阿密 休斯敦 达拉斯
西雅图的父级是芝加哥
旧金山的父级是西雅图
洛杉矶的父级是旧金山
丹佛的父级是洛杉矶
堪萨斯城的母公司是丹佛
波士顿的父级是纽约
纽约的父级是堪萨斯城
亚特兰大的父级是纽约
迈阿密的父级是亚特兰大
达拉斯的父母是休斯顿
休斯顿的父母是迈阿密

Depth-First Search (DFS)

DFS的应用

深度优先搜索可以用来解决很多问题,例如:

  • 检测图是否连通。从任意顶点开始搜索图。如果搜索到的顶点数与图中的顶点数相同,则该图是连通的。否则,图形不连通。
  • 检测两个顶点之间是否存在路径。
  • 寻找两个顶点之间的路径。
  • 查找所有连接的组件。连通分量是最大连通子图,其中每对顶点都通过路径连接。
  • 检测图中是否存在环路。
  • 在图中找到一个循环。
  • 寻找哈密顿路径/循环。图中的哈密顿路径是只访问图中每个顶点一次的路径。 哈密尔顿循环访问图中的每个顶点一次并返回到起始顶点。

前六个问题可以使用AbstractGraph.java中的dfs方法轻松解决。要找到哈密顿路径/循环,您必须探索所有可能的 DFS,以找到通向最长路径的路径。哈密​​顿路径/循环有很多应用,包括解决著名的骑士之旅问题。

版本声明 本文转载于:https://dev.to/paulike/depth-first-search-dfs-4gid?1如有侵犯,请联系[email protected]删除
最新教程 更多>
  • 为什么我在Silverlight Linq查询中获得“无法找到查询模式的实现”错误?
    为什么我在Silverlight Linq查询中获得“无法找到查询模式的实现”错误?
    查询模式实现缺失:解决“无法找到”错误在Silverlight应用程序中,尝试使用LINQ建立LINQ连接以错误而实现的数据库”,无法找到查询模式的实现。”当省略LINQ名称空间或查询类型缺少IEnumerable 实现时,通常会发生此错误。 解决问题来验证该类型的质量是至关重要的。在此特定实例中...
    编程 发布于2025-06-11
  • Go语言垃圾回收如何处理切片内存?
    Go语言垃圾回收如何处理切片内存?
    在Go Slices中的垃圾收集:详细的分析在GO中,Slice是一个动态数组,引用了基础阵列。使用切片时,了解垃圾收集行为至关重要,以避免潜在的内存泄漏。考虑使用slice使用slice的以下实现:字符串{ R:=(*Q)[0] *q =(*q)[1:len(*q)] 返回...
    编程 发布于2025-06-11
  • Async Void vs. Async Task在ASP.NET中:为什么Async Void方法有时会抛出异常?
    Async Void vs. Async Task在ASP.NET中:为什么Async Void方法有时会抛出异常?
    在ASP.NET async void void async void void void void void的设计无需返回asynchroncon而无需返回任务对象。他们在执行过程中增加未偿还操作的计数,并在完成后减少。在某些情况下,这种行为可能是有益的,例如未期望或明确预期操作结果的火灾和...
    编程 发布于2025-06-11
  • 如何从Python中的字符串中删除表情符号:固定常见错误的初学者指南?
    如何从Python中的字符串中删除表情符号:固定常见错误的初学者指南?
    从python import codecs import codecs import codecs 导入 text = codecs.decode('这狗\ u0001f602'.encode('utf-8'),'utf-8') 印刷(文字)#带有...
    编程 发布于2025-06-11
  • MySQL中如何高效地根据两个条件INSERT或UPDATE行?
    MySQL中如何高效地根据两个条件INSERT或UPDATE行?
    在两个条件下插入或更新或更新 solution:的答案在于mysql的插入中...在重复键更新语法上。如果不存在匹配行或更新现有行,则此功能强大的功能可以通过插入新行来进行有效的数据操作。如果违反了唯一的密钥约束。实现所需的行为,该表必须具有唯一的键定义(在这种情况下为'名称'...
    编程 发布于2025-06-11
  • 在细胞编辑后,如何维护自定义的JTable细胞渲染?
    在细胞编辑后,如何维护自定义的JTable细胞渲染?
    在JTable中维护jtable单元格渲染后,在JTable中,在JTable中实现自定义单元格渲染和编辑功能可以增强用户体验。但是,至关重要的是要确保即使在编辑操作后也保留所需的格式。在设置用于格式化“价格”列的“价格”列,用户遇到的数字格式丢失的“价格”列的“价格”之后,问题在设置自定义单元格...
    编程 发布于2025-06-11
  • 如何使用FormData()处理多个文件上传?
    如何使用FormData()处理多个文件上传?
    )处理多个文件输入时,通常需要处理多个文件上传时,通常是必要的。 The fd.append("fileToUpload[]", files[x]); method can be used for this purpose, allowing you to send multi...
    编程 发布于2025-06-11
  • 哪种方法更有效地用于点 - 填点检测:射线跟踪或matplotlib \的路径contains_points?
    哪种方法更有效地用于点 - 填点检测:射线跟踪或matplotlib \的路径contains_points?
    在Python Matplotlib's path.contains_points FunctionMatplotlib's path.contains_points function employs a path object to represent the polygon.它...
    编程 发布于2025-06-11
  • 如何同步迭代并从PHP中的两个等级阵列打印值?
    如何同步迭代并从PHP中的两个等级阵列打印值?
    同步的迭代和打印值来自相同大小的两个数组使用两个数组相等大小的selectbox时,一个包含country代码的数组,另一个包含乡村代码,另一个包含其相应名称的数组,可能会因不当提供了exply for for for the uncore for the forsion for for ytry...
    编程 发布于2025-06-11
  • Go web应用何时关闭数据库连接?
    Go web应用何时关闭数据库连接?
    在GO Web Applications中管理数据库连接很少,考虑以下简化的web应用程序代码:出现的问题:何时应在DB连接上调用Close()方法?,该特定方案将自动关闭程序时,该程序将在EXITS EXITS EXITS出现时自动关闭。但是,其他考虑因素可能保证手动处理。选项1:隐式关闭终止数...
    编程 发布于2025-06-11
  • 如何在php中使用卷发发送原始帖子请求?
    如何在php中使用卷发发送原始帖子请求?
    如何使用php 创建请求来发送原始帖子请求,开始使用curl_init()开始初始化curl session。然后,配置以下选项: curlopt_url:请求 [要发送的原始数据指定内容类型,为原始的帖子请求指定身体的内容类型很重要。在这种情况下,它是文本/平原。要执行此操作,请使用包含以下标头...
    编程 发布于2025-06-11
  • 编译器报错“usr/bin/ld: cannot find -l”解决方法
    编译器报错“usr/bin/ld: cannot find -l”解决方法
    错误:“ usr/bin/ld:找不到-l “ 此错误表明链接器在链接您的可执行文件时无法找到指定的库。为了解决此问题,我们将深入研究如何指定库路径并将链接引导到正确位置的详细信息。添加库搜索路径的一个可能的原因是,此错误是您的makefile中缺少库搜索路径。要解决它,您可以在链接器命令中添加...
    编程 发布于2025-06-11
  • \“(1)vs.(;;):编译器优化是否消除了性能差异?\”
    \“(1)vs.(;;):编译器优化是否消除了性能差异?\”
    答案: 在大多数现代编译器中,while(1)和(1)和(;;)之间没有性能差异。编译器: perl: 1 输入 - > 2 2 NextState(Main 2 -E:1)V-> 3 9 Leaveloop VK/2-> A 3 toterloop(next-> 8 last-> 9 ...
    编程 发布于2025-06-11
  • 在Ubuntu/linux上安装mysql-python时,如何修复\“ mysql_config \”错误?
    在Ubuntu/linux上安装mysql-python时,如何修复\“ mysql_config \”错误?
    mysql-python安装错误:“ mysql_config找不到”“ 由于缺少MySQL开发库而出现此错误。解决此问题,建议在Ubuntu上使用该分发的存储库。使用以下命令安装Python-MysqldB: sudo apt-get安装python-mysqldb sudo pip in...
    编程 发布于2025-06-11
  • 人脸检测失败原因及解决方案:Error -215
    人脸检测失败原因及解决方案:Error -215
    错误处理:解决“ error:((-215)!empty()in Function Multultiscale中的“ openCV 要解决此问题,必须确保提供给HAAR CASCADE XML文件的路径有效。在提供的代码片段中,级联分类器装有硬编码路径,这可能对您的系统不准确。相反,OPENCV提...
    编程 发布于2025-06-11

免责声明: 提供的所有资源部分来自互联网,如果有侵犯您的版权或其他权益,请说明详细缘由并提供版权或权益证明然后发到邮箱:[email protected] 我们会第一时间内为您处理。

Copyright© 2022 湘ICP备2022001581号-3