實現沒有鄰接表的bfs

我正在解決BFS上的問題。我能夠通過鄰接表實現BFS算法，但我被困在這個問題中：我必須告訴是否有可能從起點行進迷宮到迷宮終點的距離。單元格包含0或1。由於它不能通過包含值1的單元格傳播，並且兩個單元格之間的移動只有在它們共享一個公共邊緣時纔有可能。那麼如何直接在這裏實現BFS而不需要進入鄰接表呢？實現沒有鄰接表的bfs

來源

2013-09-26 TSP1993

如何查看相鄰單元格的地圖（2d數組）而不是鄰接列表？ – Shahbaz

@Shahbaz你不需要明確存儲鄰接表來解決問題。 –

@IvayloStrandjev，是不是我說的？ – Shahbaz

您不必將圖形顯式表示爲做BFS的鄰接表。從每個單元格(x,y)你知道哪些是它的4個潛在的鄰居 - (x-1, y),(x, y-1),(x+1, y)和(x, y+1)。我說potential，因爲它們中的任何一個都可能脫離桌子，因此不能成爲鄰居。現在只需用一對整數 - 它的座標和隊列中的推對來標識每個頂點。當從隊列中彈出時，使用上面所述的方法訪問四個可能的鄰居。

希望這足以幫助你 - 我可以提供完整的代碼，但最好是自己寫。

來源

2013-09-26 12:20:08

是啊，現在我明白了。但我不知道要在C中使用pair嗎？ – TSP1993

不，我不想要的代碼。 – TSP1993

@RahulKumarSingh，只是得到兩個不同的變量。有你的一對！但是，嚴重的是，你創建一個'struct'把這兩個變量放在裏面。 – Shahbaz

實現沒有鄰接表的bfs

回答

相關問題