C＃圖遍歷 - 任意兩個節點之間的跟蹤路徑

Question

尋找一種很好的方法來跟蹤兩個節點之間的寬度優先遍歷，而無需瞭解任何關於該圖的信息。與深度優先（如果它不能平移的話，你可以扔掉路徑），在遍歷過程中你可能會有很多「開放」的可能性。

Answer 1

幼稚的方法是建立一個以源節點爲根，其所有連接爲子節點的樹。根據您擁有的空間大小，您可能需要隨時消除週期。您可以使用位圖來實現這一點，其中每個位對應圖中的不同節點。當您到達目標節點時，您可以按照父鏈接回到根目錄，那就是您的路徑。由於您首先考慮的是寬度，即使您沒有消除週期，也可以確信它是最短的路徑。

Answer 2

對於廣度優先搜索，您至少需要存儲兩件事。一個是已經訪問過的節點集合，另一個是從訪問節點直接訪問但不能訪問的節點集合。然後你保持移動狀態從後者到前者，爲後者添加新的可達狀態。如果你需要從根到某個節點有一條路徑，那麼你還需要爲上述集合中的每個節點（根除外）存儲一個父節點。

通常，訪問節點集合和未訪問子節點集合（即，所看到節點集合）的並集存儲在散列表中。這是爲了能夠快速確定之前是否已經看到「新」狀態，並且如果是這種情況，則忽略它。如果你的狀態真的很多，你可能確實需要一個位數組（如Joseph Bui所提到的（57509），但是除非你的狀態可以直接或間接地用作該數組的索引，否則你需要使用散列函數將狀態映射到索引，在後一種情況下，您可能會完全忽略某些狀態，因爲它們映射到與另一個（和可見）節點相同的索引，因此您可能需要小心這一點。另外，要獲取路徑你仍然需要存儲父信息，這幾乎否定了位陣列的使用

未訪問但可見節點的集合可以存儲爲一個隊列（位數組對這個集合沒有用處，因爲陣列將大部分爲空，並且發現下一個設置位相對昂貴。）

Answer 3

我剛剛提交了一個解決方案over here也適用於這個問題。

基本上，我只保留訪問節點的單個列表（真正的堆棧）。在遞歸或保存解決方案之前，將節點添加到列表中。之後，請務必從列表中刪除。

Answer 4

如果您使用的是.NET 3.5，請考慮使用Hashset來防止重複節點被展開，這種情況發生在圖形中有周期時發生。如果您對圖表內容有任何瞭解，請考慮實施A* search以減少展開的節點數量。祝你好運，我希望它適合你。

如果你仍然是一個樹型工具的愛好者，那麼關於圖形和圖形搜索的話題有很多優秀的書籍，比如Peter Norvig和Stuart Russell的「人工智能：現代方法」。

在我的迴應中的鏈接似乎有一個bug，他們的Hashset是：http://msdn.com/en-us/library/bb359438.aspx和A *搜索：http://en.wikipedia.org/wiki/A*_search_algorithm