DFS, циклы и порядок зависимых задач

Сборка проекта состоит из шагов: сначала скачать исходники, затем сгенерировать код, затем собрать приложение. Если два шага требуют друг друга, порядок не существует. Нужно получить допустимый план либо объяснить, что зависимость образовала цикл.

Направление ребра — часть модели

Пусть u→v означает: u необходимо завершить раньше v. Топологический порядок — последовательность всех вершин, в которой каждое такое ребро направлено от более ранней позиции к более поздней. Нельзя заменить это сортировкой числовых ID: номера не кодируют зависимости.

Для рёбер 0→2,1→2,2→3 подходят 0,1,2,3 и 1,0,2,3. Единственность не обещается. Изолированные шаги тоже должны попасть в план.

DFS и три состояния

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

После завершения всех исходящих соседей вершину можно добавить в список. Перевёрнутый список завершений даёт топологический порядок, если циклов нет. Учтите глубину стека O(V): длинная цепочка может быть неудобна для рекурсивной реализации. Для неё используйте явный стек кадров или другой алгоритм.

Проверка «когда-то посещена» без состояния текущего пути ошибочно отвергнет DAG с общим потомком:0→1,0→2,1→3,2→3. Вторая встреча 3 — обычное схождение путей.

Алгоритм Кана без рекурсии

Посчитаем indegree — число входящих рёбер каждой вершины. Шаг с нулевым indegree не имеет незавершённых предварительных шагов, поэтому его можно выбрать. После выбора уменьшаем indegree его соседей; новые нули добавляем в очередь.

degree := make([]int, len(g))
for _, edges := range g {
    for _, v := range edges { degree[v]++ }
}
queue := []int{}
for v, d := range degree {
    if d == 0 { queue = append(queue, v) }
}
for head := 0; head < len(queue); head++ {
    for _, v := range g[queue[head]] {
        degree[v]--
        if degree[v] == 0 { queue = append(queue, v) }
    }
}

Если извлечено V вершин, queue содержит допустимый порядок. Если меньше, в оставшейся части есть цикл. Некоторые оставшиеся вершины могут лишь зависеть от цикла, а не принадлежать ему. Поэтому нельзя выдавать весь остаток как точный список вершин цикла.

Корректность и стоимость

Выбранная вершина не имеет входящих рёбер от ещё не выбранных, значит ни одна её предпосылка не будет нарушена. Удаление её исходящих рёбер сохраняет смысл оставшейся задачи. Если непустой ориентированный ациклический граф не имел бы вершины с нулевым indegree, последовательное движение по предшественникам неизбежно повторило бы вершину и создало цикл.

Обе версии при списке смежности имеют O(V+E) времени и O(V) рабочей памяти. Очередь Кана выбирает любой доступный шаг. Если требуется всегда минимальный ID, замените её min-heap; стоимость выбора станет логарифмической.

Самостоятельная лаборатория

Заполните Topological в exercises, запустите go test ./exercises -run TestTopological. Допишите случаи пустого графа, двух независимых цепочек, петли, неверного номера соседа и повторного ребра. Проверка должна убедиться, что каждая вершина присутствует ровно один раз, а позиция u меньше позиции v для каждого ребра.

Затем добавьте режим объяснения цикла через DFS и parent: верните конкретный замкнутый путь, а не весь остаток Кана. Практика — 60 минут.

Критерии готовности: модель направления записана; циклический вход не выдаёт частичный план как полный; общая вершина-потомок не считается циклом; независимые вершины сохранены.

Разбор

На 0→1→0 очередь пустая с самого начала, хотя V=2. На 0→1 и изолированной 2 начальные нули 0,2; ответ 0,2,1 допустим. Сравнение с единственной последовательностью 0,1,2 дало бы ложный отказ правильному решению.

Источники: Princeton: directed graphs, MIT 6.006: лекции.