Алгоритмы. Топологическая сортировка методом DFS

На входе  бесконтурный орграф (если есть контуры то привет тебе товарищ, не сработает в чистом виде этот алгоритм).

На выходе нужно получить упорядоченный список вершин графа.

Для простоты зададим граф матрицей смежности…

Берем за основу DFS и при каждом проходе добавляем пройденную вершину в наш список. Полученная последовательность и будет результатом сортировки.

Примерный код….

Процедура рандомного заполнения массива

Инициализация

Рекурсивная процедура обхода в глубину для 1 узла

Полный проход методом DFS для всех узлов

 

 

 

This entry was posted in Delphi. Bookmark the permalink.