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

Question

5

我正在寻找一种快速的方法/算法来查找图中关键节点。例如，在这个图中：节点2和5是关键节点。 alt text

我的当前方法是逐个删除非端点节点，然后检查是否可以从所有其他节点到达整个网络。这种方法显然不太高效。有更好的方法吗？

- monoceres

2

请参阅：http://portal.acm.org/citation.cfm?id=1480409。他们证明检测关键节点是 NP 完全问题，因此我不会期望有显著的改善。 - Jerry Coffin

你关心的是节点而不是连线？比如说，如果我有一个连接3和6的链接，那么要找到关键节点，我需要先找到可以移除的链接。 - James Black

@Jerry Coffin - 我记得在电力网络分析课上学过这方面的知识，但我需要再查一下资料。根据简化程度的不同，这个问题可能很容易或者非常难以解决，正如你所指出的那样，一般情况下是非常困难的。 - James Black

@Jerry Coffin - 那篇文章并未证明任何事情，实际上即使是OP的算法也在多项式时间内运行。他们证明了识别变量是NP完全的，不管它意味着什么。关键节点（关节点、割顶）可以在O（节点数+边数）中找到。 - IVlad

有趣的是，我在浏览器中关闭的最后一个标签是来自林雪平大学编程竞赛的http://uva.onlinejudge.org/external/3/315.html，等等，难道Monoceres来自林雪平吗？ - Albin Sunnanbo

哈哈！有趣的巧合，是的，我把它标记为作业，这样我就不会被直接给出答案，而是得到一些有用的提示 :) - monoceres

2个回答

1

有几种更好的方法。研究总是有帮助的

但既然这是一份作业，练习的重点很可能是要自己找出答案。

提示：您如何装饰图表以告诉您哪些节点依赖于其他节点，这些信息是否可能有助于发现关键节点？

- Steven A. Lowe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- IVlad · Accepted Answer

请参见双连通分量。将它们称为关键节点而不是割点似乎能够产生更好的搜索结果。

无论如何，该算法由简单的深度优先搜索组成，您需要为每个节点维护一些信息。