有向圖的鄰接表表示

Question

給定一個有向圖的鄰接表表示，需要多長時間計算每個頂點的出度？需要多長時間計算 入度？

由於

Answer 1

兩者都是O(m + n)其中m是邊緣的數量和n是頂點的數量。

啓動一組計數器，每個頂點一個，一個用於進度和一個出度。

掃描邊緣。對於每個邊的外部頂點，向該頂點的出度計數器添加一個。對於每個邊的頂點，爲該頂點的入度計數器添加一個。這是O(m)的操作。

輸出每個頂點的出度和度數計數器，即O(n)。

這就是你如何得到O(m + n)。

Answer 2

計算入度和出度取m個頂點和n個邊的圖的θ（m + n）。之所以是theta（m + n）而不是O（m + n），是因爲無論圖形如何，都必須經過每個頂點m和每個邊n。

Answer 3

因爲，它是一個有向圖，只給出鄰接表。

計算出度數的時間爲θ（M + N），其中M是頂點的數量，N是指邊的數量。

對於任意節點數的計數，對於任何節點，您必須計算所有其他（其餘頂點）鄰接列表中該節點出現的次數。所以，這需要theta（MN）。

但是，如果保持大小爲M的陣列，則可以做入度在THETA（M + N）的一個額外空間存儲theta的（M）

Answer 4

out-degree每計數vertex:theta(E)

in-degree每個vertex:O(E)

E是給定廣告的鄰接列表表示調圖表

Answer 5

的邊緣的數量一個頂點u的出度等於Adj [u]的長度， ，並且Adj中所有鄰接列表的長度總和爲| E |。因此，計算每個頂點的出度的時間是Θ（| V | + | E |）。

頂點的入度等於它在Adj中所有列表中出現的次數。如果我們搜索每個頂點的所有列表，則計算每個頂點的入度的時間爲Θ（| V |。| E |）。 （或者，我們可以分配一個大小爲| V |的數組T並將其條目初始化爲零，然後我們只需要掃描列表 Adj一次，當我們在列表中看到u時遞增T [u] T中的值將是每個頂點的入度，這可以用Θ（| V | + | E |）時間完成，其中Θ（| V |）爲額外存儲。有向圖的）

Answer 6

鄰接列表表示：

出度的每個頂點的

1. 格拉夫出度頂點的u是等於調[u的長度]。

2. 中調的所有鄰接表的長度之和是| E |。

3. 因此計算出度的每個頂點的時間爲Θ（V + E）

在度每個頂點

1. 的的入度頂點u的數量等於它在Adj中所有列表中出現的次數。

2. 如果我們搜索所有的列表爲每個頂點，時間來計算在度每個頂點的是Θ（VE）

3. 可替代地，我們可以分配一個數組大小的T | V |並將其條目初始化爲零。

4. 我們只需要掃描調名單一次，遞增T [C]當我們看到「U」在列表中。

5. 在T中的值將是中度的每個頂點的。

6. 這可以在Θ（V + E）來完成時間Θ（V）額外的存儲。