add_edge（v1，v2，graph） - 時間複雜度

Question

我需要建立一個圖並試圖決定如何（爲了最小的時間複雜度）。

從我的理解，有兩種流行的方式來存儲圖形的數據：adjacency_list和adjacency_matrix。

該曲線圖的聲明是（無向例如）：

typedef adjacency_list <vecS, vecS, undirectedS> UGraph; // In case of adjacency_list 

typedef adjacency_matrix<undirectedS> UGraph; // In case of adjacency_matrix 

兩種情況所使用的函數add_edge(v1,v2,UGraph)到兩個頂點之間添加一個邊緣。

所以我的問題是哪個模型會使add_edge更便宜 - 時間複雜的方式，爲什麼？

我試圖閱讀this關於時間複雜度的解釋add_edge但這個解釋是關於OutEdgeList。所以它讓我感到困惑。

add_edge哪種型號便宜，爲什麼？

Answer 1

所以我的問題是哪個數據庫會使add_edge更便宜 - 時間複雜的方式，爲什麼？

與鄰接列表相比，它更快（O（1））在矩陣中，您需要遍歷與特定頂點相連的整個列表以添加邊。