算法图算法

遍历树的概念与性质

字数统计: 840字   |   阅读时长: 2分
,

摘要: 图的遍历树的概念与性质

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

考虑图的遍历，BFS 和 DFS 过程中，每个节点都有一个深度或者层次，也就是到作为起点的节点的距离。各个节点按照深度以及递归和回溯的顺序关系，可以组织称一棵树，称为 DFS 遍历树、BFS 遍历树。

与遍历序差不多，遍历树也是遍历过程的副产品，具有一些有用的性质，可以解决一些问题。参考文章 遍历序的概念与性质。

大部分的算法，可以用 DFS/BFS 之一的，用另一个也能完成。但是寻找桥的算法，只能用 DFS 做，主要的原因就是需要用到 DFS 独特的性质。

DFS 和 BFS 各自有自己的特性，BFS 的特性主要就是 BFS 的过程直接实现了无权图最短路径的特性。本文主要关注 DFS 遍历树的特性。

图的遍历树

BFS 和 DFS 均有对应的遍历树，图中的边根据是否出现在最终的遍历树上，分为前向边与回边。

  • 前向边：最终在遍历树上的边
  • 回边：最终不在遍历树上的边

DFS 遍历树

无向图的例子

原图 DFS树
原图,遍历树的根为0 dfs遍历树

特性：回边只会连向祖先，不同子树不会互相连边。

典型应用

有向图的例子

原图与对应的 dfs 树，dfn 序。

典型应用

BFS 遍历树

原图 BFS树
原图,遍历树的根为0 bfs遍历树

特点：分层，回边只出现于同层或相邻两层，同时可以得到源点到各点的最短路。

典型应用

DFS 树和 BFS 树的回边与子树的关系

回边与子树的关系

BFS树与DFS树的其它应用

bfs树

$o(nm)$ 求边权为 1 的最小环

考虑对一个点求出一个bfs树:

  • 由于边权为一，它的回边必定只出现在相邻两层或者是同层
  • 这条回边连的两个点到源点的最短路是互不相交的，因为如果相交会有更小的环出现
  • 找到一个经过这条回边以及源点的一个最小环

枚举源点与回边就可以找出所有的最小环

dfs树

删除哪些边后可使原图不存在奇环

由于 dfs 树的回边是只连向祖先的，因此一个环的长度可以用 d[node] - d[root[node]] 表示，其中 root[node] 表示 DFS 树中 node 所在子树的根节点。

若长度是奇数，则路径上的边都可以标记一下

有的环可能由多对点包含，考虑 x,y,root[x],root[y]，他们可以组合出 abs(d[root[x]] - d[root[y]]) + abs(d[x] - d[y]) 的环：

  • 偶环与偶环组合或者奇环与奇环组合，那么可以组合成偶环，
  • 奇环与偶环组合，那么就要删除那些被奇环包含但不被偶环包含的边才能破坏这种复合的奇环。
Share