心得经验总结:无向图:计算亏格(环的孔洞)

简介: 心得经验总结:无向图:计算亏格(环的孔洞)

前一篇文章:无向图:计算亏格(环的孔洞)

首先,判断图中是否存在环。方法,找到联通子图,循环删除度为1的节点,同时删除边。直到不存在度为1的边,则联通子图只剩下环或者复杂环。

//代码效果参考:http://www.zidongmutanji.com/zsjx/426541.html

在不需要遍历出环的算法里面,可以通过欧拉公//代码效果参考: http://www.zidongmutanji.com/bxxx/203054.html

式直接计算亏格。孔洞的个数。

公式: //代码效果参考:http://www.zidongmutanji.com/bxxx/181028.html

nGenus = l-p+1; l为边的个数,p为点的个数。

过程:对于所有联通的集合,循环删除度数为1的顶点,同时删除边;计算亏格。

然而,上述过程出现了问题。主要是平面图中若严格按照直线边进行拓扑,出现了复杂图,即立体图。

如图:

改进方法:

使用多边形并差计算,以此寻找孔洞,以此来应对复杂图的特殊情况。

代码段:

import seisw.util.geom.Clip;

import seisw.util.geom.Poly;

import seisw.util.geom.PolyDefault;

相关文章
|
1月前
论多段图的最短路径问题(我认为本质上还是暴力枚举法)
本文讨论了多段图最短路径问题的解决方法,认为本质上是使用暴力枚举法,通过逐步计算每个阶段点的最短距离来确定从起点到终点的最短路径。
37 1
论多段图的最短路径问题(我认为本质上还是暴力枚举法)
|
5月前
|
存储 算法 C语言
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
87 1
数据结构实验之图论二:图的深度遍历
数据结构实验之图论二:图的深度遍历
|
6月前
|
存储 算法 搜索推荐
深度优先遍历与广度优先遍历:理解它们的原理与差异
深度优先遍历与广度优先遍历:理解它们的原理与差异
|
6月前
|
机器学习/深度学习 算法 测试技术
【单源最短路 图论】882. 细分图中的可到达节点
【单源最短路 图论】882. 细分图中的可到达节点
|
6月前
|
机器学习/深度学习 测试技术
【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离
【图论】【状态压缩】【树】【深度优先搜索】1617. 统计子树中城市之间最大距离
|
算法
广度优先遍历(BFS):逐层探索图的算法奥秘
在图论中,广度优先遍历(Breadth-First Search,BFS)是一种图遍历算法,它以一种逐层的方式探索图的节点。通过从起始节点开始,逐层向外扩展,BFS能够帮助我们解决许多与图相关的问题。
126 0
|
6月前
|
人工智能 BI 测试技术
【图论】【树形dp】【深度优先搜索】2538. 最大价值和与最小价值和的差值
【图论】【树形dp】【深度优先搜索】2538. 最大价值和与最小价值和的差值
|
存储 索引
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
78 0
|
算法
【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)
【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)
269 0
【数据结构和算法】图的应用(最小生产树、最短路径、拓扑排序、关键路径)