5
$\begingroup$

Wikipedia says:

The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e., a leaf node)

Consider this graph:

an example graph

If I start from the node A, then my DFS goes to C, then the order A, C, ... is created. But next I go to the node B and it gets wrong order A, C, B.

What do I misunderstand?

$\endgroup$
1
  • $\begingroup$ Is it an error in Wikipedia? $\endgroup$
    – porton
    Commented Apr 25 at 19:34

1 Answer 1

10
$\begingroup$

Main misunderstanding is when nodes are added to the answer - you add them when you leave them, right before/at backtracking

So you check A, check C, find that C is terminal - so you add C at the end of the answer

_ , _ , C

Then you roll back to A, check next child - B. Realise B only goes to an already visited node C, so it's "terminal" - add B to the latest available slot in the answer

_ , B , C

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.