# An algorithm for topological sorting based on depth-first search: why do we need two tags?

Wiki gives an alternative algorithm for topological sorting is based on depth-first search, as follows:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)

function visit(node n)
if n has a permanent mark then return
if n has a temporary mark then stop   (not a DAG)
mark n with a temporary mark
for each node m with an edge from n to m do
visit(m)
remove temporary mark from n
mark n with a permanent mark
add n to head of L


I couldn't see the necessity of introducing two tags: permanent and temporary. As far as I can see, the following algorithm would work, using only one tag -- explored.

L ← Empty list that will contain the sorted nodes
while exists nodes without an explored mark do
select an unmarked node n
visit(n)

function visit(node n)
mark n as explored
for each node m with an edge from n to m do
if m is unexplored
visit(m)
if m is explored
stop(not a DAG)
add n to head of L


If it's not the case, please tell me where I went wrong within this algorithm.

## 1 Answer

Consider the following graph $$G = (V, E)$$ where $$V = \{1, 2, 3\}, E = \{(1, 3), (2, 3)\}.$$ If your example started at $$1$$, it will add $$3$$ to the list and then it will add $$1$$. In the next step the algorithm will choose $$2$$ as an unvisited vertex, which has an edge to a visited vertex $$3$$. Hence, It will conclude that the graph is not a DAG. However, the graph is a DAG and your algorithm is not always correct.

The reason why we need two kinds of marking is to distinguish cycles from components we already done in previous iterations. Reaching back to an ancestor in the recursion tree means that there is a path going back to a vertex we came from and hence a cycle. Meanwhile an edge to a vertex that is permanently marked (and hence was visited in a previous iteration) can never introduce a cycle, since else we would have reached the current vertex in the same iteration as well.