在C++中實現圖形的最佳方法？

Question

我期待實現一個常量，無序，未加權，稀疏圖（即邊不移動）。但是，我會做很多頂點交換操作，從而頂點的排序會改變。

例如，一種方法是使用unordered_sets +鄰接表結構的載體：

0: 1 2 3 
1: 0 2 
2: 0 1 
3: 0 

交換0和3：

0: 3 
1: 3 2 
2: 3 1 
3: 1 2 0 

什麼是C++最好的實現？

Answer 1

boost::graph也許。

它有幾種實現方式，您可以爲每個頂點指定多個參數。進一步的調查留給學生練習。

Answer 2

調查Boost Graph Library。它可能會滿足您的需求，但如果沒有，那麼在開始嘗試推出自己的產品之前，文檔可能是瞭解該主題的一個很好的起點。

編輯：如果您希望使用稀疏圖表，adjacency list版本可能是您首先想要查看的實現。請注意，您可以通過更改用於實現它的底層數據結構（通過模板參數）來調整boost adjacency_list圖的性能特徵。

編輯：關於您所描述的頂點交換，可能最簡單的方法是設置一個頂點類型，頂點可以保留，但其屬性可以很容易地與另一個交換。 Bundled Properties機制是實現這一點的一種方式。