多圖和鄰接表

Question

我有一個問題可以表示爲一個多圖。爲了在內部表示這個圖，我正在考慮一個矩陣。我喜歡矩陣的想法，因爲我想計算一個頂點的邊數。這將是O（n）時間，因爲我所要做的就是循環遍歷正確的列，所以時間複雜度將與圖中頂點的數量成線性關係。不過，我也在考慮空間複雜性。如果這個圖表增長，可能會有很多浪費的空間。這導致我使用鄰接列表。這可能會減少我的空間複雜性，但聽起來像我的時間複雜度增加了。如果我想確定特定頂點的邊數，我將如何表示時間複雜度？我知道這個操作首先要找到頂點，所以這個操作應該是O（n），但是我也必須掃描也可以是O（n）的邊緣列表。那麼這是否意味着我的時間複雜度爲O（n^2）？

編輯：

我想，如果我是用一個哈希表，第一操作將是O（1），這是否意味着我的操作找到邊數的頂點爲O（n）？

Answer 1

它將是O（| e |），| e |可以是O（| v | ** 2），但是您想使用鄰接列表，因爲矩陣是稀疏的，所以| e | < < | v |所以最好說O（| e |）。