查找圖形連接中的鄰居節點算法

我正在尋找路徑問題。我有一個均勻間隔的節點的2D網格。我需要一個算法來查找每個節點的所有8個鄰居（如果它們存在的話），以便我可以找到所有鄰居連接。查找圖形連接中的鄰居節點算法

的唯一途徑，我知道如何做到這一點會是這樣的：

for each node 
for every other node 
    check position to find if it is neighboring if so add it to the nodes connection list

我擔心的是，這將是非常低效的O(n^2)和我想象有解決它的一個更好的辦法。

任何幫助將是偉大的！

來源

2012-02-01 Justin Meiners

如何表示網格？ – templatetypedef 2012-02-01 03:31:41

它只是一個數組，每個節點都有一個x和y。如果一個好方法需要一種不同的存儲節點的方式，那也可以。 – 2012-02-01 03:49:02

@templatetypedef這篇文章真的需要一個2D標籤嗎？ – 2012-02-01 04:17:59

一個簡單的選擇是將節點本身存儲在由節點的x和y座標索引的二維數組中。這樣，通過索引到數組中並查看其中的內容，您可以對存儲在位置（x，y）的節點進行O（1）隨機訪問。另外，如果你的節點稀疏，你可以考慮將節點存儲在由（x，y）位置鍵入的散列表中。這也給了O（1）對給定位置的節點的隨機訪問，並且用一個簡單的雙循環for循環可以列出所有八個鄰居。

希望這會有所幫助！

來源

2012-02-01 04:02:00 templatetypedef

x和y存儲爲浮點數，有可能浮點數從我的循環和節點位置可能會有不同的哈希值？（如果生病了，只需將其轉換爲int以保證安全） – 2012-02-01 04:06:45

如果您將它們存儲爲浮點數，則可能需要完全不同。爲什麼他們存儲爲浮動？什麼是「鄰居」？ – templatetypedef 2012-02-01 04:56:33

如果它簡化了解決方案，我可以避免浮動 – 2012-02-01 04:59:40

查找圖形連接中的鄰居節點算法

回答

相關問題