algorithm - 找到关键节点的快速算法是什么？

Question

我正在寻找一种快速方法/算法来查找图中的哪些节点是关键的。

例如，在这张图中:

2 号和 5 号节点很关键。

我目前的方法是尝试一次从图中删除一个非端点节点，然后检查是否可以从所有其他节点到达整个网络。这种方法显然效率不高。

有什么更好的方法？

Answer 1

参见 biconnected components .称它们为连接点而不是关键节点似乎会产生更好的搜索结果。

无论如何，该算法由一个简单的 depth first search 组成您在其中维护每个节点的某些信息。