У меня есть края, и я хочу построить из них дерево.
Проблема в том, что я могу построить свою древовидную структуру только тогда, когда края расположены в определенном порядке. Пример заказов:
(vertex, parent_vertex)
good: bad:
(0, ) <-top (3, 2)
(1, 0) (1, 0)
(2, 1) (3, 2)
(3, 2) (0, ) <-top
Я повторяю, выбрасывая ребра, и для текущей вершины пытаюсь найти ее родительский элемент в созданном дереве, затем я создаю узел и вставляю его.
result tree:
0 - 1 - 2 - 3
Таким образом, всегда должен существовать родительский элемент в дереве для новой добавленной вершины. Вопрос в том, как отсортировать входные края. Voices говорит мне о топологической сортировке, но это для вершин. Можно ли правильно отсортировать?