Por que o tsort não reporta nenhum loop neste exemplo?

Question

Como o tsort encontra a ordem nos exemplos a seguir?

Por que o tsort não reporta nenhum loop neste exemplo,

$ tsort <<EOF
a b c d c b a b
EOF

a
c
b
d

enquanto isso acontece neste? Obrigado.

$ tsort <<EOF
a b c d d c b a
EOF

tsort: -: input contains a loop:
tsort: a
tsort: b
a
b
tsort: -: input contains a loop:
tsort: c
tsort: d
c
d

    

Answer 1

Não há loop na sua primeira entrada. Vamos dividir:

a b c d c b a b

Ou, colocando em pares:

• a < b
• c < d
• c < b
• a < b (este especificado duas vezes!)

Então você tem que ambos "a" e "c" vêm antes de "b" e que "c" também vem antes de "d". Mas não há loops lá!

No seu segundo exemplo, o que você tem são dois loops diretos, ambos com < b, b < um (loop!) e também c < d, d < c (loop!)

Colocá-los em um gráfico para visualização (você pode querer olhar para o programa dot ) pode ajudá-lo a visualizar esses loops facilmente!