Print in-degree and the out-degree of every vertex

Question

I am struggling with this algoritm question:

How would I write a theta(m+n) algorithm that prints the in-degree and the out-degree of every vertex in an m-edge, n-vertex directed graph where the directed graph is represented using adjacency lists.

This sounds like a homework question. My hint: try modifying a BFS tree generating algorithm. Specifically, how you handle already found edges for each node. — imallett
A BFS tree would not work unless you know all the vertices v such as in_degree(v) = 0. — didierc
And btw OP wants an algorithm that uses adjacency lists, i think BFS uses adjacency matrices (if i am not wrong)? — Sumit Gera

Realz Slaw Realz Slaw · Accepted Answer · 2012-09-19T18:01:01

Note: For brevity I am using "O" in place of theta.

No need for BFS.

In the case where your adjacency lists consist of a list of directed edges, maintain two vertex-count mappings, one for in-degrees, and one for out-degrees. Each vertex should be initially mapped to zero. Then iterate through each edge, u,v and increment out-degree(u) and in-degree(v). After iterating through all the edges, you can iterate through each vertex, and print its result from the mapping. Iterating through each edge is O(m), iterating through each vertex (once to initialize the mapping, and once to actually print them), is O(n). Their sum is O(m+n).

Example codes:

#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]

You can use any associative map for the vertex-count mappings. If you use a hashmap, you will get amortized constant time operations, and it will have no bearing on the overall algorithm's complexity. However, if you know that the vertices are in a range with no gaps, such as [1,n], then you can use an array of counts, with the index representing the vertex that has its value. So:

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.

This plainly gives you constant time mapping operations.

Print in-degree and the out-degree of every vertex

2 Answers