# Which Graph Algorithm should I use to find all possible groups in a graph?

I have the following situation:

(Alex, Bob)

(Alex, Charlie)

(Debra, Erika)

Imagine that each row in the list represents a friendship. Alex is friends with Bob. Alex is friends with Charlie. And Debra is friends with Erika.

I would like to figure out how many independent friends groups there are. So if someone is a friend of a friend (or a friend of a friend to the nth degree), they would belog to the same group. In other words how many groups are there, that do not overlap eachother.

From the list above I would expect 2 groups:

(Alex, Bob, Charlie)

(Debra, Erika)

Which algorithm should I use to calculate these groups, from the list provided above?

Note: In the actual case the number of friendships is in the tens of millions, so I am looking for the most efficient solution.

• In graph theory these "groups" are called connected components. Commented Dec 4, 2019 at 15:58
• @Albjenow I was thinking from the title that this would be a question about finding all the subgraphs that are valid Cayley graphs, or all the automorphisms of a graph. But, alas. Commented Dec 4, 2019 at 17:19