CODEWITHSUNDEEP
algorithmgraphpseudocode
notamathwiz
notamathwiz

Reputation: 235

counting total degrees of a graph

In a directed graph, the total degree of a node is the number of edges going into it plus the number of edges going out of it. Give a linear-time algorithm that takes as input a directed graph (in adjacency list format, as always), and computes the total degree of every node. The output of the algorithm should be an array total[.], with an entry for each node.

this is my pseudo-code for this problem:

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]

can someone concur i did this right or tell me what i need to fix if i made a mistake, what im really unsure about is if i did the outdegrees (out[.]) right

i used this code as a reference point to come up with my own:

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

Upvotes: 1

Views: 2019

Answers (1)

neeKo
neeKo

Reputation: 4280

Your second for block is the same as the first one, the only difference being the array name. This means it's going to count the same edges as the first one, giving you a wrong result.

In your second for, you need to count the other edge, not the same one:

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

Alternatively, you could count them all in one go:

Assuming input G=(V,E) is a list of nodes (V) and a list of edges (E) represented by node pairs ((u, v)), and assuming duplicates should count, all you need to do is count the nodes (both out and in) in the edge list.

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

Upvotes: 2

Related Questions