图的深度优先搜索算法并生成DFS树 - CSDN博客

前面一篇文章介绍了图的广度优先搜索算法和BFS树，这篇文件笔者将介绍另一种图的遍历算法-深度优先算法概述深度优先搜索（Depth-First Search，DFS） ... 图的深度优先搜索算法并生成DFS树 不能说的秘密go 2017-12-0400:59:53 17055 收藏 9 分类专栏： 我的数据结构之旅 版权声明：本文为博主原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/canot/article/details/78705704 版权 我的数据结构之旅 专栏收录该内容 18篇文章 1订阅 订阅专栏 前面一篇文章介绍了图的广度优先搜索算法和BFS树，这篇文件笔者将介绍另一种图的遍历算法-深度优先算法 概述 深度优先搜索（Depth-FirstSearch，DFS）选取下一顶点的策略，可概括为：优先选取最后一个被访问到的顶点的邻居。

以顶点s为基点的DFS搜索，将首先访问顶点s；再从s所有尚未访问到的邻居中任取其一，并以之为基点，递归地执行DFS搜索。

故各顶点被访问到的次序，类似于树的先序遍历而各顶点被访问完毕的次序，则类似于树的后序遍历 图的深度优先搜索的代码实现 首先来看看再遍历算法中节点和弧使用到的属性： 节点 privateintstatus=0;//状态0undiscovered"未发现"1discovered"已发现"2visited"已完成" privateintparent=-1; privateintdTime=-1;//开始遍历的时间 privateintfTime=-1;//结束遍历的时间 弧 privateinttype; //弧类型：0CROSS跨边1TREE（支撑树） //2BACKWARD(该弧的起点和终点在支撑树中存在终点到起点的路径) //3FORWARD(该弧的起点和终点在支撑树中存在其他路径依然可以从起点到终点) 遍历算法 //从节点index开始遍历 publicvoiddfsTree(intindex){ this.reload();//复位所有节点和弧状态 //用来记录某个节点被遍历的时间 Integerclock=newInteger(0); ints=index; do{ if(allNodes[s].getStatus()==0){ dfs(s,clock); } }while(index!=(s=(++s%size)));//按序号检查，防止遗漏index无法连通的节点 } publicvoiddfs(intindex,Integerclock){ //发现该节点 allNodes[index].setStatus(1); //记录开始访问的时间 allNodes[index].setdTime(++clock); //找出节点index的所有邻居 for(inti=0;iparent->parent...==index case1: edge.setType(2); break; //如果该节点已经被访问完毕。

则根据其遍历结束时间来区分 case2: inttype=allNodes[index].getdTime()>allNodes[i].getdTime()?0:3; edge.setType(type); break; } } } //index节点访问完毕 allNodes[index].setStatus(2); allNodes[index].setfTime(++clock); } 算法的实质功能，由子算法dfs（）递归地完成。

每一递归实例中，都先将当前节点v标记为“已发现”状态，再逐一核对其各邻居u的状态并做相应处理。

待其所有邻居均已处理完毕之后，将顶点v置为“访问完毕”状态，便可递归回溯。

若项点u尚处于“未发现”状态，则将边（v,u）归类为树边，并将v置为u的parent。

此后，便可将u作为当前顶点，继续递归地遍历。

若项点u处于“已发现”状态，则意味着在此处发现一个有向环路。

此时，在DFS遍历树中u必为v的祖先，故应将边（v,u）归类为后向边BACKWARD。

