# 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) –  Ivo Flipse Apr 15 '12 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. –  Gustavo Delfino Apr 15 '12 at 14:47

## 1 Answer

Here is one way:

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


The proper terminology for what you asked, as hinted by the code, is connected components of a graph. I had to convert a graph to undirected one, since connectivity in a directed graph is a stronger condition, and not what you were after here.

-