algorithm - 计算图的总度数

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 (out[.])

我使用此代码作为引用点来提出我自己的:

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

第二个 for block 与第一个相同，唯一的区别是数组名称。这意味着它将计算与第一个边相同的边，从而给您一个错误的结果。

在你的第二个 for 中，你需要计算另一条边，而不是同一条边:

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