定向圖發現節點的輸入邊緣並非都可以從給定節點

Question

在最近的一次採訪中，我被問到了下面的問題。

給定一組節點和邊以及一個起始節點指向最終結束節點。在下圖中，從1開始到15結束。他們的問題是以節點2（或任何節點）爲起點，我們如何才能找到其路徑中的下一個節點，其輸入邊緣不能全部從節點2到達即我們如何能達到14）。

我該怎麼做，僞代碼應該沒問題。

Answer 1

我看不出有什麼辦法避免遍歷整個圖形至少一次（假設節點沒有父母的鏈接）。如果這是確定的，然後根據地圖上一個簡單的解決方案，從節點到集即時父母（「父地圖」下同）爲：

• 寫一個擴展的起點下的所有節點父地圖例行節點（使用dfs）。該例程不需要探索地圖中已經是鍵的節點。

• 爲圖中的每個節點調用上面的例程。這給出了從節點到父母的完整映射（圖的轉置，有效）。

• 使用新地圖從問題中的給定節點（例如2）調用上述例程。這給出了從父節點可到達的從節點到父節點的映射。

• 使用來自給定節點的bfs，找到兩個映射中父節點的不同的第一個節點。

你不需要實際的父節點存儲在地圖（這只是最簡單的解釋方式）;你可以通過標記訪問節點並存儲父節點數量來做類似的事情。

還有另一種說法：找到圖的轉置和從給定節點可到達的節點集。然後從給定節點的bfs中找到第一個節點，其中轉置導致可達集之外的父節點。（這真的只是個問題......）

Answer 2

我會說：

1. 發現它們是從節點2.運行BFS或任何完整的算法可達找到設置所有可達R節點。查找無法訪問使用U = V - R

2. 查找所有可從這些無法訪問的節點到達的節點，無論您何時找到節點，您是否位於節點2的可到達列表中。如果是，則只保存邊緣用過的。

在第二步中，您連續挑選U中的節點並執行BFS。你把節點不同：

• 無論何時你發現屬於U這是已經選擇了一個節點X，你停止
• 無論何時你發現屬於U，而不是選擇了一個節點Y，你從U
刪除此節點
• 當您在R中找到節點時，您會記住邊緣並將此節點標記爲「不要永遠訪問」。

Answer 3

1. 標記可從起始節點到達的所有邊。
2. 找到可從具有未標記輸入邊緣的起始節點到達的第一個節點。

Answer 4

• 如果該算法做一次查找，然後只需考慮的StartNode：
  • 找出所有從起始節點到達的節點。 （通過運行BFS圖形遍歷算法）
  • 保存從StartNode可訪問的節點列表，以便高效查找散列表。
  • 對於其是從當前節點可到達的（按順序）的每個節點：
    • 校驗輸入節點（起始vertext進入邊緣的）
    • 如果所有傳入的節點在哈希表中是可用的，則移動到下一個可到達節點 - 否則返回此節點。