基环树
- 概念
- 基环树相关问题
转载自https://www.codetd.com/article/7620085
概念
具有N个点N条边的连通图,如果不保证连通,它就会称为基环树森林
在有向图中，我们也有类似的概念。Ｎ个点、Ｎ条边、每个节点有且仅有一条入边的有向图就好像以“基环”为中心，有向外扩展的趋势，故称为“外向树”。Ｎ个点、Ｎ条边、每个节点有且仅有一条出边的有向连通图就好像以“基环”为中心，有向内收缩的趋势，故称为“内向树”。外向树和内向树也经常统称为“基环树”。如果不保证连通，那么Ｎ个点、Ｎ条边、每个节点有且仅有一条出（入）边的有向图也可能是“内（外）向树森林”的形态。
基环树（Ｎ个点Ｎ条边的连通无向图）
内向树（每个点的出度都为1，进了环就出不去）
外向树（每个点的入度都为1，出了环就回不来）
基环树相关问题
基环树的结构仍然很简单，但比树要复杂些，因此常作为一些经典模型的扩展，以适当增加题目的难度，例如基环树的直径、基环树两点之间的距离、基环树动态规划等。无论哪种模型，求解基环树相关问题的方法一般都是先找出图中唯一的环，把环作为基环树的广义“根节点”，把除了环之外的部分按照若干棵树处理，再考虑与环一起计算。
- 基环树的直径
- 基环树两点之间的距离
- 基环树动态规划
最后
以上就是乐观冰淇淋最近收集整理的关于【数据结构】基环树(环套树)概念基环树相关问题的全部内容，更多相关【数据结构】基环树(环套树)概念基环树相关问题内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复