Чи дійсна класифікація граней DFS? - алгоритм, граф, глибина першого пошуку

DFS можна використовувати для класифікації країв до дерево, вперед, назад і хрест.

Враховуючи класифікацію ребер та кількість вершин, чи можемо ми визначити за лінійною складністю, чи є це дійсним результатом DFS? А якщо так - то як?

Наприклад, тут недійсна класифікація: (отримати таку неможливо, незалежно від обраної нами кореневої вершини та порядку відвідування дітей)

Відповіді:

Перепрошую за дещо коротку відповідь: так, і ось алгоритм. Переконайтеся, що краї дерева справді утворюють дерево. Для кожного іншого краю обчисліть найпоширенішого предка його кінцевих точок. Для передніх країв це повинен бути хвіст. Для задніх краї це має бути Для поперечних країв це не повинно бути ні тим, ні іншим.

Припускаючи, що поки що все виглядає добре,кореневі шляхи від голови та хвоста поперечного краю надходять до ДМС через різних дітей. У всіх можливих порядках DFS, що генерують дану класифікацію, дитину голови відвідують до дитини хвоста. Зберіть усі ці обмеження та переконайтеся, що немає циклу.

Я стверджую, що разом ці перевірки є надійними та повними. Повнота перевіряється шляхом лінеаризації обмежень за допомогою топологічного сортування та побудови правдоподібного порядку DFS.