Six Degrees

Question (LI.531)

Six degrees of separation is the theory that everyone is six or fewer connections away. Given a friendship network, find the degrees of two people, return -1 if one of them cannot be connected.

Example

I: a = 1, b = 4

1------2-----4
 \          /
  \        /
   \--3--/

O: 2

I: a = 1, b= 4

1      2-----4
             /
           /
          3

O: -1

Approach

Level order traversal. Prune the entire search if the level is greater than 6.

Code

public int sixDegrees(List<UndirectedGraphNode> graph,
                      UndirectedGraphNode person1,
                      UndirectedGraphNode person2) {
    if (person1 == person2) return 0;
    // init queue and set
    Queue<UndirectedGraphNode> queue = new LinkedList<>();
    Set<UndirectedGraphNode> visited = new HashSet<>();
    queue.offer(person1);
    visited.add(person1);
    // bfs by level
    int level = 0;
    UndirectedGraphNode current;
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        // note: i < queue.size() won't work because we offer and poll elements within that level
        for (int i = 0; i < levelSize; i++) { 
            current = queue.poll();
            if (current == person2) {
                return level;
            }
            for (UndirectedGraphNode friend : current.neighbors) {
                if (!visited.contains(friend)) {
                    queue.offer(friend);
                    visited.add(friend);
                }
            }                
        }
        level++;
        if (level > 6) break;
    }
    return -1;
}