如何序列化圖表？

Question

這是一個interview question：如何序列化圖形？我看到這個answer，但我不確定這是否足夠。

它看起來像一個非常混亂的「開放式問題」，候選人可能會問更多關於需求的問題：節點和邊是什麼，它們是如何序列化的，這個圖是加權的，導向的等等。 ，圖中有多少個節點/邊。關於基礎設施的情況？這是一個純文件系統還是我們應該/可以使用數據庫？

那麼，你會如何回答這個問題？

Answer 1

我認爲你的答案provided是相當合理的。國際海事組織，基本上你需要知道應用程序的背景，我會問至少：

• 是否指示或不？
• 什麼是與頂點，邊和圖本身相關的屬性？
• 是圖稀疏（如果是這樣，那麼我們最好不要使用鄰接矩陣）？

最簡單的方法是將其存儲爲邊緣列表。 但是，在不同的應用程序中有一些經典的方法來做到這一點。 例如，如果您正在進行電路仿真，那麼圖形是稀疏的，並且生成的圖形/矩陣可以作爲列壓縮形式存儲。如果您正在解決（最小成本）最大流量問題，那麼已經有一個DIMACS格式，這樣公共解算器就可以讀取並寫入它。如果您想要人類可讀，結構化的方式也是一個不錯的選擇，XML可以提供自我驗證（已經有一個標準的GraphML）。順便說一句，dot格式是相當獨立的。

Answer 2

梅。不管你存儲什麼，它基本上都是：

輸出圖中的每個頂點。如果首先沒有所有頂點，則在重新讀入圖形時重建圖形。

現在可以存儲頂點之間的邊界。希望你的頂點有某種形式的ID，以唯一標識它們。我見過的版本是「將一個（圖|樹）存儲在數據庫中」。因此，讀入節點，存儲在散列表或類似的O（1）攤銷查詢中。然後，foreach邊緣，查找ID源和ID-dest以及鏈接。

瞧，你已經反序列化它。如果它不是一個數據庫，相同的想法通常會保持不變 - 首先序列化節點，然後是邊緣。