Graph algorithm to calculate node degree

Question

I'm trying to implement the topological-sort algorithm for a DAG. (http://en.wikipedia.org/wiki/Topological_sorting) First step of this simple algorithm is finding nodes with zero degree, and I cannot find any way to do this without a quadratic algorithm.

My graph implementation is a simple adjacency list and the basic process is to loop through every node and for every node go through each adjacency list so the complexity will be O(|V| * |V|).

The complexity of topological-sort is O(|V| + |E|) so i think there must be a way to calculate the degree for all nodes in a linear way.

Niklas B. · Accepted Answer · 2014-03-07T00:36:55.743

2

You can maintain the indegree of all vertices while removing nodes from the graph and maintain a linked list of zero indegree nodes:

indeg[x] = indegree of node x (compute this by going through the adjacency lists)
zero = [ x in nodes | indeg[x] = 0 ]
result = []
while zero != []:
    x = zero.pop()
    result.push(x)
    for y in adj(x):
        indeg[y]--
        if indeg[y] = 0:
            zero.push(y)

That said, topological sort using DFS is conceptionally much simpler, IMHO:

result = []
visited = {}
dfs(x):
    if x in visited: return
    visited.insert(x)
    for y in adj(x):
        dfs(y)
    result.push(x)
for x in V: dfs(x)
reverse(result)

edited Mar 07 '14 at 00:36

answered Mar 06 '14 at 17:44

Niklas B.

92,950
18
194
224

I think he is asking how to quickly calculate indeg() in your code. – Leo Mar 07 '14 at 00:09
@linwei: Oh, now I see what you meant by your comment. `indeg(y)` is a variable, not a function. It already has the correct value, we just need to read it. I tried to make that a bit more clear now – Niklas B. Mar 07 '14 at 00:35
I understood that. It's just that after I read OP' question now I am curious too, how could you initially get all the indeg of every nodes in linear time ? – Leo Mar 07 '14 at 00:49
1

@Linwei: Initialize `indeg[x] = 0` for all `x`. For every edge `(v,w)`, increment `indeg[w]` – Niklas B. Mar 07 '14 at 01:01
One can easily find the indeg at the time of taking input from user . Which would most likely be a loop hence linear. – jack_1729 Jan 27 '18 at 11:55

score 0 · Answer 2 · answered Feb 27 '17 at 06:05

You can achieve it in o(|v|+|e|). Follow below given steps:

Create two lists inDegree, outDegree which maintain count for in coming and out going edges for each node, initialize it to 0.
Now traverse through given adjacency list, for edge (u,v) in graph g, increase count of outdegree for u, and increment count of indegree for v.
You can traverse through adjacency list in o(v +e) , and will have indegree and outdegree for each u in o(|v|+|e|).

score 0 · Answer 3 · edited Aug 17 '17 at 22:54

0

The Complexity that you mentioned for visiting adjacency nodes is not quite correct (O(n²)), because if you think carefully, you will notice that this is more like a BFS search. So, you visit each node and each edge only once. Therefore, the complexity is O(m+n). Where, n is the number of nodes and m is the edge count.

edited Aug 17 '17 at 22:54

Sᴀᴍ Onᴇᴌᴀ

8,218
8
36
58

answered Aug 17 '17 at 22:35

Ghasem

13
4

score -1 · Answer 4 · answered Mar 06 '14 at 17:49

-1

You can also use DFS for topological sorting. You won't need additional pass to calculate in-degree after processing each node.

http://www.geeksforgeeks.org/topological-sorting/

answered Mar 06 '14 at 17:49

Delta

1
1

Graph algorithm to calculate node degree

4 Answers4