Question

In lecture we discussed Milgram’s 1967 experiment; he picked 300 people at random in Nebraska and asked them to send a letter to a stockbroker in Boston, by way of relaying the letter through a chain of people. The rule is that every person has to know the next person they are sending the 1 letter to on a first name basis. He found that on average each letter went through the hands of 6.4 people before reaching the stockbroker. This is where the expression ”six degrees of separation” comes from. When you tell your friend Dirk about this experiment he says he is not surprised. Dirk says that often, when he tells something to a friend, a couple of days later he hears back the same information from someone else! You decide to test whether the six degrees of separation principle can also be applied to oneself. Let’s imagine that “friendships” on Facebook are a good representation of Milgram’s rule for being on first-name terms with somebody. Assume you are given access to all of the friendship links on Facebook as a graph (where nodes are accounts, and links are “friends”). Design an algorithm to determine if there is a chain of at most 7 friends (because the average number in Milgram’s experiment was 6.4) such that Dirk is friends with both the first and the last person. You may assume that the graph is undirected. For full credit your algorithm should run in time O(m + n) (where n and m are the number of nodes and edges, respectively).

Hint: MODIFY/ USE BFS please helP!

Answer 1

What you're looking for is cycle detection in undirected graph using BFS and the only change I have to make is add a counter to keep a track of how many nodes are intermediaries.

1. Initialize the parent array as -1. It will keep track of the parents of nodes we encountered. Initially, all nodes have parents set to -1 because we don't know yet that who is who's parent(valid assumption, right?)

2. Initialize counter to 0 and visited(array to check what all nodes we have visited - standard bfs) as -1, indicating we haven't yet visited any node.

3. Create a queue for BFS. Enqueue the start node(Dirk) to it. Mark the start node(Dirk) as visited and insert it to the queue.

4. While the queue is not empty, deque a vertex from queue (call it u) and increment counter by 1. For all adjacent vertices v, check

• If v has not yet been visited - mark v as visited, increment counter by 1, enqueue v and set parent of v as u.
• else, if v has been visited, check if parent of u is not v. If that is the case, return counter and break out of the loop because it's a cycle, right?

5. Return "-1" indicating that no cycle was found, if nothing was returned from 4b.

** In your case, you should return true/break if the value of counter is at most 7. I haven't added this, because it's meant to be a general algorithm.

Running time : O(m + n)