Алгоритмы Тарьяна для SCC
Я наткнулся на эту часть SCC. Я знаю, что 5,6,7 — это сильно связная компонента. Выполнение алгоритма Тарьяна для SCC, начиная с номера de 5, я получаю неудовлетворительные значения low-link на уровне 7.
Граф и дерево DFS
пусть (x,y) ->(id,low-link)
Выполняя DFS(узел 5),(5,5), я достиг узла 6(6,6). Из узла 6 у меня есть два внешних ребра, одно смежное с узлом 5, а другое смежное с узлом 7. Предположим, выбираем другое, смежное с узлом 7, (7,7). От узла 7 к узлу 6 идет только одно внешнее ребро, которое уже посещено. Поэтому я выполнил обновление с низким уровнем связи (7,7) до (7,6). Затем я возвращаюсь к узлу 6 и исследую это внешнее ребро, идущее к узлу 5. Итак, обновляю (6,6) до (6,5). Затем снова возвращаюсь к узлу 5.
По словам Тарьяна, я должен был получить (5,5),(6,5),(7,5), но я получил (5,5),(6,5),(7,6)
Где я неправ?
Так разве не обязательно, чтобы все значения нижнего звена были одинаковыми для сильно связанного компонента?
Ответы 1
Неправда, что значение low для всех узлов сильносвязного компонента должно быть одинаковым. Необходимо только, чтобы первый узел, посещаемый при обходе DFS сильно связного компонента, имел id[node] == low[node]. Любой другой узел в сильно связном компоненте должен иметь low[node] < id[node], поскольку он может достичь более раннего узла через заднее ребро.
Чтобы фактически обработать сильно связанные компоненты, мы можем поместить каждый узел в стек, когда он впервые встречается при обходе DFS. Как только мы идентифицируем первый узел сильно связного компонента, мы можем удалить все узлы из стека вплоть до этого узла, который образует сильно связный компонент.
Почему вы говорите, что «По Тарьяну я должен получить (5,5), (6,5), (7,5)»? Это неправда.