首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >寻找划分图的节点

问寻找划分图的节点
EN

Stack Overflow用户
提问于 2014-07-10 10:00:53
回答 2查看 269关注 0票数 1

我有一个无向图,表示地图各区域之间的连通性。我想识别一组节点(区域),这些节点(区域)可以在不创建图分区的情况下被删除。

我试过的是:

遍历树(BFS,DFS.),存储深度并选择深度较高的节点(O(n))。计算完毕后,我可以在每次删除时更新O(~1)中的深度--通过检查相邻节点的深度(连接度不超过某个阈值)。

有更便宜的方法吗?如果你不知道这个问题的学术术语,也很难找到图表文献。我的图表在200到500个节点之间。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2014-07-11 14:25:18

您希望找到的节点是,而不是接口点。请参阅该维基百科页面为一些算法提供了解决方法,解决了节点检测的问题。另见此页。最后,注意其中一些算法已经在诸如艾格图之类的工具中实现了。

PS:这与Vikram发现的问题非常相似,但并不完全相同,因为关注的焦点是节点,而不是链接。

票数 1
EN

Stack Overflow用户

发布于 2014-07-10 10:29:07

您正在解决的问题可以归结为图中的桥梁发现问题。

算法:-

  1. 用tarjan的方法计算图中的所有桥梁。
  2. 然后删除没有桥接器作为边缘的节点。
  3. 然后重新评估由网桥划分的被移除节点的子图中的网桥。
  4. 继续执行2&3操作,直到没有要删除的节点为止。
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/24673646

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档