搜索最短路徑中的BFS性能

有一個圖表，最多可達10000個節點，每個節點最多可以有4個相鄰節點。圖爲未加權和無向。任務是查找從節點A到節點B的最短路徑。路徑長度是路徑中訪問的節點數。 BFS算法可以在小於一秒找到那條路徑並且使用小於64mB的內存？搜索最短路徑中的BFS性能

原始問題與網格（最多100 * 100）和可以訪問的地方，開始地點，結束地點和無法訪問的地方。我的第一個猜測是將其縮減爲使用BFS搜索找到未加權圖中的最短路徑。但是，我不知道該解決方案的大圖的速度和內存使用情況。

來源

2013-03-10 Hypnotic

1秒？ 64 MB？對不起，但是如果你沒有定義單個操作的持續時間，比如一個節點的訪問，或者圖形所使用的編碼類型（列表，矢量......），這個問題就沒有答案。 – Luca 2013-03-10 22:10:00

圖的鄰接表...我不知道單個操作的持續時間。問題更多地是關於這些節點和邊緣的bfs的時間複雜度。 – Hypnotic 2013-03-10 22:15:34

BFS的時間複雜度爲O（n），其中n爲10.000，在最壞的情況下，您必須訪問每個節點才能找到路徑。 – Luca 2013-03-10 22:23:38

空間複雜

所以，你有10個節點，每個節點可以連接多達其他4個節點。頂點的最大數量是40 000.在adjency list它需要O(|V|+|E|)=50 000內存空間。每個變量需要32位來表示它在列表中。最大內存量將是40000*32/(1000*1000*8)=0.16兆字節。如果使用adjacent matrix，則需要O(|V|^2)=40000*40000/(1000*1000*8)=200兆字節。

時間複雜度

百科：

的時間複雜度可以表示爲O（| V | + | E |），因爲每個頂點和每一個邊緣將在最壞的探討案件。注意：O（| E |）可能會在O（| V |）和O（| V |^2）之間變化，具體取決於輸入圖表的稀疏程度（假定圖形已連接）。

因此，在最壞的情況下，時間複雜度將是O(|V|+|E|) = 40 000 + 10 000 = 50 000。使用現代計算機，不會在1秒內計算出問題。

來源

2013-03-10 22:41:26 aphex

1s is imho ok（更像現代計算機上的0.001s - 10^9操作/秒）。內存 - 您需要鄰接列表表示法array int [10000] [4] +要記住的東西關閉/已用/未看見的節點> = 10000 * 4 * 6 = 240000 = 0.24MB。所以如果我的數學沒問題的話應該沒問題。

來源

2013-03-10 22:40:49 kyticka

搜索最短路徑中的BFS性能

回答

相關問題