Software Engineer Study Guide — Depth First Search vs. Breadth First Search

Depth First Search

• Uses a Stack data structure
• It is an edge based technique
• It performs two stages, first visited
• Might traverse through more edges to reach a destination vertex from a source
• Is more suitable when there are solutions away from the source
• Is more suitable for game or puzzle problems. We make a decision then explore all paths through this decision. And if this decision leads to win situation, we stop.
• Complexity is O(V+E) when adjacency list is used and O(V²) when Adjacency Matrix is used, where V stands for vertices and E stands for edges

Breadth First Search

• Uses Queue data structure, meaning first in first out
• It is a vertex based technique for finding a shortest path
• One vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue
• It is slower than DFS
• Can be used to find single source shortest path in an unweighted graph
• Is more suitable for searching vertices which are closer to the given source
• Considers all neighbors first and therefore not suitable for decision making trees used in games or puzzles
• Complexity is O(V+E) when Adjacency List is used and O(V²)