Java堆棧溢出錯誤 - 圖算法

Question

我正在使用一個數據結構來表示一個圖形，一個HashMap - HashMap（一個用於地點，一個用於表示目的地的地方），我插入了20 000個地點。 現在我需要做一個函數來知道兩個Localities之間是否存在路徑，這個函數是遞歸的，它需要我使得我的hashMap的很多獲取對象與它們一起工作。 對於每個目的地，我總是要執行獲取我的api的方法，給我一個目的地的hashMap的副本 每當我運行我的程序，我得到一個Stackoverflow錯誤。爲什麼這總是發生？這是由於高遞歸調用？或者是因爲經常調用get方法來獲得本地目的地的hashMap的副本？

謝謝。

Answer 1

堆棧溢出是由超過某個固定限制的遞歸深度引起的。這可能與複製HashMap無關;這會導致OutOfMemoryError。如果你正在做遞歸的圖形搜索，錯誤很可能是由兩種

1. 深度優先搜索會太深，或
2. 一個錯誤在你的遞歸的邏輯造成的。

沒有更多的數據我不能說這是什麼。但請注意，可以使用明確的堆棧迭代地編寫DFS以存儲要瀏覽的節點。發佈更多的代碼將有助於我們做出更好的診斷。

希望這會有所幫助！

Answer 2

這是遞歸調用。遞歸調用的每個級別都會消耗堆棧中的空間，因此如果您獲得大量這些調用，則將耗盡堆棧空間。改變你的算法是非遞歸的。

Answer 3

您使用哪種算法尋找最短路徑？它可以包含圓圈或負邊緣權重嗎？ 根據不同，使用Dijktra，Prim，Floyd-Warshall或任何其他。 Steven Skiena的「算法設計手冊」，p。 206ff對各種最短路徑圖算法給出了一些很好的詳細解釋。我敢肯定，其中許多是迭代的而不是遞歸的。

Answer 4

同樣的事情發生在一個更小的圖上嗎？ 如果是這樣，你的遞歸中有一些錯誤可能會導致無限遞歸。 如果不會發生較小的圖形，這是您的算法，擊倒你。

Answer 5

謝謝你的幫助，問題已經解決了。我決定忘記遞歸調用，並選擇DFS變體。