Алгоритм сильносвязанных компонентов Тарьяна - зачем индексом в заднем крае?

Question

Я изучаю Tarjan's algorithm for strongly-connected components и способ, которым это работает, ясен для меня. Во всяком случае, есть линия, которую я не понимаю:

// Consider successors of v 
for each (v, w) in E do 
    if (w.index is undefined) then 
    // Successor w has not yet been visited; recurse on it 
    strongconnect(w) 
    v.lowlink := min(v.lowlink, w.lowlink) 
    else if (w.onStack) then 
    // Successor w is in stack S and hence in the current SCC 
    v.lowlink := min(v.lowlink, w.index) // ************* 
    end if 
end for 

Я обозначил строку звездочками. Почему мы должны взять на себя открытие индекса/время узла при столкновении с задней кромкой-

v.lowlink := min(v.lowlink, w.index) 

, а не просто захват его компонентами значения?

v.lowlink := min(v.lowlink, w.lowlink) 

Я не могу придумать случай, когда это будет проблемой.

Может кто-нибудь просветить меня, пожалуйста? Редактировать: I Подозреваемый Это только семантическое требование, то есть низкая ссылка определяется как самый ранний предок, доступный от узла с только одним обратным, но это всего лишь дикая догадка.

Answer 1

Проверка правильности проходит, если w.lowlink - это, по меньшей мере, самый низкий индекс, достижимый от w и не более низкий индекс, достижимый от w, используя не более одного заднего края. Обнаружение компонентов просто требует от нас знать, можем ли мы «убежать» на более низкий индекс.

Возможно, причина в том, что он представлен таким образом, что можно представить, что lowlink устанавливается только в пост-порядке, а затем ваш вариант не будет определен. (Псевдокод Wikipedia инициализирует его в предварительном порядке до index.)