Depth first vs Breadth first search

Question 1

What is a common use of breadth first search?

Answer 1

To find the path containing the least number of nodes between two points in an unweighted graph

Question 2

How does a breadth first search work?

Answer 2

The algorithm starts searching at a designated start node and searches through all the adjacent nodes (neighbours) before moving on.

Uses a queue as a supporting data structure to keep track of the nodes that have not been fully explored.

Question 3

What is a common use of depth first search?

Answer 3

Navigating a maze

Question 4

How does a depth first search work?

Answer 4

Begins at the start node and then searches as far as possible down a branch of the graph until there are no more nodes along the current branch to be explored. If the target node is found along the way, the search can stop. Otherwise, the algorithm must backtrack and find another branch to explore.

uses a stack as each newly discovered node is inspected immediately and route can be stepped through in reverse to find a new path.

Question 5

Difference between depth first and breadth first search?

Answer 5

. In a depth-first search, a ​branch​ is​ fully explored ​before backtracking, whereas in a breadth-first search a ​node​ is fully explored​ before venturing on to the next node.