CODEWITHSUNDEEP
time-complexitydepth-first-searchbreadth-first-search
glera
glera

Reputation: 43

Breadth first or Depth first

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.

Upvotes: 1

Views: 453

Answers (2)

William Prigol Lopes
William Prigol Lopes

Reputation: 1889

I believe that you can use the the Dijkstra algorithm.

Is a BFS approach that updates your path, is the path have a smaller value. Think as distance have always a cost of 1 and, if you have two friends (A and B) for a person N.

Those friends have a common friend C but, in a first time your algorithm checks a distance for friend A with cost 4 and mark as visited, they can't check the friend B that maybe have a distance of 3. The Dijkstra will help you doing checking this.

The Dijkstra solve this in O(|V|+|E|log|V)

See more at https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Upvotes: 0

jvd
jvd

Reputation: 774

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.

Upvotes: 2

Related Questions