CODEWITHSUNDEEP
algorithmgraphgraph-theoryconnected-components
user15862679
user15862679

Reputation:

Graph, Definition of strongly connected component (SCC)?

According to the definition of strongly connected component T in a directed graph G(V, E), it says that for each u,v vertices in T then there is a path connecting them together (in both direction)

My question is, suppose I found a strongly connected component, does that mean the path can always include vertices from within T and not V\T?

If not can I see a contradiction example?

Upvotes: 0

Views: 143

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59164

If by "the path" you mean every path from u to v or vice-versa, then yes, it does.

If a vertex w is on a path from u to v, then of course it can reach v. Also, v can at least reach w through u.

w can reach everything reachable by both v and u -- v, u, and w can all reach exactly the same set of vertices.

They are in the same SCC.

Perhaps the easiest way to understand the definition of an SCC is like this: If you remove all edges that aren't in cycles, then each remaining connected component is a strongly connected component. Each vertex in an SCC can reach all the other ones.

Upvotes: 1

Related Questions