Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 16:37, 3 May 2022

Revision as of 23:38, 18 August 2022

Line 42:

'''if''' ''v''.index is undefined '''then'''

strongconnect(''v'')

'''end if'''

'''end for'''

'''function''' strongconnect(''v'')

Line 65 ⟶ 63:

''// It says w.index not w.lowlink; that is deliberate and from the original paper''

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

'''end if'''

'''end for'''

''// If v is a root node, pop the stack and generate an SCC''

Line 77 ⟶ 73:

'''while''' ''w'' ≠ ''v''

output the current strongly connected component

'''end if'''

'''end function'''

The <code>index</code> variable is the depth-first search node number counter. <code>S</code> is the node stack, which starts out empty and stores the history of nodes explored but not yet committed to a strongly connected component. Note that this is not the normal depth-first search stack, as nodes are not popped as the search returns up the tree; they are only popped when an entire strongly connected component has been found.