如何在有向圖中找到最小的一組頂點，以便可以達到所有其他頂點

給定一個有向圖，我需要找到可以到達所有其他頂點的最小頂點集合。如何在有向圖中找到最小的一組頂點，以便可以達到所有其他頂點

所以函數的結果應該是最小的頂點數，通過跟隨有向邊可以達到所有其他頂點。

可能的最大結果是如果沒有邊緣，所有節點都會返回。

如果圖中有周期，則爲每個週期選擇一個節點。哪一個並不重要，但如果算法再次運行，它應該是一致的。

我不確定這是否存在現有算法？如果是這樣，它有一個名字？我試圖做我的研究，最接近的東西似乎是找到mother vertex 如果是這種算法，是否可以詳細闡述實際算法，因爲在該鏈接中給出的答案有點模糊。

鑑於我必須在JavaScript中實現此，首選項將是一個.js庫或JavaScript示例代碼。

來源

2010-12-20 Ryan Ramage

您在標題中提到了一個DAG（有向無環圖），但隨後提到「如果圖中有周期......」您是否只是指有向圖？ – Davy8 2010-12-20 18:59:07

沒有你的問題是不同的 – 2010-12-20 19:09:24

對不起，是的，它只是一個有向圖，而不是DAG，因爲可以有循環。我已經更新了標題。 – 2010-12-20 19:11:58

根據我的理解，這只是在圖中找到強連通的組件。 Kosaraju's algorithm是這樣做的最新方法之一。它使用兩次深度優先搜索來對付一些僅使用一次的算法，但我最喜歡它的簡單概念。

編輯：爲了擴大這一點，最小的一組頂點被發現，正如在這篇文章的評論中建議的那樣： 1.找到圖的強連通組件 - 將每個組件縮減爲單個頂點。 2.剩餘的圖是一個DAG（或者如果存在不連貫的組件，則是一組DAG），其中的根形成所需的一組頂點。

來源

2010-12-21 18:05:33 kyun

爲了擴大這一點：1.找到強連接的組件。 2.對於每個頂點，任意選擇其中一個頂點，並將強連通的組件收縮到該頂點。這留下了一個DAG。 3.選擇邊緣爲零的所有剩餘頂點。完成。（道歉爲我所介紹的任何錯誤！） – 2010-12-21 18:17:09

如果我看看http://en.wikipedia.org/wiki/Strongly_connected_component上的示例圖，我想要的結果是[a]，[b]或[E]。正如你可以從那些起始節點到所有其他節點（通過多跳）。但是，你建議的算法會產生[a，c，g]嗎？ – 2010-12-21 18:37:39

我應該更清楚。正如Jason Orendorff所建議的那樣，您必須找到強連通的組件（例如 - [abef]，[fg]和[cdh]），將每個任意減少到一個頂點（比如[a] [g]和[c] ）。現在，找到這些組件之間的連接（生成一個DAG，因爲所有的週期都收縮到一個頂點） - 這將是[ac] [cg]並選擇剩餘圖中的「根」（節點中沒有）成爲你的解決方案。 – kyun 2010-12-21 19:24:18

[編輯＃2：正如Jason Orendorff在評論中提到的那樣，發現反饋頂點集是過度殺傷性的，並且會產生一個比通常所需更大的頂點集。 kyun's answer（或將是，當他/她在評論中的重要信息增加了）做正確的方式]

[編輯：我有兩個步驟南轅北轍......現在我們應該保證極小。]

呼叫所有頂點在度零Z。 Z中沒有頂點可以通過任何其他頂點到達，因此它必須包含在最終集合中，其中必須包含在中。
使用深度優先（或寬度優先）遍歷，追蹤從Z中每個頂點可到達的所有頂點並刪除它們 - 這些頂點已被Z「覆蓋」。
該圖現在純粹由定向循環組成。找到一個feedback vertex setF它給你一個最小的可能的頂點集，它的去除會破壞圖中的每個循環。不幸的是，如維基百科鏈接所示，這個問題對有向圖而言是NP難的。
您正在尋找的頂點集是Z+F。

來源

2010-12-20 19:30:16

爲什麼找到一個反饋頂點集，而不是kyun建議的？這似乎是不必要的額外工作。 – 2010-12-21 18:14:59

@Jason：想一想，你是對的。沒有必要在每個循環中找到一個頂點。 – 2010-12-22 00:02:56

如何在有向圖中找到最小的一組頂點，以便可以達到所有其他頂點

回答

相關問題