Kosaraju's algorithm
E1045495
Kosaraju's algorithm is a graph traversal method used to efficiently find all strongly connected components in a directed graph.
Observed surface forms (1)
| Surface form | Occurrences |
|---|---|
| Sharir's algorithm for strongly connected components | 1 |
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
graph algorithm
ⓘ
strongly connected components algorithm ⓘ |
| alternativeName | Kosaraju–Sharir algorithm NERFINISHED ⓘ |
| assumes | graph is finite ⓘ |
| canBeUsedFor |
condensation of directed graph
ⓘ
finding strongly connected components in control-flow graphs ⓘ |
| category | algorithm design techniques ⓘ |
| complexityClass | linear-time algorithm ⓘ |
| correctnessBasedOn |
duality between graph and its transpose
ⓘ
properties of DFS finishing times ⓘ |
| domain | directed graphs ⓘ |
| field |
computer science
ⓘ
graph theory ⓘ |
| guarantees | partition of vertices into strongly connected components ⓘ |
| handles |
graphs with cycles
ⓘ
graphs with multiple strongly connected components ⓘ |
| implementationDetail |
first DFS can be done on original graph
ⓘ
second DFS is done on transposed graph ⓘ vertices processed in decreasing order of first-pass finish times ⓘ |
| input | directed graph ⓘ |
| inputConstraint | graph may be disconnected ⓘ |
| namedAfter | S. Rao Kosaraju NERFINISHED ⓘ |
| notableFeature |
conceptually simple
ⓘ
requires two full DFS traversals ⓘ |
| numberOfPasses | 2 GENERATED ⓘ |
| originallyPublishedIn | journal article by S. Rao Kosaraju ⓘ |
| output | set of strongly connected components ⓘ |
| property |
linear time in size of graph
ⓘ
two-pass DFS algorithm NERFINISHED ⓘ |
| relatedTo |
Gabow's algorithm
NERFINISHED
ⓘ
Tarjan's algorithm NERFINISHED ⓘ |
| requires |
ability to compute graph transpose
ⓘ
stack or ordering of vertices by finish time ⓘ |
| solves | strongly connected components problem ⓘ |
| spaceComplexity | O(V + E) ⓘ |
| step |
first DFS to compute finishing times
ⓘ
second DFS in order of decreasing finishing times ⓘ transpose graph ⓘ |
| taughtIn |
graph theory courses
ⓘ
undergraduate algorithms courses ⓘ |
| timeComplexity | O(V + E) ⓘ |
| usedIn |
model checking
ⓘ
network analysis ⓘ static program analysis ⓘ |
| usesTraversal | depth-first search NERFINISHED ⓘ |
| worksOn |
adjacency list representation
ⓘ
adjacency matrix representation ⓘ |
| yearProposed | 1978 ⓘ |
Referenced by (3)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Sharir's algorithm for strongly connected components