Feature #1: Friend Circles
Explore how to determine friend circles on Facebook by treating user friendships as an undirected graph. Understand how to use Depth-First Search (DFS) to find connected components in the adjacency matrix, which represent groups of directly or indirectly connected friends. This lesson guides you through implementing this algorithm efficiently, focusing on time and space complexity.
We'll cover the following...
Description
First, we need to find all the people that are in each user’s friends circle on Facebook. Your individual friend circle is defined as a group of users who are directly or indirectly friends with you. Assume there are a total of n users on Facebook. Some of them are your friends and others are not. The friendship/connection is transitive in nature. For example, if Shaw is a direct friend of Andy, and Andy is a direct friend of Noah, then Shaw is an indirect friend of Noah. Getting the total number of friend circles that exist on Facebook helps us suggest connections on Instagram for every user.
We’ll be provided with an n x n square matrix, where n is the number of users on Facebook. A cell [i,j] will hold the value 1 if user i and user j are friends. Otherwise, the cell will hold the value 0. For example, consider ...
There are two ...