我有一个无向图,表示地图各区域之间的连通性。我想识别一组节点(区域),这些节点(区域)可以在不创建图分区的情况下被删除。
我试过的是:
遍历树(BFS,DFS.),存储深度并选择深度较高的节点(O(n))。计算完毕后,我可以在每次删除时更新O(~1)中的深度--通过检查相邻节点的深度(连接度不超过某个阈值)。
有更便宜的方法吗?如果你不知道这个问题的学术术语,也很难找到图表文献。我的图表在200到500个节点之间。
发布于 2014-07-11 14:25:18
发布于 2014-07-10 10:29:07
您正在解决的问题可以归结为图中的桥梁发现问题。
算法:-
https://stackoverflow.com/questions/24673646
复制相似问题