Difference between a directed cycle and a strongly connected component

Question

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?

Answer 1

In a directed graph G(V,E):

• A directed path is a sequence of vertices in which there is a directed edge pointing from each vertex in the sequence to its successor in the sequence, with no repeated edges.
• A directed cycle is a directed path (with at least one edge) whose first and last vertices are the same.
• A vertex w is reachable from a vertex v if there exists a directed path from v to w.
• A directed graph is strongly connected if every vertex is reachable from every other vertex in the graph
  • A corollary of this is that for every pair of vertices v and w in G there is a directed path from v to w and a directed path from w to v.
• A directed graph that is not strongly connected consists of a set of strongly connected components, which are maximal strongly connected sub-graphs.
  • A corollary of this is that for every pair of vertices 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:

• A directed cycle is a single directed path (where the first and last vertices are the same) and cannot have repeated edges;
• A strongly connected component is a sub-graph where there is a directed path from every vertex in the sub-graph to every other vertex in the sub-graph.

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).