程序员经验分享-hwhale

BFS遍历树和DFS遍历树

2023-11-20

遍历树

按照遍历的顺序（如不清楚图的遍历，请先阅读图的遍历）,绘制成树型结构

DFS遍历树

以下为图到遍历树的转化(如果不清楚图的遍历,请先阅读笔者的另一篇文章:图的遍历(动图)),按照DFS遍历的顺序,绘制成一棵树,途中红色的边就是遍历过程中没有经过的边(在遍历树上,红色的边其实是不存在的,只是为了和图做比对和便于后面的分析,笔者在遍历树上绘制出来了)
图转化为DFS遍历树
从遍历树中可以看出,非遍历的边可以指向自己的祖先节点(即后向边),而查找桥的算法恰恰就是使用了后向边的性质,而在BFS遍历树中并不存在该性质,所以查找桥只可以用DFS遍历

  • 后向边:不在遍历树上的边
  • 前向边:在遍历树上的边

BFS遍历树

以下为图到遍历树的转化(如果不清楚图的遍历,请先阅读笔者的另一篇文章:图的遍历(动图)),按照BFS遍历的顺序,绘制成一棵树,途中红色的边就是遍历过程中没有经过的边(在遍历树上,红色的边其实是不存在的,只是为了和图做比对和便于后面的分析,笔者在遍历树上绘制出来了)
图转化为BFS遍历树
从遍历树中可以看出,非遍历的边是无法指向自己的祖先节点(即BFS遍历树不存在后向边),而查找桥的算法恰恰就是使用了后向边的性质,而在BFS遍历树中并不存在该性质,所以查找桥只可以用DFS遍历

  • 横叉边:不在遍历树上的边
  • 前向边:在遍历树上的边
  • 理论分析: BFS是一层一层遍历的,所以所有未访问过的节点只可能访问自己下一层的节点或者同层的节点,不可能访问到祖先节点
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

图论

遍历树

查找桥只能用深度优先遍历

查找桥只能用DFS

遍历

