打印度和

Question

我這個algoritm問題掙扎的每個頂點的出度：

我怎麼會寫theta(m+n)算法打印在度，並在每個頂點的出度m-邊，n-vertex有向圖，其中有向圖用鄰接表來表示。

Answer 1

爲每個節點維護一個散列表並將其初始化爲零。做BFS的時候，當你碰到一個與當前頂點增量值相鄰的頂點（即正被命中）的哈希表中的一個頂點時，一個頂點的入度就是頂點的頂點度。對於頂級度來說，做同樣的事情（也就是說，當你有節點連接到它時，它的值增加1並迭代（BFS））。

Answer 2

注：爲簡潔起見，我用「O」代替theta。

不需要BFS。

如果鄰接表中包含一個有向邊的列表，則維護兩個頂點數映射，一個用於in-degrees，另一個用於out-degrees。每個頂點應該初始映射爲零。然後遍歷每個邊，u,v並增加out-degree（u）和in-degree（v）。迭代遍歷所有邊後，可以遍歷每個頂點，並從映射中打印結果。迭代遍歷每個邊是O（m），遍歷每個頂點（一次初始化映射，一次實際打印它們）是O（n）。他們的總和是O（m + n）。

示例代碼：

#python-ish, untested 

V = set([1,2,3,4,5]) 
#{(u,v} 
E = set([(1,2),(1,3),(2,3)]) 

in_degree_count = {} 
out_degree_count = {} 

#initialize the mappings to 0 
#O(n) 
for u in V: 
    in_degree_count[u] = 0 
    out_degree_count[u] = 0 

#iterate through each edge, incrementing the respective mappings for u,v 
#O(m) 
for u,v in E: 
    out_degree_count[u] += 1 
    in_degree_count[v] += 1 

#iterate through each vertex to print them 
#O(n) 
for u in V: 
    print 'out_degree({0}):'.format(u), out_degree_count[u] 
    print 'in_degree({0}):'.format(u), in_degree_count[u] 

可以使用了頂點計數映射關係的關聯圖。如果你使用hashmap，你會得到一個分攤的恆定時間操作，並且它不會影響整個算法的複雜性。但是，如果您知道頂點處於沒有間隙的範圍內，例如[1，n]，則可以使用計數數組，其索引代表具有其值的頂點。所以：

in_degrees = [0] * (n + 1) #array/list of zeros, of size n, 
          # index 0 is disregarded since there is no vertex named 0 
in_degree[1] = 0 # will mean that vertex `1` has an in-degree of zero. 
etc. 

這顯然是給你一定的時間映射操作。