[討論] 演算法課的 Adjacency List

[LeoSW (易─雪)]

大家好

因為對於Adjacency List的部份有點不太了解

所以想請問一下各位

在老師的投影片裡面

有關Adjacency List 來表示Graph的Data Structure裡面

其中：

Insertion 需要 O(1) 的時間

Deletion 需要 O(1) 的時間

Query 需要 O(deg) 的時間



Query 需要 O(deg) 這個可以理解

只要將某一個List Linear Search 即可



Insertion 需要 O(1) 如果只是往後接那就是O(1)的時間內可以完成



可是Deletion 可以在O(1)的時間以內做完

是怎麼處理的呢？



有請教大家了

謝謝囉~

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.30.43
推 gglk:好像有聽到老師說: 如果我們知道要刪的對象是被哪個POINTER
→ gglk:指到，就是O(1)，否則可能還需要搜一遍，也就是O(n)
→ gglk:有錯請原諒
推 angela7736:聽到跟樓上一樣的話
→ LeoSW:如果還要搜尋應該是O(deg)吧？
推 gglk:謝謝 O(deg)
→ LeoSW:感謝兩位解答~