When searching graphs, there are two easy algorithms: breadth-first and depth-fi

Question

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).

Now, are there any advantages of one over another?

The ones I could think of:

If you expect your data to be pretty far down inside the graph, depth-first might find it earlier, as you are going down into the deeper parts of the graph very fast.

Conversely, if you expect your data to be pretty far up in the graph, breadth-first might give the result earlier.

Is there anything I have missed or does it mostly come down to personal preference?

Explanation / Answer

One scenario (other than finding the shortest path, which has already been mentioned) where you may have to choose one over the other to get a correct program would be infinite graphs:

If we consider for example a tree where each node has a finite number of children, but the height of the tree is infinite, DFS might never find the node you're looking for - it will just keep visiting the first child of every node it sees, so if the one you're looking for isn't the first child of its parent, it will never get there. BFS however is guaranteed to find it in finite time.

Similarly if we consider a tree where each node has an infinite number of children, but the tree has a finite height, BFS might not terminate. It will only visit the children of the root node and if the node you're looking for is the child of some other node, it won't be reached. In this case DFS is guaranteed to find it in finite time.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.