誘導子圖;兩個節點之間的路徑存在

Question

對不起，我的文本牆儘可能簡潔！

我從G內部得到了一個非常大的有向圖G和頂點子集S，我想要做的是找到由S引發的G的子圖，並附加考慮如果某些路徑存在於G中的頂點p和頂點q之間，在感應子圖中這兩個頂點之間存在邊。這是關鍵;它比一般的誘發子圖問題更復雜一些（我認爲）。

我能想到的解決問題的最基本的方法如下（我知道它可能不是最有效的，讓我知道，如果你有沒有其他建議太複雜來實現）：對於S中的每一對頂點都測試G中它們之間存在的路徑。如果存在這樣一條路徑，則在p和q之間插入一條邊在感應子圖中。對我而言，n^2的時間不是那不好。

所以，我想我有兩個問題： 1）什麼是確定兩個頂點之間是否存在路徑的最快方法？我不需要知道路徑，只是它是否存在。此外，如果我可以對整個圖進行一些預處理以加快計算速度，那麼可能會是什麼情況，因爲我必須在每對頂點之間執行此計算？

2）有沒有比我建議找到我描述的誘導子圖的類型更快的方法？

非常感謝您的幫助！

Answer 1

發現兩個頂點之間是否存在路徑的問題稱爲傳遞閉包問題，在一般情況下它與矩陣乘法一樣困難。我首先在你的圖上運行強連通組件算法，將週期壓縮成單個節點並形成有向圖。如果你幸運的話，你會有一些大的週期，這會使後續的傳遞性問題變得容易。然後我會運行Floyd Warshall，在該圖上配對最短路徑算法來計算傳遞閉包，因爲它的代碼非常簡單。也許基於o（n^3）矩陣乘法的算法之一會更快，但我懷疑它會更快，因爲常數是如此之低Floyd Warhsall。

以下是strongly connected components的快速算法。

這包含matrix multiplication and transitive closure.

等價我不知道的證明，如果有什麼好的辦法來解決計算傳遞閉包爲您解決原來的問題。我懷疑不是，但另一方面，有時候聰明的人會想出很棒的東西。