我有一个表示 map 区域之间连通性的无向图。我想确定可以在不创建图形分区的情况下删除的节点组(区域)。
我尝试过的:
遍历树(BFS，DFS ...)，存储深度并选择具有更高深度的节点(O(n))。计算完成后，我可以通过检查邻居节点的深度(连通性不超过特定阈值)在每次移除-添加时更新 O(~1) 的深度
有没有更便宜的方法来做到这一点？如果您不知道该问题的学术术语，寻找图谱文献也非常困难。我的图表在 200 到 500 个节点之间。
最佳答案
您正在解决的问题可以简化为bridge finding图中的问题。
算法:-
- calculate all bridges in the graph using tarjan's method.
- then remove a node which does not have bridge as a edge.
- Then re-evaluate the bridges in subgraph of the removed node partitioned by bridges.
- Continue doing 2 & 3 until there is no node to remove.
关于algorithm - 查找划分图的节点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24673646/