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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ In graph theory these "groups" are called connected components. $\endgroup$ – Albjenow Dec 4 '19 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$ – Aaron Rotenberg Dec 4 '19 at 17:19
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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