Breadth first or Depth first

Question

There is a theory that says six degrees of seperations is the highest degree for people to be connected through a chain of acquaintances. (You know the Baker - Degree of seperation 1, the Baker knows someone you don't know - Degree of separation 2)

We have a list of People P, list A of corresponding acquaintances among these people, and a person x

We are trying to implement an algorithm to check if person x respects the six degrees of separations. It returns true if the distance from x to all other people in P is at most six, false otherwise.

We are tying to accomplish O(|P| + |A|) in the worst-case.

To implement this algorithm, I thought about implementing an adjacency list over an adjacency matrix to represent the Graph G with vertices P and edges A, because an Adjacency Matrix would take O(n^2) to traverse.

Now I thought about using either BFS or DFS, but I can't seem to find a reason as to why the other is more optimal for this case. I want to use BFS or DFS to store the distances from x in an array d, and then loop over the array d to look if any Degree is larger than 6.

DFS and BFS have the same Time Complexity, but Depth is better(faster?) in most cases at finding the first Degree larger than 6, whereas Breadth is better at excluding all Degrees > 6 simultaneously.

After DFS or BFS I would then loop over the array containing the distances from person x, and return true if there was no entry >6 and false when one is found.

With BFS, the degrees of separations would always be at the end of the Array, which would maybe lead to a higher time complexity?

With DFS, the degrees of separations would be randomly scattered in the Array, but the chance to have a degree of separation higher than 6 early in the search is higher.

I don't know if it makes any difference to the Time Complexity if using DFS or BFS here.

jvd jvd · Accepted Answer · 2020-06-03T16:17:32

Time complexity of BFS and DFS is exactly the same. Both methods visit all connected vertices of the graph, so in both cases you have O(V + E), where V is the number of vertices and E is the number of edges.

That being said, sometimes one algorithm can be preferred over the other precisely because the order of vertex visitation is different. For instance, if you were to evaluate a mathematical expression, DFS would be much more convenient.

In your case, BFS could be used to optimize graph traversal, because you can simply cut-off BFS at the required degree of separation level. All the people who have the required (or bigger) degree of separation would be left unmarked as visited.

The same trick would be much more convoluted to implement with DFS, because as you've astutely noticed, DFS first gets "to the bottom" of the graph, and then it goes back recursively (or via stack) up level by level.

Breadth first or Depth first

2 Answers