题中n代表树点。我现在能想到的就只有：有向图的最大边数为n(n-1)，但我不知道如何证明出Ω(n^2)？还是说这种情况并不可能？谢谢！
通过深度优先搜索算法生成有向图的DFS树，是否有可能存在横叉边数目等于Ω(n^2)的情况？
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
分享- 邀请回答
-
2条回答 默认 最新
JonathanYan 2020-01-27 12:55关注有具体的说明吗，什么题，什么场景
如果非要到n^2，那就往里填平行边呗，某个图的dfs树种存在横叉边的话，把这些横叉边添加到n^2规模再搜索不就是你要的了。本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏举报 分享
- 2020-01-26 14:27回答 2 已采纳 有具体的说明吗，什么题，什么场景 如果非要到n^2，那就往里填平行边呗，某个图的dfs树种存在横叉边的话，把这些横叉边添加到n^2规模再搜索不就是你要的了。
- 2024-02-19 07:00闻缺陷则喜何志丹的博客 输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维...
- 2021-10-20 19:51Xunlan_的博客 ②：tarjan算法求无向图割边 前言 第一次写算法，讲得肯不透彻，有误还请指教awa 文章目录系列文章目录一、回顾二、tarjan算法 一、回顾 先来回顾一下dfs的基本框架： //存图方式：vector(g[N]) void dfs(int u){...
- 2021-12-21 18:01naturerun的博客 Tarjan算法正确性的详细证明
- 2023-04-02 23:351203_的博客 了解dfs树的边的分类以及判断方式
- 2023-01-15 01:00buqiming不起名的博客 二：Tarjan基础 ：边： 边有四类 ,以此图为例，对此树dfs： 1:树枝边：(x,y)例如(1,3) 2:前向边：(x,y)例如(1,7) PS:树枝边是特殊的前向边。 3:后向边：(x,y)例如(7,1) 4:横叉边：(x,y)例如(9,8) ：判断是都存在强...
- 2022-03-08 23:04ikrvxt的博客 （有的人叫做灭绝树） 任一有向图都存在支配树，前提是满足 s s s 能到达所有点。 支配树不一定是图 G G G 的树形图，即树上有些边不存在于图 G G G 中。 dfs \text{dfs} dfs 树。 对图 G G G 建 dfs \text{dfs} dfs...
- 2018-01-18 20:26riba2534的博客 在图论中，一个有向图被成为是强连通的（strongly connected）当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连通子图（这里指点数极大）被称为强连通分量...
- 2021-10-14 21:04Edward The Bunny的博客 有向图的 dfs树 横叉边方向唯一，总是从后访问的点指向先访问的点。 dfs树详解 tarjan 点双 定义： 不存在割点的图。 性质： 两点一线型点双，较为特殊，以下在讨论特定性质时可能不纳入考虑范围。 点双的dfs树上，...
- 2022-08-25 20:49xjsc01的博客 有向图G=(V,E)中，如果存在一个点r，使得从r出发，那么就可以到达所有的节点，那么称G为一个流图，记作(G,r)
- 2022-10-24 18:14峰不二子的小迷弟的博客 与无向图的深度优先遍历类似，我们也可以定义“流图”的搜索树和时间戳的概念：在一个流图(G, r) 上从 r 出发进行深度优先遍历，每个点只访问一次。所有发生递归的边 (x, y)（换言之，从 x 到 y 是对 y 的第一次访问...
- 2017-12-03 19:52obrcnh的博客 Tarjan算法 计算强连通分量个数
- 2018-08-16 01:37默一鸣的博客 树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。 图进行DFS会得到一棵DFS树（森林），在这个树上 才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式...
- 2022-02-04 17:53cqust_qilin02811的博客 文章目录有向图强连通分量1.定义：2.基本术语与概念2.1 边的概念2.2 缩点...给定一张有向图，若对于图中任意两个节点x，y，既存在从x到y的路径，也存在y到x的路径，则该有向图是强连通图。 有向图的极大强连通子图被称
- 2021-09-08 22:26Star星屹程序设计的博客 根据在有向图G上进行深度优先遍历所产生的深度优先森林，可以把图中的边分为四类： 树边：（Tree edge） 后向边：又称 回溯边（Back edge） 前向边：（Forward edge） 交叉边：（Cross edge） 树边，前向边，后...
- 2019-02-19 14:30蜗角虚名羊的博客 树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上 才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式也...
- 2019-05-11 16:05t11383的博客 问题描述： 给定一个有向图，要求使用深度优先搜索策略，判断图中是否存在环。 ❗算法分析❗： 判断图中是否存在环，要涉及到图的拓扑排序。回看数据结构的书
- 2014-08-23 09:38Jimmy_Fun的博客 [有向图强连通分量] 在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通...
- 2022-08-28 23:40花开终为谢的博客 深度优先遍历，二叉搜索树
- 2023-06-22 17:03chirou_的博客 这题最难想的是求出来连通分量后怎么处理，为什么最少需要将一个新软件直接提供给多少个学校，才能使软件能够通过网络被传送到所有学校的答案是入度为0的连通分量数。为什么最少需要添加几条新的支援关系，使得将一...
- 没有解决我的问题, 去提问
悬赏问题
- ¥15 基于卷积神经网络的声纹识别
- ¥15 Python中的request，如何使用ssr节点，通过代理requests网页。本人在泰国，需要用大陆ip才能玩网页游戏，合法合规。
- ¥100 为什么这个恒流源电路不能恒流？
- ¥15 有偿求跨组件数据流路径图
- ¥15 写一个方法checkPerson，入参实体类Person，出参布尔值
- ¥15 我想咨询一下路面纹理三维点云数据处理的一些问题，上传的坐标文件里是怎么对无序点进行编号的，以及xy坐标在处理的时候是进行整体模型分片处理的吗
- ¥15 CSAPPattacklab
- ¥15 一直显示正在等待HID—ISP
- ¥15 Python turtle 画图
- ¥15 stm32开发clion时遇到的编译问题