從邊緣創建鄰接列表的複雜性？

Question

我正在創建一個算法，可以從邊緣列表中建立一個鄰接列表。

例如，如果輸入的數據是：

1 2 
1 8 
2 8 
3 5 
3 1 
4 5 
4 6 
5 2 
5 9 
6 4 
6 8 
7 4 
7 10 
8 4 
8 6 
9 4 
9 5 
10 7 
10 3 

輸出將是：

1: 8 4 6 
2: 4 6 
3: 9 2 8 
4: 2 9 8 
5: 8 4 
6: 5 4 
7: 5 6 3 
8: 5 6 4 
9: 5 6 2 
10: 4 5 1 

算法顯然是受頂點的數量限定和邊緣，使原本我想這將是O（V + E）。但我只能通過在二維數組中實現for循環來實現程序的工作，我相信這會導致O（N^2）的複雜性。

任何人都可以幫助我更好地理解？

Answer 1

這取決於您正在使用哪種數據結構將頂點存儲到相鄰頂點列表中。遍歷邊的列表當然會有時間複雜度O（e）。任何較大的時間複雜度都是從在地圖中查找頂點所需的時間以及將新項目插入頂點的相鄰頂點列表所需的時間。如果你使用的是平面陣列，那麼你可能會有O（v * e）的複雜性（對於每個邊，循環遍歷頂點列表來找到所需的頂點），但是這可以通過使用散列表或樹來改進很多數據結構，爲您提供更好的查找性能。