# Get suggested friends (2 solutions) – DFS and Union Find

Get suggested friends is one of a coding question in social network applications. The data structures for social network is usually a graph. In the graph, you can use depth first search(DFS) or breadth first search(BFS) to find the connections between people. Alternatively, you can also use Union find to group the people by their connections. Here we provide solutions to get suggested friends with 2 solutions: DFS and Union find.

You are in charge of designing a small, in-memory social network, with the basic functionality of adding friendship between two people via an AddFriendship function, and a GetSuggestedFriends function for a particular user in the network. The criteria is to pick someone with whom the given user has the most number of friends in common.
Start by discussing the most suitable data structure, and implement all the objects and functions.

### Solution 1: DFS

Many times, adjacent list is used to model the unweighted undirected graph. If there are connection between two people, addFriendship (ie addEdge) is called. Then you can use dfs to traverse all reachable nodes in the graph, and build the connected groups. When using dfs, apply memoization so that the time complexity is Linear O(V+E).

## Python

Output:
Suggestion friends of Zoe: [Sarah, Jess]
Suggestion friends of Sam: [Chris]

O Notation:
Time complexity: O(V+E), V is total number of people, E is number of connections
Space complexity: O(V)

### Solution 2: Union find

Union find is to use union and find methods in a data structure a disjointed set. Behind the scene, it is a forest structure. A disjoint set contains a set of elements that can be partitioned into subsets. All the elements in one subset has one root.

In this implementation, you use path compression and union by rank to optimize the tree’s depth. So that the time complexity is from O(n) to O(α(n)), α(n) is the inverse ackermann function. By finding which group the element belongs, you can find the suggested friends. Here are the implementation of suggested friends in Java, JavaScript and Python.

## Python

Output:
Friends circle of Zoe: [Zoe, Sarah, Jess, Joshua]
Friends circle of Sam: [Chris, Amy, Sam]

O Notation:
Time complexity: O(n*logn), n is total number of people
Space complexity: O(n)