在C++中使用stl實現圖形的比較

Question

要實現一個圖形我們可以使用列表向量std::vector<std::list<vertex>> 但是我已經在某處看到了如果使用像這樣的地圖std::map<vertex, std::set<vertex>>那麼我們可以做得更好。任何人都可以從內存或速度的角度弄清楚這是比第一種更好的選擇，哪種更好？

Answer 1

這裏有兩點不同之處。

std::vector<std::list<vertex>>是所謂作爲「鄰接表」，並且std::map<vertex, std::set<vertex>>被稱爲一個「鄰接組」，與添加的不同之處在於有使用map代替vector散列頂點數組的索引。我會先討論第一個區別（即list<vertex> vs set<vertex>）。

第一個實現基本上是一個鏈接列表數組，其中每個鏈表都給出了與頂點相鄰的所有頂點。第二種實現是將每個頂點映射到一組相鄰頂點的有序映射。

鄰接表的比較VS生長的鄰接設置順序：

空間：（E + V）VS（E + V）

添加邊緣：1對日誌V

檢查鄰接： （頂點度檢查）對日誌V

迭代通過一個頂點的鄰居：（頂點度檢查）與（日誌V +檢查頂點的程度）

...其中E是邊的數量，V是頂點的數量，頂點的度數是連接到它的邊的數量。 （我正在使用無向圖的語言，但對於有向圖，您可以進行類似的推理）。所以如果你有一個非常密集的圖（每個頂點有很多的邊，即高度），那麼你想使用鄰接集。

關於地圖vs矢量的使用：插入和擦除對於矢量是O（N），對於地圖是O（log N）。然而，查找對於矢量是O（1），對於地圖是O（log N）。根據你的目的，你可能會使用一個。雖然你應該注意到，當你使用一個連續的內存空間時（如向量那樣）有緩存優化等。但是我不太瞭解這個，但是還有其他答案提到它：vector or map, which one to use?