## The Problem

Given a list of friendships, calculate the degrees of separation between each person listed and the coolest guy around Quinn

## Step 1: Data Representation

• Often the hardest part of solving any problem
• Very cruicial to the rest of your approach
• Should be well thought out
• The more problems you do, the easier this becomes

## Undirected Graphs

• We will represent the data given to us as an undirected graph
• What is a graph?
• Not your typical line or bar graph
• Graphs in math are defined as a 2-tuple (V, E)
• A set of vertices connected by a set of edges
• Each person will be a vertex in our graph and each friendship will be an edge
• Undirected just means that each edge is bidirectional (just like the friendship relation)

## Step 2: Choosing an Algorithm

• Now that we have decided on a way to represent our data, we must choose an algorithm to process it
• Since we have decided to use a graph, it would only make sense to consider graph algorithms
• Breadth first search is a commonly used algorithm for traversing graphs
• Useful for this problem because it traverses the graph in a level order manner
• It first handles the root (Quinn)
• Then moves to Quinnâ€™s direct neighbours (QDist level 1)
• Continuing down until each level has been processed

## Step 3: Implementation

• Now that we have our data structure and algorithm mapped out, we can begin implementing them

## Graph Implementation

• Most languages do not include a graph data structure in the standard library
• Thankfully they are relatively simple, and most languages do provide the tools nessesary to do so
• Generally implemented using a map
• We map verticies to a list of their corresponding adjacent verticies

## How I Did it

• Not the only way

## Breadth First Search and Cycle Detection

• Breadth first search is also relatively easy to implement
• One thing to keep in mind is that cycles may appear in the graph
• For instance:

## Breadth First Search and Cycle Detection

• To handle this we simply need to make sure we do not visit any vertex more than once
• Each time a node is visited add it to a set of visited nodes
• Do not process any node that has already been visited

## Putting it all together

• We now have a map that maps each person to their QDist value
• Basically done at this point, we just need to handle the uncool people
• Since there does not exist a path in the graph from them to Quinn, they will not appear in the visited map
• This can be solved many different ways
• You could store all the names at the very beginning and then check which do not appear in the visited map