Зачем нам нужно запускать DFS на дополнении графа в алгоритме Косараю?

Существует знаменитый алгоритм поиска сильно связанных компонентов, называемый Kosaraju's algorithm, который использует два DFS для решения этой проблемы, и работает в θ(|V| + |E|) время.

Сначала мы используем DFS для дополнения графа (GR) чтобы вычислить обратный порядок по вершинам, а затем мы применяем второй DFS на основной граф G беря вершины в обратном порядке, чтобы вычислить сильно связанные компоненты.

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

Как это помогает второй DFS найти сильно связанные компоненты?

Источник

3 ответа

Решение

Предположим, что результат первой DFS:

----------v1--------------v2-----------

где "-" обозначает любое число, и все вершины в сильно связной компоненте g появляются между v1 и v2.

DFS по почте дает следующую гарантию, что

  • все вершины после v2 не будут указывать на g в обратном графе (то есть вы не можете достичь этих вершин из g в графе происхождения)
  • все вершины до v1 не могут быть указаны из g в обратном графе (то есть вы не можете достичь g из этих вершин в графе происхождения)

одним словом, первая DFS гарантирует, что во второй DFS сильно подключенные компоненты, которые посещаются ранее, не могут иметь краевых точек для других невидимых сильно связанных компонентов.

Некоторое подробное объяснение

давайте упростим график следующим образом:

  • весь граф G
  • G содержит две сильно связные компоненты: одна - g, другая - одна вершина v
  • между v и g есть только одно ребро, либо от v до g, либо от g до v, имя этого ребра e
  • g', e' представляют собой обратную сторону g, e

ситуация, в которой этот алгоритм мог потерпеть неудачу, может быть заключена как

  1. начать DFS от v, и e ' указывает от v до g'
  2. запустить DFS из вершины внутри g', а e' указывает от g' до v

Для ситуации 1

График происхождения будет как g-->vи обратный график выглядит как g'<--v,

Чтобы запустить второй DFS из v, почтовый порядок, сгенерированный первым DFS, должен быть примерно таким:

g1, g2, g3, ..., v

но вы легко обнаружите, что ни запуск первой DFS из v, ни из g'не может дать вам такой почтовый заказ, поэтому в этой ситуации гарантированно будет первая DFS, что вторая DFS не будет начинаться с вершины, быть вне и указывает на сильно связанный компонент.

Для ситуации 2

аналогично ситуации 1, в ситуации 2, где начальный граф g<--v и обратное это g'-->v, гарантируется, что v будет посещено до любой вершины в g'.

Источник

  1. Когда вы запускаете DFS на графике в первый раз, для каждого посещаемого вами узла вы получаете знания обо всех узлах, которые достижимы с этого узла (вы получаете эту информацию после завершения первого DFS).

  2. Затем, когда вы инвертируете все вершины и запускаете DFS еще раз, для каждого посещаемого вами узла вы получаете знания обо всех узлах, которые могут достичь этого узла в неинвертированном графе (опять же, вы получаете эту информацию после завершения второго DFS).

Пример: допустим, ваша первая DFS достигает узла X. С этого узла "вы можете видеть" всех соседей, которых вы можете посетить. (Надеюсь, это довольно понятно). Затем, скажем, ваша вторая DFS достигает этого узла X, но на этот раз все вершины инвертированы. Если затем из вашего узла X "вы можете видеть" любые другие узлы, это означает, что до инвертирования вершин узел X был доступен из всех соседей, которые вы видите сейчас. Вызывая вторую DFS в правильном порядке, вы получаете для каждого узла X все узлы, которые достижимы из X в обоих деревьях DFS (и, таким образом, для каждого узла X вы получаете узлы, которые были оба достижимы из X и могли достичь X - это сильно связанные компоненты по определению).

Источник

Предположим, список L это DFS-посещение после заказа. u->v указывает, что существует путь пересылки из u в v,

Если u->v и не v->u, затем u должен появиться слева от v в L, Узлы в SCC, такие как v а также wОднако может появиться в любом произвольном порядке в списке L,

Imgur

Итак, если узел x появляются строго раньше y в списке L:

  • Случай 1: x->y а также y->xкак в случае с v а также w
  • Вариант 2: x->y и не y->xкак в случае с u а также v
  • case3: нет x->y и не y->x

Алгоритм Косараю перебирает L слева направо и запустите DFS, начиная с каждого узла на графе транспонирования (где направление ребер меняется на противоположное). Если какой-либо узел доступен через DFS и не принадлежит ни к одному SCC, то мы добавляем этот узел в SCC текущего корня.

В случае 1 мы добавим y в ГТК x, В случае 3, y а также x находятся в разных ГТК.

Случай 2 требует особого внимания. В то время, когда мы вызываем DFS из y, x уже в каком-то другом SCC, поэтому мы не будем добавлять x в ГТК y, Представьте себе, если вы вызывали DFS, начиная с root y до DFS, начиная с корня x, затем x будет добавлен в ГТК y, что не так.

Короче говоря, первая DFS организует те узлы, которые могут достигать y но не может быть достигнуто с y слева от него. Таким образом, вторая DFS может избежать добавления таких узлов x в ГТК y,

Источник
Другие вопросы по тегам