Я пытаюсь изучить алгоритм Tarjan из Википедии в течение 3 часов, но я просто не могу сделать голову или хвост.: (
http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1
Почему это поддерево дерева DFS? (на самом деле DFS создает лес? o_O)
И почему v.lowlink=v.index подразумевает, что v является корнем?
Может кто-нибудь объяснить это мне/дать интуицию или мотивацию за этим алгоритмом?
Идея такова: когда вы просматриваете дерево, каждый раз, когда вы просматриваете ветку и возвращаетесь назад, вы проверяете, встретили ли вы ребро в верхнем node в дереве.
Если вы этого не сделали (if (v.lowlink = v.index)), то вы только что завершили SCC - он состоит из текущего node и всех узлов в стеке. Это точно поддерево дерева DFS, за исключением уже завершенных узлов в SCC.
Если вы это сделали, вы распространяете эту информацию на "верхние" узлы (v.lowlink := min(v.lowlink, w.lowlink)), потому что в сочетании с этим путем в дереве DFS ребро создает путь "вверх".
DFS создает лес, но вы всегда считаете одно дерево временем. SCC всегда включается в одно дерево DFS, иначе (будучи SCC) в обоих направлениях между двумя (все) деревьями будет путь, который противоречит.
просто добавление в ответ pjotr: v.lowlink - это в основном индекс самого верхнего node, который вы нашли в дереве. Имейте в виду, что вверху в этом контексте означает минимум, поскольку вы продолжаете увеличивать индексы, когда идете вниз. Теперь, после обработки всех ваших преемников, в основном три случая:
v.lowlink < v.index: Это означает, что вы нашли задний край. Обратите внимание, что у нас нет просто нашел какой-либо задний край, но тот, который указывает на node, который "выше" текущего. То, что v.lowlink < v.index подразумевает.
v.lowlink = v.index: В этом случае мы знаем, что нет заднего края, ссылающегося на что-либо выше текущего node. Возможно, это был задний край этого node (что означает, что один из ваших узлов-преемников w имеет нижнюю ссылку, такую что w.lowlink = v.lowlink = v.index). Также может быть, что был задний край, относящийся к чему-то ниже текущего node, что означает, что был уже сильно подключенный компонент ниже текущего node, который уже был распечатан. Однако текущий node определенно является корнем также сильно связанного компонента.
v.lowlink > v.index: Это на самом деле невозможно. Я просто перечисляю его ради полноты.;)
Надеюсь, что это поможет!
Некоторая интуиция об алгоритме Тарьяна:
Во время DFS, когда мы сталкиваемся с задним ребром из вершины v, мы обновляем его минимально возможного предка, то есть обновляем значение low [v]
Теперь, когда все исходящие ребра вершины обрабатываются, то есть мы собираемся выйти из вызова DFS для вершины v, мы проверим значение low [v], независимо от того, низкий ли [v] == v (Объяснение ниже). Если это не означает, что v не является корнем SCC, и теперь мы даем преимущество родительскому элементу v, то есть самый низкий достижимый предок родителя [v] теперь изменен на низкий [v].
Это звучит логично, как если бы не было прямого заднего края от родительского [v] до предка v, но есть путь (задний край v + edge к v), через который родительский [v] может все еще достигают предка v. Таким образом, мы также обновили низкую [parent [v]] здесь. Поэтому мы будем продолжать обновлять эту цепочку, а низкий [v] для всех v будет продолжать обновляться до тех пор, пока мы не достигнем предка (с помощью обратного отслеживания). Для этого предка low [v] будет равен v. И таким образом это будет действовать как корень SCC.
Надеюсь, что это поможет