尋找關鍵節點的快速算法是什麼？

我正在尋找一種快速的方法/算法來查找圖中的哪些節點是至關重要的。尋找關鍵節點的快速算法是什麼？

例如，在該圖中： alt text

節點號2和5是至關重要的。

我目前的方法是嘗試一次從圖中刪除一個非端點節點，然後檢查是否可以從所有其他節點到達整個網絡。這種方法顯然不是非常有效。

什麼是更好的方法？

2010-09-09 monoceres

參見：http：//portal.acm.org/citation.cfm？id = 1480409。他們證明檢測關鍵節點是NP完全的，所以我不會期望有大幅度的改進。 – 2010-09-09 16:08:22

你關心的是節點，而不是鏈接？例如，如果我有3到6之間的鏈接，那麼要找到關鍵節點，我需要首先找到可以刪除的鏈接。 – 2010-09-09 16:08:45

@Jerry Coffin - 我在電氣網絡分析課上記得有關此事的一些事情，但我需要回顧一下，但根據簡化情況，這可能很容易或很難解決，因爲一般情況太困難了，正如你所指出的那樣。 – 2010-09-09 16:11:13

請參閱biconnected components。將它們稱爲關節點而不是關鍵節點似乎會產生更好的搜索結果。

在任何情況下，該算法都包含一個簡單的depth first search，您可以在其中維護每個節點的某些信息。

2010-09-09 16:37:15 IVlad

非常感謝，清晰點確實給出了更好的結果，我發現了一些非常有用的鏈接深度優先搜索。 – monoceres 2010-09-09 19:42:57

有幾種更好的方法。 research is always helpful

但由於這是功課，練習的點很可能是要弄清楚自己

提示：你怎麼能裝點圖告訴你節點取決於什麼其他節點上的東西，並會這些信息可能有助於發現關鍵節點？

2010-09-09 16:11:41

回答