Причина, по которой все DAG имеют более одного топологического порядка сортировки - PullRequest
0 голосов
/ 27 апреля 2019

Мне интересно, почему у всех направленных ациклических графов более одного топологического порядка сортировки.

Я искал в Google и сказал, что большинство из них просто из-за того, что у них есть хотя бы одна топографическая сортировка. Но я думаю о том, как реализован односвязный список:

A -> B -> C -> D

Это может означать, что технически может пройти только один путь toposort - D, C, B, A ...

Однако, возможно, это не направленный ациклический граф, но я не уверен, как опровергнуть дело, поскольку оно направлено (от A до B и т. Д.), Ациклично (циклов назад не существует ) График (это технически дерево) ..

Большое спасибо за предоставленные разъяснения!

...