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
scroll top