Классификация рёбер и поиск цикла

Если ты различаешь четыре вида рёбер по цвету и временам, знаешь критерий цикла через обратное ребро и помнишь, почему visited вместо серого цвета даёт ложные срабатывания, листай до «Теперь сам».

Как думаешь, всякое ли повторное ребро - цикл

Ориентированный граф: a→b, a→c, b→c. Запусти обход из a: идём в b, из b в c, возвращаемся, потом из a смотрим ребро a→c - а вершина c уже посещена. Прежде чем читать дальше, ответь: цикл ли это? И чем этот случай отличается от треугольника a→b, b→c, c→a, где цикл есть?

На что это похоже

Осмотр здания с журналом из прошлого урока. Ты идёшь по коридору и видишь дверь в комнату, где уже горит свет. Два разных случая. Первый: это комната, из которой ты СЕЙЧАС пришёл, она открыта и стоит на твоём пути - значит коридоры замыкаются в кольцо. Второй: это комната, которую ты осмотрел час назад и закрыл за собой, - никакого кольца, просто к ней ведут две дороги. Отличить одно от другого можно, только помня, какие двери у тебя ЗА СПИНОЙ ещё открыты.

Механизм: четыре вида рёбер

смотрим ребро u → v, вершина u сейчас СЕРАЯ

v белая   → ДРЕВЕСНОЕ ребро: по нему спускаемся, оно входит в дерево обхода
v серая   → ОБРАТНОЕ ребро: v на текущем пути, значит есть ЦИКЛ u → ... → v → ... → u
v чёрная  → уже закончена, спускаться некуда; два подслучая:
            tin[u] < tin[v]  → ПРЯМОЕ: v - потомок u, до которого дошли раньше другим путём
            tin[u] > tin[v]  → ПЕРЕКРЁСТНОЕ: v в ранее законченной ветви

Поиск цикла в ориентированном графе:

color = [0] * V          # 0 белая, 1 серая, 2 чёрная

def dfs(v):
    color[v] = 1
    for u in adj[v]:
        if color[u] == 1:
            return True          # обратное ребро - цикл найден
        if color[u] == 0 and dfs(u):
            return True
    color[v] = 2
    return False

В НЕОРИЕНТИРОВАННОМ графе всё проще: прямых и перекрёстных рёбер там не бывает вовсе (почему - разберём ниже), остаются древесные и обратные. Но появляется своя тонкость: ребро назад в родителя - не цикл, а то же самое ребро, по которому пришли. Его пропускают:

def dfs(v, parent):
    color[v] = 1
    for u in adj[v]:
        if u == parent:          # осторожно: при КРАТНЫХ рёбрах так нельзя,
            continue             # надо пропускать конкретное ребро, а не вершину
        if color[u] == 1:
            return True
        if color[u] == 0 and dfs(u, v):
            return True
    color[v] = 2
    return False

Правило

Ребро u → v классифицируется по цвету v: белая - древесное, СЕРАЯ - обратное (цикл), чёрная - прямое (tin[u] < tin[v]) или перекрёстное (tin[u] > tin[v]). Ориентированный граф ацикличен тогда и только тогда, когда обход не нашёл ни одного обратного ребра. Проверять цикл по visited НЕЛЬЗЯ: чёрная вершина - это не цикл. В неориентированном графе бывают только древесные и обратные рёбра, а ребро в родителя пропускают (при кратных рёбрах - по номеру ребра, а не по номеру вершины).

Разбор: классифицируем рёбра

Граф: a→b, b→c, c→a, a→c, d→b. Обход стартует из a, потом внешний цикл дойдёт до d.

вход a (серая, tin=0)
  ребро a→b: b белая  → ДРЕВЕСНОЕ, идём
    вход b (серая, tin=1)
      ребро b→c: c белая → ДРЕВЕСНОЕ, идём
        вход c (серая, tin=2)
          ребро c→a: a СЕРАЯ → ОБРАТНОЕ ← цикл a→b→c→a
        выход c (чёрная, tout=3)
    выход b (чёрная, tout=4)
  ребро a→c: c ЧЁРНАЯ, tin[a]=0 < tin[c]=2 → ПРЯМОЕ
выход a (чёрная, tout=5)

внешний цикл: вход d (серая, tin=6)
  ребро d→b: b ЧЁРНАЯ, tin[d]=6 > tin[b]=1 → ПЕРЕКРЁСТНОЕ
