節點（頂點）應該知道圖中的鄰居嗎？

Question

我試圖在飛鏢中實現一個圖。

我想創建類節點（頂點），邊和圖。

主要思想是圖形有一個節點列表和一個邊緣列表。

後來我會在圖上實現一些搜索算法。

我想也爲每個節點（列表鄰居）添加一個鄰居列表，因此每個節點都知道它的鄰居（後續節點是準確的）。我的想法是，當節點具有此信息時，獲取一個節點的後續節點比每次算法必須檢查邊界列表時的速度快。我知道更改（刪除邊緣，節點，添加新邊緣，節點）也會花費更多，因爲我必須在兩個位置更新它們。但目前我不打算在創建圖表後過於動態。

您認爲這種方法有意義嗎？或者我的方式可能存在一些市長缺陷？

感謝您的回覆。

Answer 1

即使您在創建圖表後不改變圖表，通過對創建的圖表進行非規範化處理，使其變得更加複雜/困難。你可能會得到一些很難追查的奇怪的錯誤。當你在一兩個月後回到這段代碼時，它會變得更加混亂，因爲它在你的記憶中並不新鮮，並且不直觀。

您將不得不有一個荒謬的節點數量來實現任何性能增益，並且如果您有一個荒謬的節點數量，您會將邊緣引用的數量加倍，從而增加內存佔用量。此外，如果您正在編譯爲JavaScript，對垃圾收集器不感興趣，因爲您不需要引用更多的對象。

如果你想改善圖表的性能，我會研究可以同時運行的分離物。請記住，圖表可能會變得很複雜，所以如果你可以保持簡單，那麼保持簡單。