I have this graph. The SCCs in this Graph are {a, b, e}, {d, g}, and {c, d, h}. But the cycles in this graph are the same components, right?
So what exactly is the difference between SCCs and directed cycles? Do they only differ in specific cases?
In a directed graph G(V,E)
:
w
is reachable from a vertex v
if there exists a directed path from v
to w
.v
and w
in G
there is a directed path from v
to w
and a directed path from w
to v
.v
and w
in the strongly connected sub-graph G'(V',E')
where V' ⊂ V
and E' ⊂ E
there is a directed path from v
to w
and a directed path from w
to v
.The difference is that:
If you have the strongly connected component:
A → B
↓ ↖ ↓
C → D
Then there is a directed path C → D → A → B
and a directed path B → D → A → C
but there is no directed cycle that contains both B
and C
as the edge D → A
would have to be visited twice in the cycle.
Additionally, there is another (technical) difference that if the directed cycle visits all the vertices then it is a strongly connected directed graph and not a strongly connected component (as a component is a strict sub-graph).