1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ In graph theory these "groups" are called connected components. $\endgroup$
    – Albjenow
    Commented Dec 4, 2019 at 15:58
  • $\begingroup$ @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. $\endgroup$ Commented Dec 4, 2019 at 17:19

1 Answer 1

1
$\begingroup$

These are called the connected components of the graph.

For most purposes, any graph traversal algorithm will suffice for finding the connected components. However, if you have a really big graph, see this question on Stack Overflow for practical considerations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.