有效實現廣度優先算法的動態隊列

我正在構建一個廣度優先圖搜索算法，用於搜索倫敦地鐵。有效實現廣度優先算法的動態隊列

我有算法想通了，但你可能知道，算法需要爲了一個隊列廣告來追蹤所有需要搜索（以正確的順序）的邊緣。

我一直在閱讀有關管理隊列和大量或非常大量排隊項目（邊緣）的效率問題。

誰能告訴我如何實現基於圍繞Java的ArrayList隊列，可以跟蹤頭部和尾部，並且有效地管理內存，同時它的增長？

任何提示/指針非常感謝！

2011-01-06 Alex

我會問的第一件事是你真的有問題 - 是否讓你等待？第二個是如果它讓你等待你抽樣，看看它最花時間在做什麼。該FIFO可能是一個問題，但先驗，可能不是。就像猜測一樣，你應該能夠每微秒處理1個節點，所以我不認爲速度會成爲問題。 – 2011-01-06 19:03:32

我寧願使用某種專門化的隊列，因爲它比我們的隊列一直排序更麻煩。雖然這不是必需的，但我只想更多地瞭解隊列以及如何完成它們。 – Alex 2011-01-06 19:16:08

我想我不明白你爲什麼需要排序，但無論如何，@ Kim的答案看起來不錯。 – 2011-01-06 19:19:06

我認爲你的問題是密切相關的這個話題：Breadth-First search in Java

，除非你有一個真正好原因不使用ArrayList。 Java已經有很多隊列實現 - 請參閱Queue接口瞭解詳細信息。

就你而言，選擇LinkedList作爲你的隊列實現可能就足夠了。另請參見http://www.codeproject.com/KB/java/BFSDFS.aspx，其中簡單介紹了使用LinkedList作爲隊列的廣度優先搜索實現。

來源

2011-01-06 19:10:21

請記住，您將需要快速測試來查看您的對象是否已在隊列中。 ArrayList和Queue都不提供此功能（其contains檢查是O(n)）。如果您可以通過添加額外字段來修改正在處理的對象，則很容易。如果沒有，你會想保持某種快速Set（可能是HashSet）來跟蹤哪些對象在隊列中。

來源

2011-01-06 19:21:33

有效實現廣度優先算法的動態隊列

回答

相關問題