查找关节点组

Question

我有一些无向图,我试图找到清晰点.有例子

它有一个关节点 - 顶点#2.

但我也想找到#4和#5作为清晰组点.因为联合移除#4,#5也将图形切割成未连接的子图.我想象示例图作为3个连接的子图.

我怎样才能找到指定的切点？

Answer 1

我认为除了循环遍历所有组合之外没有任何更快的方法，因为您没有任何限制。（我什至认为这个测试没有意义。）

\n\n

虽然没有指定编程语言，但请让我使用 python 作为示例。

\n\n

当你进行关节点搜索时，最知名的方法是Tarjan\xe2\x80\x99s算法。我想读这篇文章的每个人都知道这一点，所以如果您不介意的话，我将跳过它作为一个函数，您可以在https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in中找到-图表/ .

\n\n

class Graph:\n   #From www.geeksforgeeks.org\ndef worker(g, prefix, arr, u):\n\n    container = g.graph[u]\n    if u in g.AP():\n        print prefix\n        arr.append([prefix])\n        del g\n    else:\n        for i in container:\n            if str(i) not in prefix.split(\' \'):\n                new_prefix = prefix + \' \' + str(i)\n                new_g = copy.deepcopy(g)\n                new_g.combineNode(u, i)\n                if len(new_g.graph) > 1:\n                    worker(new_g, new_prefix, arr, i)\n\nstruct = {\n    0:[1,12,13,14,15],\n    1:[2,12,14,15],\n    2:[3,4,5,14],\n    3:[4],\n    4:[5,6],\n    5:[6,9],\n    6:[7,8,9],\n    7:[8,10,11],\n    8:[9,10,11],\n    9:[10],\n    10:[11],\n    12:[15],\n    13:[14,15]\n} \ng1 = Graph (total)\n\nfor key,value in struct.iteritems():\n    for child in value:\n        g1.addEdge(key, child)\n\nresult = []\nfor i in range(0, total):\n    print \'Remove root \' + str(i)\n    worker(g1, str(i), result, i)\nprint result\n

\n\n

我写它是为了防止只有最小长度的组来划分图。比如说 (4, 5)，如果它已经是 AP，那么连接到它们的任何点也应该是 AP。

\n\n

以防万一，任何人都想要完整的测试代码。https://gist.github.com/MichaelKHTai/c438fd0911d0584be1e37f1fd1599b7e

\n\n

此外，应该通过跳过重复的节点组来优化它，例如（4,5）和（5,4）。

\n