Content deleted Content added
→Text excised from 2-satisfiability: new section |
|||
Line 16:
This description of the algorithm was included on the page on [[2SAT]], but was irrelevant there.
I'll paste it here so bits of it could be integrated into this article if required. —[[User:Oliphaunt|Oliphaunt]] ([[User talk:Oliphaunt|talk]]) 13:21, 21 August 2013 (UTC)
:Kosaraju's algorithm performs two depth first searches, but is very simple: the first search is used only to order the vertices, in the reverse of a [[postorder]] depth-first traversal. Then, the second pass of the algorithm loops through the vertices in this order, and for each vertex that has not already been assigned to a component, it performs a depth-first search of the [[transpose graph]] starting from that vertex, backtracking when the search reaches a previously assigned vertices; the unsassigned vertices reached by this search form a new component.
| |||