# How to divide a graph into connected components?

Suppose I have some edges:

edges = {1 -> 2, 2 -> 3, 3 -> 1, 4 -> 5, 3 -> 6, 7 -> 8, 8 -> 9, 8 -> 10};


And I make a graph:

g = Graph[edges, VertexLabels -> "Name", ImagePadding -> 10]


After seeing the graph, you realize that there are three separate sub-graphs or families in it, and I want to see them separately. This is what I have done:

families = {Subgraph[g, {1, 2, 3, 6}], Subgraph[g, {4, 5}], Subgraph[g, {7, 8, 9, 10}]};
nMax = 3;
Manipulate[families[[n]], {n, 1, nMax, 1}]


I would like to know how to calculate nMax and families automatically. My real problem has thousands of edges and it is not viable to do it visually.

• Have a look at Kosaraju's algorithm I had to implement this for Coursera's algorithms class and it worked great even on huge graphs (5 million edges) Commented Apr 15, 2012 at 8:46
• @IvoFlipse Thank you for the link. Computing Leonid's answer for my 3.3 million edges took less than 4 seconds on my laptop. Commented Apr 15, 2012 at 14:47

Subgraph[g, #, VertexLabels -> "Name", ImagePadding -> 10] & /@