鄰接列表indegree

Question

我正在解決這個CLRS問題，它要求找出圖的每個頂點的indegree G(V,E)。我發現解決方案爲O(|E|)，因爲我們只需掃描所有邊來找出所有頂點的度數。

但我在網上找到的大多數解決方案都說它是O(|V|+|E|)。怎麼來的？頂點如何佔用時間？

Answer 1

如果我們假設圖的實現使用頂點對象，並且每個頂點都有一個關聯的後繼列表並且沒有附加的數據結構，那麼直接迭代邊將是不可能的。

如果有向圖連通，那麼每個vertext至少有一個關聯的邊。這意味着通過迭代遍歷頂點遍歷頂點需要O(|E|)時間 - 頂點迭代不會增加運行時間，這是由邊的數量決定的。

如果有向圖是而不是連接，那麼在頂點上的迭代不一定由邊的數量支配;即使是孤立的頂點也必須進行處理以發現它們沒有關聯的輸出弧，這可以在O(|V|+|E|)時間內完成。

總之，無論哪種情況，O(|V|+|E|)的運行時限都是正確的;然而，對於連接的有向圖（或允許直接在邊上迭代而不管頂點的數量如何的實現），可以獲得更加嚴格的運行時限爲O(|E|)。