Topological Sort

Artikali · Post by **Artikali** » Fri Nov 17, 2006 5:59 am

I used standart Topological sort algorithm, but if node==5000 it says stack overflow, any one know how to do it without recursion.
Thanks

ayon · Post by **ayon** » Fri Nov 17, 2006 9:05 am

ya, it can be done using indegree. indegree indicates number of edges coming into u from any other vertices.

1. output and remove any node u, elements of V, such that indegree = 0.
2. decrease all indegree[v] by one, if (u,v) is an edge.
3. jump to 1 untill all node has been removed.

Note that, you will always find at least one node of indegree 0 if there exists no cycle in the graph.