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