An algorithm for topological sorting based on depth-first search: why do we need two tags?
-
06-11-2019 - |
Pergunta
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.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange