подсчет общих степеней графа

Question

В ориентированном графе общая степень узла - это количество ребер, входящих в него, плюс количество ребер, выходящих из него. Дайте алгоритм линейного времени, который принимает в качестве входного ориентированного графа (в формате списка смежности, как всегда), и вычисляет общую степень каждого узла. Вывод алгоритма должен быть массивом total [.], С записью для каждого узла.

это мой псевдо-код для этой проблемы:

procedure total degree(G) 
Input: Directed graph G=(V,E) 
Output: array total[.] with an entry for each node 

for all u in V in[u]=0 
for all u in V:  
    for all (u,v) in E: 
     in[v]=in[v]+1 

for all u in V out[u]=0 
for all u in V: 
    for all (u,v) in E: 
     out[u]=out[u]+1 

for all u in V total[u]=0 
for all u in V: 
    total[u]=in[v]+out[u] 
return total[u] 

может кто-то согласен я сделал это правильно или сказать мне, что я должен исправить, если я сделал ошибку, что им на самом деле не знаете о том, если я сделал outdegrees ([.] из) право

я использовал этот код в качестве опорной точки, чтобы придумать мой собственный:

function sources(G) 
Input: Directed graph G = (V;E) 
Output: A list of G's source nodes 
for all u in V : in[u] = 0 
for all u in V : 
    for all edges (u,w) in E: 
     in[w] = in[w] + 1 
L = empty linked list 
for all u in V : 
    if in[u] is 0: add u to L 
return L 

Answer 1

Ваш второй для блока такой же, как и первый, единственный разность b eing имя массива. Это означает, что он будет считать те же края, что и первый, что дает неверный результат.

В вашей секунду, вам нужно подсчитать другого края, а не то же самое одно:

for all u in V out[u]=0 
for all u in V: 
    for all (u,v) in E: 
     out[v]=out[v]+1 

---

В качестве альтернативы, можно пересчитать их все на одном дыхании:

Предполагая, что вход G=(V,E) представляет собой список узлов (V) и список ребер (E), представленных парами узлов ((u, v)), и при условии, что дубликаты должны подсчитываться, все, что вам нужно сделать, - это подсчет узлов (оба и в) в списке краев.

for all u in V 
    total[u] = 0 

for all (u, v) in E 
    total[u] = total[u] + 1 
    total[v] = total[v] + 1 

return total