查找有向圖中任意兩個頂點之間的所有邊線

Question

我有一個算法來查找有向圖的邊從頂點或者到任何其他具有O（| V | + | E |）的頂點。時間複雜性（基於DFS）。我必須開發一種算法來查找O（| V || E |）中任意兩個頂點之間的邊。

你有任何建議或提示，以實現這一目標嗎？

如果我重複每個頂點的DFS-Visit，只有第一次頂點是白色的，接下來的時間這個調用將什麼也不做。 如果我在這之前重置顏色，那麼算法將是O（| V |^2 + | V || E |）。

非常感謝你提前！

Answer 1

拆分成子問題的問題，在這裏你可以使用你的算法來達到所需的複雜性，具體如下：

• 使用的結構圖DFS（底層無向圖），並找到所有的連接組件。讓它們成爲（V1，E1），（V2，E2），...，（Vk，Ek）
• 對於每個這樣的組件，運行你的算法。顯然，在不同組件中的2個節點之間沒有橋接。

的複雜性將是：
步驟1是O(V+E) - DFS。
步驟2：

• 我們使用您開發的每個節點的每個組件上的黑 盒重複算法，等等組件i的複雜性是O(V_i^2 + V_i*E_i)
• 由於每個構件i：E_i >= V_i -1（否則它不是 連接，樹有|V|-1邊緣），O(ViEi + Vi^2) = O(ViEi)。
• 因此，此步驟的複雜程度爲O(V1E1 + V2E2 + ... + VkEk)。

• 注意，對於每個iE_i <= E，因此複雜性是不 差那麼：

  O(V1E + V2E + ... + VkE) = O(E *(V1+V2+ ... + Vk)) = O(VE) 
  

因此，總的複雜度爲O(VE)，根據需要。