SCC
Summary
SCC algorithms
| Time Complexity | Constraint | Type of Graph ADT | |
|---|---|---|---|
| kosaraju’s algorithm | AL | ||
| tarjan’s algorithm | AL |
SCC related problems
Concept
Strong connectivity
StronglyConnected(G):
choose any vertex s
F = Reachable(G, s)
B = Reachable(reverse(G), s)
return every vertex is marked in both F and B
==>
by definition
<== for any u,v inn G
u~>s~>v and v~>s~>u
so u~>v and v~>u
Strongly connected components
- subgraphs in which every vertex is reachable from every other vertex
- 6 vertex graph
Definition
- Research mutual reachability as an equivalence relation
- Distinguish strongly connected sets from maximal SCCs
- Check treatment of isolated vertices and self-loops
can two SCCs share a vertex?
- no
- lemma - any two SCCs must be disjoint
- by contradiction
- if there is path from u to v, v to u and v to w and w to v, then there is u to w and w to u, so
is an SCC
can DAGs have SCCs?
- no
Component graph
-
is a DAG
-
proof? by contradiction
-
for every directe graph G, the component graph of G is a DAG
-
having a directed cycle among components contradicts maximality
-
Contract each SCC to one meta-vertex
-
Verify why a directed cycle among components would contradict maximality
-
Research how topological order supports downstream DAG algorithms
largest finish time by DFS always gives a vertex in a source component
take the reversal of G?
SCC partition by DFS finish times
- run DFS on G^r to get finish times
- while G != 0
- v <- vertex with largest finish time
- C <- DFS(v)
- G <- G / C
component finish time
Kosaraju
SCC(G):
run full DFS on G
order = vertices in decreasing finish time
R = reverse(G)
comp[v] = UNASSIGNED for every v
label = 0
for s in order:
if comp[s] == UNASSIGNED:
label = label + 1
DFS from s in R:
visit only UNASSIGNED vertices
assign label to every visited vertex
return comp
the DFS finish time is what gives us the post-order behaviour
Algorithms
- Compare two-pass kosaraju’s algorithm with one-pass tarjan’s algorithm
- Both run in
with adjacency lists - Track required state, recursion risks, and component output order
Research directions
- Derive the 2-SAT satisfiability criterion from implication-graph SCCs
- Explore dependency cycles and wait-for graphs
- Study source and sink SCCs in graph augmentation problems
- Check conventions for the condensation graph edge set