BFS遍历树和DFS遍历树 的相关文章

  • 东北大学acm训练第五周

    include

  • 【C语言】图的邻接表——超详细解析

    图的邻接表 我们重点分析一下无向图 邻接表 我们如何将图中所有顶点和边建立起联系 1 我们发现 V0这个顶点与V1和V3相连 通过右边的邻接表可以看到会出现一个以 V0为头结点的单链表 后面连接的元素就是V1和V3 在顶点数组中的下标 2

  • 1600*B. Jumping Jack（数学&&找规律）

    解析 一直往右条 直到第一次超过 x 如果当前和目标点 p x为偶数 则 p x 2 的那一步向左跳 这样会少跳 p x 正好补在多跳的这一段 如果为奇数 则不能除2 则继续跳 直到距离为偶数即可 x和x答案一样 include

  • 数据结构 图 part2

    文章目录 图的遍历 深度优先遍历 DFS 遍历步骤 邻接矩阵的存储 邻接表的存储 广度优先遍历 BFS 遍历步骤 非连通图的遍历 连通分量 如何遍历 生成树 图的遍历 深度优先遍历 DFS 遍历步骤 在访问图中某一起始顶点v后 由v出发 访

  • 图论：Dijkstra算法——最详细的分析，图文并茂，一次看懂！

    文章目录 1 Dijkstra算法简介 2 算法实现范例 3 邻接矩阵 4 Dijkstra 算法的 C 描述 5 Dijkstra 算法的 Matlab 描述 6 温故知新 1 Dijkstra算法简介 背景 迪杰斯特拉算法 Dijkst

  • [STL]vector常见用法详解

    目录 引入 常见用法介绍 1 vector的定义 2 vector容器内元素的访问 3 vector常用函数实例解析 1 push back 2 pop back 3 size 4 clear 5 insert 6 erase vector

  • XYZZY 【POJ - 1932】【SPFA】

    题目链接 有N个点 然后输入1 N个点 输入从它到其他点的血量变化 然后有几个点能到达 最后是这几个点 我们起点为1 终点为N 然后求的是我们是不是有可能或者达到终点 gt 0 直接SPFA跑最长路 感觉是在造样例 6 0 1 2 1000

  • hdu 5756:Boss Bo

    题目链接如下 Problem 5756 先用dfs确定每个节点的序号编号 并且可以获得每个节点可以包括的子树节点区间范围 再用线段树建立一棵树 在第一次建立的时候我们记录每个节点的深度 然后再进行一次dfs 这次dfs用来更新以不同节点为根

  • 无向图的遍历-BFS与DFS

    一 理论部分 无向图的遍历可用深度搜索 DFS 与广度搜索 BFS 深度搜索的基本方式是由图的一个节点1出发然后随机选一个与其相邻的节点2 接着在选择一个与其相邻的节点3 当一条路遍历完后再选择最近一个遍历过的 且相邻节点有未遍历过的节点

  • 图的应用--Prim算法

    图的应用 Prim算法 Prim算法是一种基于顶点的贪心算法 从起始顶点出发 每次迭代选择当前可用的最小权值边 然后把边上依附的其他顶点加入最小生成树 prim算法可以称为 加点法 比较适合稠密图 算法思想 设G V E 是一个加权连通图

  • 大学生团体天梯赛（第五届）

    题目地址 天梯赛 include

  • AcWing 378. 骑士放置（最大独立集&&匈牙利算法）

    输入样例 2 3 0 输出样例 4 解析 题意为求最大独立集 即为总点数 最小点覆盖 include

  • [UVA1364

    评测地址 网址1 网址2 题目描述 题意 给出n位骑士 然后有m个关系 每个关系以格式 a b a b a b给出 表达骑士 a a

  • 《算法图解》读书笔记（二）

    第六章 图 广度优先搜索 1 解决最短路径问题 shortest path problem 的算法被称为广度优先搜索 breadth first search 2 图由节点 node 和边 edge 组成 一个节点可能与众多节点直接相连 这

  • 图论算法＜三＞：判断有向图中是否有存在循环 ，以及环的个数和各个环中的元素

    1 目的 判断有向图中是否有存在循环 以及环的个数和各个环中的元素 2 示例效果 2 1 原始数据 路线起终点整理如下 共计12个顶点 19条边 起点 终点 1 最后的1代表起点终点是连通的 起点 终点 1 2 4 1 起点 终点 1 9

  • hdu1827Summer Holiday【tarjan强连通分量解决最小联系费用】

    1A 撒花 这比买买买开心多了 思路 既然是强连通分量的题 很容易想到形成的东西是一坨一坨的 哈哈 然后如果某一坨入度为0 那么很不幸 这一坨只能直接被威士忌通知 至于具体通知这一坨中的哪一个 枚举一遍就知道了 最后把话费求和 感觉强连通分

  • 714阿里巴巴模拟面试

    介绍一下数据库分页 https www nowcoder com questionTerminal 3577280c810546658f06f19c01ff0345 给定一棵树 求出这棵树的直径 即两个节点距离的最大值 应该是左右子树遍历深

  • 图论--最近公共祖先LCA

    最近公共祖先LCA LCA Least Common Ancestors 即最近公共祖先 是指这样一个问题 在有根树中 找出某两个结点u和v最近的公共祖先 另一种说法 离树根最远的公共祖先 最近公共祖先是相对于两个节点来说的 一般来说 最近

  • The Necklace 【UVA - 10054】【欧拉回路详解】

    题目链接1 题目链接2 题目求的是一串珠子 要让它们首尾相互照应才能串起来 并且 最后要连成一个环 使得最后的珠子的尾与第一个珠子的头相互对应 那么 这道题就是道求欧拉回路的题了 我们要先判断这是不是能够构成欧拉回路 这是个无向图 再对于需

  • 有向图的拓扑排序

    给定一个 nn 个点 mm 条边的有向图 点的编号是 11 到 nn 图中可能存在重边和自环 请输出任意一个该有向图的拓扑序列 如果拓扑序列不存在 则输出 1 1 若一个由图中所有点构成的序列 AA 满足 对于图中的每条边 x y x y

随机推荐

  • 利用RepVGG训练一个cifar-10数据

    文章目录 1 训练整体代码 1 1 repvgg代码 1 2 cifar 10数据 2 学习率更新策略 3 RepVGG原理详解 4 权重convert过程 4 1 推理步骤 4 2 权重转换的步骤 5 导出onnx 5 1 模型转换前的o

  • Linux系统下，永久修改海思开发板的IP地址

    问题描述 给开发板需要重新设置下IP地址 并永久生效 解决步骤 先看下开发板当前的IP 使用命令 ifconfig 3519AV100 ifconfig eth0 Link encap Ethernet HWaddr 9A BC 07 72

  • Linux安装jenkins

    本文基于阿里云租的服务器 centos8版本下安装jenkins 1 安装jenkins 首先先登录jenkins官网去下载对应的包 地址 Jenkins 在上图中选择版本下载即可 下载完上传到你的linux中 如下图所示 至于存放的地址没

  • Vue3.0 + Ts 项目使用element-plus 自动按需导入 使用v-loading报错

    问题展示 使用v loading报错 无法找到样式 element plus es components loading directive style css 解决办法 element plus版本 element plus 2 1 9

  • 【SpinalHDL】verilatorScript.sh: line 1: verilator_bin.exe: command not found

    问题 verilatorScript sh line 1 verilator bin exe command not found 解决 使用msys2安装iverilator后将安装路径下的 mingw64 bin添加到系统环境变量PATH

  • 为什么jmeter做压测叫做“并发”而不叫“并行”？

    昨天开测试方案评审会议 其中有一条性能测试需求为 测试100个用户同时进行查询 响应时间小于2s 方案中给出了100个用户并发操作的说明 关于 并发 二字 百思不得其解 首先 挖出脑袋里大学操作系统课堂上提到的概念 并发 在操作系统中 是指

  • Struts2常用的Ajax标签

    Struts2为了简化Ajax过程 提供了一些常用的Ajax标签 对于一些更复杂的Ajax通信过程 我们可以使用JSON插件来实现 1 div标签 div标签在页面上生成一个div元素 但这个div元素的内容不是静态内容 而是从服务器获取的

  • C#冒泡排序算法

    冒泡排序实现原理 冒泡排序是一种简单的排序算法 其原理如下 从待排序的数组的第一个元素开始 依次比较相邻的两个元素 如果前面的元素大于后面的元素 升序排序 则交换这两个元素的位置 使较大的元素 冒泡 到右侧 继续比较下一对相邻元素 重复步骤

  • FastJson 之 List＜Map＞转化成对应List＜Object＞

    List

  • pytorch分割网络数据输入接口

    pytorch的自定义接口是真的方便 记录一下自己分割数据输入的脚本 coding utf 8 Time 2019 10 31 21 36 Author Yunyun Xu Contact 1443563995 qq com File My

  • PTA(A)1074 Reversing Linked List (25point(s))(坑)

    思路 最后一个点是坑 可能存在孤立点 代码 include

  • vscode的Document This插件

    Document This插件 主要针对JavaScript 和 TypeScript 语言生成注释 光标放在函数名上 连续按 两下 Ctrl Alt D description param number x param number y

  • 【分库分表】sharding-jdbc—分片策略

    目录 StandardShardingStrategy ComplexShardingStrategy InlineShardingStrategy HintShardingStrategy NoneShardingStrategy 标准分

  • [架构之路-185]-《软考-系统分析师》-3-操作系统基本原理 - 文件索引表

    目录 一 文件的索引块 二 索引分配表 三 索引表的链接方案 四 多层索引 五 混合索引分配 一 文件的索引块 存放在目录中的文件 并非是文件的真实内容 目录中记录了文件的索引块是几号磁盘块 文件对应的索引表是存放在指定的磁盘块中的 二 索

  • 线上问题排查----------ORG.APACHE.CATALINA.CONNECTOR.CLIENTABORTEXCEPTION: JAVA.IO.IOEXCEPTION: BROKEN PIPE

    今天公司技术支持的童鞋报告一个客户的服务不工作了 紧急求助 于是远程登陆上服务器排查问题 查看采集数据的tomcat日志 习惯性的先翻到日志的最后去查看有没有异常的打印 果然发现了好几种异常信息 但是最多还是这个 24 Nov 2016 0

  • Golang-使用 goroutine 运行闭包的“坑”

    介绍 在 Go 语言中 函数支持匿名函数 闭包就是一种特殊的匿名函数 它可以用于访问函数体外部的变量 需要注意的是 在 for range 中 使用 goroutine 执行闭包时 经常会掉 坑 因为匿名函数可以访问函数体外部的变量 而 f

  • 【Android】从零搭建组件化项目

    组件化系列文章介绍的内容稍微多了点 本着研究透这玩意的精神 从组件化的简介开始说起 目录 简介 组件化 模块化与插件化 开始 创建配置共享文件 打包模式配置 APT与JavaPoet 简介 什么是组件化 将多个功能模板拆分 重组的过程 为什

  • VM安装windows7 32位

    首先你电脑必须安装了 VMware 推荐版本 VMware12 或者 VMware 11 版本 然后你还需要一个系统镜像 可以通过下面链接下载 Win7 的镜像 复制链接 打开迅雷新建任务即可下载 Windows7 64位 ed2k fil

  • ubuntu换源为阿里云源

    切换目录到 etc apt 目录下 备份sources list文件 sudo cp sources list sources list bak 然后执行换源脚本 在当前路径下 sudo sources sh 脚本下载路径 http dow

  • BFS遍历树和DFS遍历树

    遍历树 按照遍历的顺序 如不清楚图的遍历 请先阅读图的遍历 绘制成树型结构 DFS遍历树 以下为图到遍历树的转化 如果不清楚图的遍历 请先阅读笔者的另一篇文章 图的遍历 动图 按照DFS遍历的顺序 绘制成一棵树 途中红色的边就是遍历过程中没

热门标签