граф называют ориентированным если вс вершины смежные

Из вершины номер 2 нет рёбер, идущих не в черные вершины. Возвращаемся к вершине номер 4. Красим вершину номер 2 в черный цвет и кладем ее в стек.

Существует ребро из вершины номер 4 в вершину номер 2. Переходим к вершине номер 2 и красим ее в серый цвет.

Существует ребро из вершины номер 1 в вершину номер 4. Переходим к вершине номер 4 и красим ее в серый цвет.

Переходим к вершине номер 1. Красим ее в серый цвет.

Имеем бесконтурный ориентированный граф. Изначально все вершины белые, а стек пуст. Начнем обход в глубину с вершины номер 1.

Думаю будет проще рассмотреть данный алгоритм на примере:

Цвет: во время обхода в глубину используется 3 цвета. Изначально все вершины белые. Когда вершина обнаружена, красим ее в серый цвет. Когда просмотрен список всех смежных с ней вершин, красим ее в черный цвет.

Запускаем обход в глубину, и когда вершина обработана, заносим ее в стек. По окончании обхода в глубину вершины достаются из стека. Новые номера присваиваются в порядке вытаскивания из стека.

Подробнее о поиске в глубину можно почитать в .

Поиск в глубину или обход в глубину (англ. Depth-first search, сокращенно DFS) один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них.

Я остановлюсь на рассмотрении последнего, поскольку он наиболее популярен, нагляден и прост в реализации.

Метод топологической сортировки с помощью обхода в глубину

Алгоритм Демукрона

Существует несколько способов топологической сортировки из наиболее известных:

Из рисунка видно, что граф не отсортирован, так как ребро из вершины с номером 4 ведет в вершину с меньшим номером (2).

Пример ориентированного неотсортированного графа, к которому применима топологическая сортировка

Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф. В задачах подобного плана рассматриваются только конечные сети.

Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.

Топологическая сортировка (Topological sort) один из основных алгоритмов на графах, который применяется для решения множества более сложных задач.

Алгоритмы / Топологическая сортировка | Gliffer