1

I have a non-directed graph that represents the connectivity between regions of a map. I'd like to identify groups of nodes (regions) that could be removed without creating graph partitions.

What I have tried:

Walking the tree (BFS, DFS...), storing the depths and selecting the nodes with the higher depth (O(n)). Once calculated, I can update the depths in O(~1) on each removal-addition by checking the depth of neighbour nodes (connectivity does not exceed a certain threshold)

Is there a cheaper way to do this? Also finding graph literature is also very hard if you don't know the academical term for the problem. My graphs are between 200 and 500 nodes.

4

2 回答 2

2

您正在解决的问题可以简化为在图中寻找问题的桥梁。

算法 ：-

  1. 使用 tarjan 的方法计算图中的所有桥梁。
  2. 然后删除一个没有桥作为边的节点。
  3. 然后重新评估由桥划分的已删除节点的子图中的桥。
  4. 继续执行 2 和 3，直到没有要删除的节点。
于 2014-07-10T10:29:07.920 回答
1

您想找到不是 关节点的节点。参照。这个Wikipedia 页面提供了一些算法，可以解决检测关节点的问题。另请参阅此页面。最后，请注意其中一些算法已经在igraph等工具中实现。

PS：这与 Vikram 确定的问题非常相似，但不完全相同，因为重点是节点，而不是链接。

于 2014-07-11T14:25:18.577 回答