如何找到一個圖的鄰居effiiciently

Question

我有如下圖所示

算法開始於綠色節點，並遍歷該圖是創建圖形的程序。假設一個節點（帶有4個引用左，右，上，下的鏈接列表類型節點）已被添加到圖像中紅點所示的圖形中。爲了將新創建的節點與其鄰居相集成，我需要找到這四個對象並將它們鏈接起來，以保持圖形連通性。

以下是我需要澄清

1. 假設所有黃色節點是空的，我不養另一個數據結構來映射節點是什麼，找到鄰居的存在，最有效的方法新創建的節點。我知道像DFS，BFS等最基本的圖形搜索算法和最短路徑算法，但我不認爲其中任何一個都足夠有效，因爲該圖可以有大約10000個節點，並執行圖搜索算法（從綠色節點開始）以找到添加新節點時的鄰居似乎在計算上花費很大。
2. 如果圖搜索是不可避免的，那麼最好的替代結構是什麼。我想到了一個大型的多維數組。但是，這具有內存浪費，並且還存在沒有負指數的問題。由於圖像中的圖形可以在任何方向上增長。我對此的解決方案是編寫一個由基於數組的數據結構組成的獨立類來描繪負向索引。但是，在採取這種選擇之前，我想知道如果我能夠解決問題而不解決新的結構並且節省大量的返工。

感謝您的任何反饋和閱讀此問題。

Answer 1

我不知道我是否正確理解你。你想

• 檢查是否有從（0,0）的路徑（X1，Y1）

或

• 檢查任何的鄰居（X1 ，y1）在圖中？ （即使沒有從（0,0）到這些鄰居的路徑）。

我假設你正在尋找一個路徑（否則你不會使用鏈表），這意味着你不能存儲沒有路徑到（0,0）的點。

此外，你提到你不想使用任何其他數據結構旁邊/而不是你的二維鏈表。

您無法避免全圖搜索。 BFS和DFS是經典算法。我不認爲你關心最短路徑 - 任何路徑都行。

您可能會考慮的另一種方法是A *（簡單解釋here）或其變體之一（請看here）。

另一種數據結構可能是一組節點（每個節點當然是一對< x，y>）。你可以很容易地運行4次檢查，看看它的任何鄰居是否已經在集合中。這將需要O（n）空間和O（檢查和添加）時間。如果您的編程語言不支持配對作爲集合的節點，則可以使用單個整數（x *（Ymax + 1）+ Y）。

Answer 2

您可以使用空間索引，如四叉樹或r-tree。

Answer 3

您的數據結構可以正常工作，但可能效率不高。這將是很多工作。

使用您當前的數據結構，您可以使用A *搜索（請參閱https://en.wikipedia.org/wiki/A * _search_algorithm獲取基本描述）來查找指向該點的路徑，該路徑必然會找到鄰居。然後假裝你在這個時候有一個小傢伙，把他的右手放在牆上，然後讓他順時針找到他的方向。當他回來時，他會發現其餘的。

順時針找到他的方式是什麼意思？例如，假設你從鄰居那裏走下來以達到他的目的。那麼你的傢伙應該面對他有鄰居的右派，左派和左派的第一個。如果他可以正確的話，他會的，然後他會嘗試向下，向右，向上和向左的方向。 （想象一下，試着用右手在牆上自己走迷宮。）

這種方式就是瘋狂。

這裏有兩個更容易處理的替代數據結構。

您可以使用四叉樹。有關說明，請參見http://en.wikipedia.org/wiki/Quadtree。通過這種插入，節點在時間上是對數的。發現鄰居也是對數的。而且你只用空間來存儲你的數據，所以即使你的圖很分散，這也是高效的。

或者，您可以創建一個類型的數組，該數組既可以使用正數也可以使用負數。然後是建立在二維類別上的積極和消極指數。該類將被作爲常規數組和偏移量來實現。所以一個數組可以從某個數字開始，正數或負數。如果您嘗試插入位於偏移量之前的數據片段，則可以在該片段下方創建一個新的偏移量，並在數組長度的固定部分創建一個新數組，並將數據從舊數據複製到新。現在插入/找到鄰居通常是O(1)，但它可能是非常浪費內存。