这里为每个顶点v都记录了被发现的和访问完成的时刻，对应的时间区间【dTime(v),fTime(v）】均称作v的活跃期（activeduration）。

实际上，任意顶点v和u之间是否存在祖先/后代的“血缘”关系，完全取决于二者的活跃期是否相互包含。

对于有向图，顶点u还可能处于“已发现”状态。

此时，只要比对v与u的活跃期，即可判定在DFS树中v是否为u的祖先。

若是，则边（v,u）应归类为前向边FORWARD（forwardedge）；否则，二者必然来自相互独立的两个分支，边（v,u）应归类为跨边（crossedge）。

如果v的dTime()小则为前向边，否则为跨边 bfs(s）返回后，所有访问过的顶点通过parent指针依次联接，从整体上给出了顶点s所属连通或可达分量的一棵遍历树，称作深度优先搜索树或DFS树（DFStree）。

与BFS搜索一样，此时若还有其它的连通或可达分量，则可以其中任何顶点为基点，再次启动DFS搜索，来构成了DFS森林（DFSforest）。

实例 下图针对含7个顶点和18条边的某有向图，给出了DFS搜索的详细过程。

注意观察顶点时间标签的设置，顶点状态的演变，边的分类和结果，以及DFS树（森林）的生长过程： 粗边框白色，为当前顶点；细边框白色、双边框白色和黑色，分别为处于未发现、已发现和已完成状态的顶点；dTime和fTime标签，分别标注与各顶点的左右 最终结果如图t所示，为包含两棵DFS树的一个DFS森林。

可以看出，选用不同的起始基点，生成的DFS树（森林）也可能各异。

如本例中，若从D开始搜索，则DFS森林可能如图u所示。

复杂度 除了原图本身，深度优先搜索算法所使用的空间，主要消耗于各顶点的时间标签和状态标记，以及各边的分类标记，二者累计不超过0(n)+O(e)=O(n+e）。

当然，如采用以上代码的直接递归实现方式，操作系统为维护运行栈还需耗费一定量的空间一尽管这部分增量在渐进意义下还不足以动摇以上结论。

时间方面，不计对子函数dfs（）的调用，dfsTree（）本身对所有顶点的枚举共需0(n）时间。

不计dfs（）之间相互的递归调用，每个顶点、每条边只在子函数dfs（）的某一递归实例中耗费O(1）时间，故累计亦不过0(n+e）时间。

综合而言，深度优先搜索算法也可在O(n+e）时间内完成。

不能说的秘密go 关注 关注 7 点赞 踩 3 评论 9 收藏 一键三连 扫一扫，分享海报 专栏目录 图的深度优先搜索算法 11-06 图的深度优先搜索算法图的深度优先搜索算法图的深度优先搜索算法 DFS树 malanlllll的的的的的博客 03-27 3876 翻译自THeDFStreeanditsapplications:howIfoundoutIreallydidn’tunderstandbridges 介绍 这是一篇对可以用图的DFS树来解的题的教程/扩展。

在很长一段时间，我并没有真正理解传统算法是如何找到桥的。

很多题解看起来没有真正解释它是如何工作的，很多只是顺带提到它但后迅速地进入实现部分。

某一天有人解释了... 评论3 请先登录后发表评论~ 插入表情 代码片 HTML/XML objective-c Ruby PHP C C++ JavaScript Python Java CSS SQL 其它 树与图的深度优先遍历，树的DFS序、深度和重心 小康的博客 09-06 1309 深度优先遍历：时间复杂度为O(n+m) voiddfs(intx){ v[x]=1;//记录点x已被访问过 for(inti=head[x];i;i=next[i]){ inty=ver[i]; if(v[y])continue;//点y已经被访问过了 dfs(y); } } ... 图论（五）深度优先搜索DFS saltriver的专栏 01-14 1万+ 深度优先搜索(DFS,DepthFirstSearch)是一个针对图和树的遍历算法。

早在19世纪就被用于解决迷宫问题。

对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。

DFS的实现方式相比于BFS应该说大同小异，只是把queue换成了stack而已，stack具有后进先出LIFO(LastInput 图的常用程序（构造，DFS,BFS,及其生成树） 12-03 自己写的，还很粗糙，希望大家多指点一下！ 深度优先生成树和广度优先生成树 数据结构入门教程 04-15 2万+ 本章的第一节中，介绍了有关生成树和生成森林的有关知识，本节来解决对于给定的无向图，如何构建它们相对应的生成树或者生成森林。

其实在对无向图进行遍历的时候，遍历过程中所经历过的图中的顶点和边的组合，就是图的生成树或者生成森林。

图1无向图 ... 图|深度优先生成树和广度优先生成树 挖坑埋你 11-07 3万+ 本章的第一节中，介绍了有关生成树和生成森林的有关知识，本节来解决对于给定的无向图，如何构建它们相对应的生成树或者生成森林。

其实在对无向图进行遍历的时候，遍历过程中所经历过的图中的顶点和边的组合，就是图的生成树或者生成森林。

图1无向图 例如，图1中的无向图是由V1～V7的顶点和编号分别为a～i的边组成。

当使用深度优先搜索算法时，假设V1作为遍历的起始点，涉及到的顶点和... 数据结构和算法总结（一）：广度优先搜索BFS和深度优先搜索DFS weixin_30617695的博客 09-20 1304 前言 这几天复习图论算法，觉得BFS和DFS挺重要的，而且应用比较多，故记录一下。

广度优先搜索 有一个有向图如图a 图a 广度优先搜索的策略是： 从起始点开始遍历其邻接的节点，由此向外不断扩散。

1.假设我们以顶点0为原点进行搜索，首先确定邻接0的顶点集合S0... 深度优先搜索——树 qq_39457296的博客 05-04 526 98.验证二叉搜索树 //递归版本 classSolution{ public: TreeNode*pre; boolisValidBST(TreeNode*root){ if(root){ if(!isValidBST(root->left)){ returnfalse; ... 图、图的遍历、DFS生成树、BFS生成树 KinboSong的博客 04-02 1万+ 图分为：无向图和有向图 图的遍历：深度优先遍历（Depth-FirstSearch，DFS）和广度优先遍历（Breadth-FirstSearch，BFS）。

深度优先遍历和广度优先遍历参考博客：https://segmentfault.com/a/1190000002685939 图的深度优先和广度优先搜索算法 火雨(Nick) 03-13 5124 图的深度优先和广度优先搜索算法   1.图的深度优先搜索算法：     图的深度优先搜索算法的基本思想是：从图G的某个顶点V0出发,访问V0,然后选择一个与V0相邻且未被访问过的顶点Vi访问,再从Vi出发选择一个与Vi相邻且未被访问的顶点Vj进行访问,依此下去,直到当前被访问过的顶点的所有邻接顶点都已被访问,则按相反顺序退回到已访问的顶点序列中,如果其中的顶点还存在未被访 图的遍历（深度优先搜索） 热门推荐 Unique-You的博客 10-19 9万+ 1、深度优先搜索遍历过程 图的深度优先搜索(DepthFirstSearch)，和树的先序遍历比较类似。

它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。

若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有 八数码深度优先搜索_树的深度优先搜索(上) weixin_39827775的博客 12-04 471 还记得我们说迭代法的具体应用中的二分法吗？我们讨论了一个查字典的例子。

如果要使用二分查找，我们首先要把整个字典排个序，然后每次都通过二分的方法来缩小搜索范围。

不过在平时的生活中，咱们查字典并不是这么做的。

我们都是从单词的最左边的字母开始，逐个去查找。

比如查找“boy”这个单词，我们一般是这么查的。

首先，在a～z这26个英文字母里找到单词的第一个字母b，然后在b开头的单词里找... 深度优先搜索、广度优先搜索及其生成树 05-31 深度优先搜索、广度优先搜索及其生成树.txt深度优先搜索、广度优先搜索及其生成树.txt深度优先搜索、广度优先搜索及其生成树.txt深度优先搜索、广度优先搜索及其生成树.txt 深度优先搜索树（通过数组以后序遍历以及中序遍历创建树） Hanzoe的博客 11-13 87 题目 通过中序遍历和后序遍历创建树，同时找到到根的路径权和最小的叶子。

输入： 3214576 3125674 输出 1 解答 #include #include #include #include #include usingnamespacestd; constintmaxv=10000+10; ve 总结深度优先与广度优先的区别 baizhaokui5595的博客 04-30 1056 1、区别 1）二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

2）深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。

要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。

具体说明如下： 先序遍历：对任一子树，先访问根，然后遍历其左子树，最... 回顾深度优先生成树 最新发布 calm_encode的博客 12-09 3703 一概述 在深度遍历的过程中，我们可以得到一棵遍历树，称为深度优先生成树(生成森林)。

二深度优先生成树(生成森林)实例分析 如图： 我们从顶点A出发访问该图； 我们按深度优先搜索算法继续访问了顶点C，D，E。

然后访问顶点B，得到的深度优先生成森林如图： 注：邻接矩阵法的深度优先生成树唯一，邻接表法的不唯一。

因为邻接表法在生成边表时，根据输入顺序的不同，它生成的边表也会不同。

所以邻接表法的深度优先生成树不唯一，同理于广度优先生成树。

... DFS深度优先搜索树算法 weixin_45044448的博客 12-20 386 深度优先搜索树算法 上课学习到的算法就在这里写一下 算法的思路其实就是在一个图中，从某个结点出发，一直沿着出度结点出发，再从该出度结点出发，直到没有出度或结点被访问过，递归调用。

中间加计时器记录结点的发现时间和完成时间。

图是有向图或者无向图其实没什么影响。

我用java来实现这个算法 先定义一个类，用作结点的表示 classv{ Stringv_name=""; intv... 深度优先遍历生成树，并对生成树进行层序遍历，输出得到的序列(c数据结构) 06-19 深度优先遍历生成树，并对生成树进行层序遍历，输出得到的序列（数据结构C语言版） 树与图的深度优先遍历 qq_22121229的博客 06-19 667 树与图的深度优先遍历 树与图的存储 树是一种没有闭环的无向图，无向图是一种特殊的有向图。

因此我们只要表示出有向图就可以了。

有向图的表示有两种，分别是邻接图和邻接表。

用的比较多的是邻接表。

邻接表的结构就是一个数组拉一个链表和之前谈到的哈希表解决冲突的链表法一样。

例题 给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。

请你找到树的重心... ©️2021CSDN 皮肤主题:编程工作室 设计师:CSDN官方博客 返回首页 不能说的秘密go CSDN认证博客专家 CSDN认证企业博客 码龄7年 暂无认证 189 原创 1万+ 周排名 148万+ 总排名 159万+ 访问 等级 1万+ 积分 544 粉丝 526 获赞 255 评论 1074 收藏 私信 关注 热门文章 CPUload过高产生的原因及排查 49633 Swagger使用文档 48537 MyBatis嵌套查询解析 41773 Redis持久化存储(AOF与RDB两种模式) 41443 理解JPA注解@GeneratedValue 39714 分类专栏 中间件 1篇 异步处理框架 4篇 java并发编程 15篇 JavaEE流行框架 36篇 JavaNIO与Netty网络编程学习笔记 7篇 JDK集合源码剖析 6篇 java基础 56篇 Android开发 22篇 javaWeb基础 14篇 设计模式 5篇 linux 7篇 JavaEE流行框架 41篇 网络编程 7篇 NoSQL 17篇 数据库 8篇 并发编程 19篇 javaScript 4篇 项目管理工具 2篇 JVM 9篇 TCP-IP 1篇 javaNIO 5篇 缓存 11篇 webservice 1篇 docker 4篇 分布式 5篇 MQ 4篇 JMS 2篇 我的数据结构之旅 18篇 Redis 10篇 MongoDB 5篇 Swagger 2篇 RESTful 1篇 契约测试 1篇 微服务 1篇 java8新特性 1篇 RPC 1篇 NodeJs 4篇 操作系统 2篇 二叉树 7篇 图 2篇 搜索树 6篇 分布式锁 2篇 最新评论 JavaNIO学习笔记(三)使用Selector客户端与服务器的通信 让时间来证明一切: 写事件能解释下吗 Spring与Hibernate整合时的核心类LocalSessionFactoryBean详解 norang: 写的好呀，没想到这个接口，还能有这个用处。

图的深度优先搜索算法并生成DFS树 m0_64472455: 很详细 编写一键安装伪分布式Hadoop的脚本 weixin_53591808: 赞 伸展树的特性及实现 qq_52143141: 清华教材上的图 您愿意向朋友推荐“博客详情页”吗？ 强烈不推荐 不推荐 一般般 推荐 强烈推荐 提交 最新文章 Mysql(InnoDB)的SQL加锁分析 Mysql调优记：INNERJOIN查询Usingtemporary;Usingfilesort问题优化 Java为什么要将String设置为不可变对象？ 2020年2篇 2019年10篇 2018年13篇 2017年35篇 2016年129篇 2015年14篇 目录 目录 分类专栏 中间件 1篇 异步处理框架 4篇 java并发编程 15篇 JavaEE流行框架 36篇 JavaNIO与Netty网络编程学习笔记 7篇 JDK集合源码剖析 6篇 java基础 56篇 Android开发 22篇 javaWeb基础 14篇 设计模式 5篇 linux 7篇 JavaEE流行框架 41篇 网络编程 7篇 NoSQL 17篇 数据库 8篇 并发编程 19篇 javaScript 4篇 项目管理工具 2篇 JVM 9篇 TCP-IP 1篇 javaNIO 5篇 缓存 11篇 webservice 1篇 docker 4篇 分布式 5篇 MQ 4篇 JMS 2篇 我的数据结构之旅 18篇 Redis 10篇 MongoDB 5篇 Swagger 2篇 RESTful 1篇 契约测试 1篇 微服务 1篇 java8新特性 1篇 RPC 1篇 NodeJs 4篇 操作系统 2篇 二叉树 7篇 图 2篇 搜索树 6篇 分布式锁 2篇 实付元 使用余额支付 点击重新获取 扫码支付 钱包余额 0 抵扣说明： 1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。

2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。

余额充值