выход d (tout=7)

Все четыре вида в одном примере. Обрати внимание на два «повторных» ребра: a→c и d→b ведут в уже посещённые вершины, но ни одно из них не даёт цикла - в обоих случаях вершина ЧЁРНАЯ, её обход давно закончен, и вернуться из неё в текущий путь нельзя. Цикл дало только c→a: единица в момент просмотра была серой.

Разбор: почему в неориентированном графе нет перекрёстных рёбер

Пусть в неориентированном графе есть ребро {u, v}, и пусть обход вошёл в u раньше, чем в v (tin[u] < tin[v]). Докажем, что v обязательно окажется потомком u в дереве обхода - а значит ребро будет либо древесным, либо обратным, и на перекрёстное места не остаётся.

Когда мы стоим в u, ребро {u, v} лежит в списке соседей u, и мы его обязательно просмотрим до выхода из u. В этот момент v либо ещё белая, либо уже серая, либо уже чёрная - разберём все три случая.

Белая. Мы прямо по этому ребру и спустимся: оно древесное, v - потомок u.

Серая. Невозможно: серые вершины - это те, что лежат на пути от корня к u, то есть вошли РАНЬШЕ u. А мы предположили tin[u] < tin[v].

Чёрная. Значит v уже вошла и вышла. Вошла она позже u (по предположению) и притом до того, как мы дошли до этого ребра, - то есть внутри вызова dfs(u), ведь u всё ещё серая. По теореме о скобках отрезки u и v либо вложены, либо не пересекаются; не пересекаться они не могут - вход в v случился внутри отрезка u. Остаётся вложенность, а при tin[u] < tin[v] вложен отрезок v, то есть v - потомок u, и ребро обратное (смотрим мы его со стороны предка).

Практический смысл: в неориентированном графе достаточно ДВУХ видов рёбер, и любое ребро в посещённую вершину (кроме ребра в родителя) - обратное, то есть цикл. Именно поэтому проверка «есть ли цикл в неориентированном графе» такая короткая, а вот в ориентированном она требует цветов.

Что ломается без этого

Первое, самое частое: искать цикл в ориентированном графе по visited вместо трёх цветов. На графе a→b, a→c, b→c такой код объявит цикл (при просмотре a→c вершина c уже посещена), хотя циклов нет вовсе. Ошибка живучая: на многих тестах она даёт верный ответ, потому что цикл там действительно есть. Второе: забыть вернуть вершину в чёрный цвет - точнее, красить её чёрной ДО перебора соседей; тогда настоящие циклы перестанут находиться. Третье: в неориентированном графе пропускать родителя по номеру ВЕРШИНЫ при кратных рёбрах: два ребра между u и v - это настоящий цикл длины два, но код его не заметит, потому что примет второе ребро за ребро в родителя; правильный способ - помнить номер ребра, по которому пришли. Четвёртое: считать, что петля (v→v) обнаружится сама - она даёт обратное ребро и обнаружится, но при пропуске родителя её легко случайно отсечь. Пятое: путать «есть цикл» и «граф не дерево»: у неориентированного графа без циклов может быть несколько компонент (это лес, а не дерево).

Зачем это в работе

Поиск цикла - едва ли не самая частая графовая задача в прикладном коде. Зависимости пакетов, модулей, сборочных целей: цикл означает, что собрать нельзя, и хорошая система обязана назвать участников цикла, а не упасть по глубине рекурсии. Взаимные блокировки в базе данных - это цикл в графе «транзакция ждёт транзакцию», и детектор дедлоков ищет его именно обратным ребром. Циклы в схемах данных (внешние ключи), в конфигурации (включения файлов), в электронных таблицах (формула ссылается сама на себя), в наследовании классов и миксинов - всюду один и тот же алгоритм. Классификация рёбер нужна и сама по себе: компиляторы по обратным рёбрам графа потока управления находят ЦИКЛЫ в программе - те самые for и while, которые надо оптимизировать; это называется анализом естественных циклов.

Теперь сам

Ориентированный граф: 1→2, 2→3, 3→1, 4→1, 4→3. Обход стартует из вершины 1, затем внешний цикл доходит до остальных; соседи по возрастанию. Классифицируй каждое ребро и скажи, сколько в графе циклов.