如何爲鄰接表構造適合BFS的數據結構？

Question

關於構建和搜索鄰接樹的面試問題，但我從未與他們合作過，所以我不知道從哪裏開始。

我有一個包含像數據的文件：

2 13556 225 235 
225 2212 226 
2212 8888 2213 
8888 144115 72629 141336 8889 146090 129948 167357 
144115 160496 163089 144114 144116 
... 

格式化爲這樣：

<parent node> <child node> [ <child node> [ …] ] 

每個邊緣具有長度1

我然後需要計算這兩者之間的最短路徑的節點（這兩個是在問題中指定的）。然後，我需要在大O符號中提供估計的複雜性。

後者我可能大概是說，儘管直到現在我還沒有聽說過它，而維基百科在理解如何將搜索功能分解爲大O方面並沒有多大幫助，但我會以後擔心（除非有人有一個好的鏈接，他們可以分享）。

我現在所關心的是試圖對這些數據建模，然後搜索最短路徑。就像我說過的，我之前從來沒有使用過這種結構，所以我對於哪裏開始都感到不知所措。我在鄰接名單here上發現了另一個問題，但它似乎並不是我所期待的，除非我完全忽略了這一點。在我看來，輸入數據需要重新組織以滿足在這個問題中使用的結構，而我正在從文件中讀取數據，所以我想我需要遍歷每個節點和節點列表以確定我是否已經進入了家長，並且可能需要很長時間。我也不知道如何使用該結構創建bfs搜索。

這裏有很多搜索的例子，所以我可能會理清那個部分，但是獲取數據模型的任何幫助都可以從數據文件加載並適用於bfs搜索（或，如果有更好的搜索選項，請給我上課），會有很大的幫助。

Answer 1

您希望將這些數據存儲在HashTable<int, List<int>>（字典）（鏈接）中，鍵爲int（NodeID），值爲List<int>，其中這些是來自節點的可能目標，它是鍵。

您需要有另一個HashTable<int, int>（ShortestPathLastStep），它將存儲兩個NodeID。這將代表到達給定節點的最短路徑中的最後一步。你需要這個才能播放最短的路徑。

要執行BFS（廣度優先搜索），你會使用Queue<int>（bfsQueue）。將起始節點（在您的問題中給出）推入隊列。現在執行以下算法

-- currentNodeID = pop bfsQueue 
---- children = Links[NodeID] 
------ foreach (childNodeID in children) 
--------- if (childNodeID == destinationNodeID) 
----------- exit and playback shortest path 
----------if (!ShortestPathLastStep.contains(childNodeID)) 
------------ ShortestPathLastStep.Add(childNodeID, currentNodeID); 
----------bfsQueue.Push(childNodeID); 
----------goto first line 

該解決方案假設在任意兩個節點之間的傳輸是恆定成本。這對於BFS來說非常理想，因爲第一次到達目的地時，您將採取最短路徑（如果鏈接長度可變，則不是這樣）。如果鏈接長度不是恆定的，則在決定覆蓋ShortestPathLastStep值時必須添加更多邏輯，直到隊列爲EMPTY時才能退出，並且只會將節點推入隊列中從來沒有去過節點（它不會存在於短路徑列表中），或者你發現這種新的到達方式比最後一種方式要短（現在你必須重新計算節點的最短距離你可以從這個節點進入）。