Направленный ациклический граф
Ориентированный ациклический граф или DAG — это ориентированный граф без ориентированных циклов. Он состоит из вершин и ребер, каждое ребро направлено от одной вершины к другой, так что эти направления никогда не образуют замкнутый цикл.
Ориентированный граф является DAG, только если он топологически упорядочен.
Что такое топологическая сортировка
Топологическая сортировка для направленного ациклического графа — это линейное упорядочение вершин таким образом, что для каждого направленного ребра u->v вершина u предшествует v в порядке. Топологическая сортировка для графа невозможна, если он не является DAG.
Для графа может быть более одной топологической сортировки. Первая вершина в топологической сортировке всегда является вершиной с нулевой степенью вхождения.
Алгоритм DFS для поиска топологической сортировки
Рассмотрим ориентированный ациклический граф.
- Инициализировать пустой стек, посещенный логический массив.
- Запустите dfs с узла. Передайте стек, посещенный массив и узел в рекурсивный метод.
dfs (узел, стек, посещено).
- Внутри рекурсивной функции dfs отметьте узел как посещенный.
- Пройдите через все непосещенные дочерние элементы узла.
- Сделайте dfs на непосещенном ребенке.
- Наконец, поместите узел в стек, если все дочерние элементы посещены.
- После завершения обхода dfs проверьте, равен ли размер стека номеру узла.
Если нет, граф не является DAG и не имеет топологического порядка.
В противном случае вытолкните все элементы из стека и сохранить их в массиве результатов. - Вернуть результирующий массив.
Сложность времени и пространства
- Мы проходим через все узлы и ребра. Таким образом, временная сложность будет O(V + E), где V = вершины или узлы, E = ребра.
- Мы используем посещаемый массив, дополнительный стек и список смежности для графа. Таким образом, сложность пространства будет O(V) + O(V) + O(V + E) + дополнительное пространство для стека рекурсии.
Код
Первоначально опубликовано на:
