Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.
We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.
Breadth first search is a traversal on graphs where you traverse level by level, which means we'll get to all the shallow nodes before any "deep nodes". Can think of this as traversing the graph in a manner of reading left to right on each level. On the other hand, depth first search is a traversal on graphs where you traverse "deep nodes" before all the shallow ones. This means that you go as far down one path as possible until you hit a dead end (no neighbors are still undiscovered or you have no more neighbors). Once you hit a dead end, you backtrack/undo until you find an edge you haven't traversed yet.
The only graph operation necessary for something like DFS or BFS is getting the neighbors (or getting the out neighbors specifically in a directed graph). This operation is the fastest when using an Adjacency List, which will take $\mathcal{O}(deg(u))$ rather than the Adjacency Matrix's $\mathcal{O}(|V|)$.
Situation to use BFS over DFS:
We discussed a situation in the lecture videos today when BFS is preferable to DFS: unweighted shortest paths. If we are trying to solve the unweighted shortest path problem, BFS will explore the nodes
Situation to use DFS over BFS:
This one is a bit tricky! The only potential downside to BFS is its memory usage. BFS requires memory proportional to the perimeter sizes, while DFS requires memory proportional to the longest path. There are certain graphs (one explained below) where the perimeters can be much larger than the longest path. In some sense, if you don't care about finding something "nearby" (like the shortest unweighted path), you might want to consider DFS for that context.
In some sense, the worst case example of a graph for BFS is something like a binary tree (or in generally, an $M$-ary tree). Consider a binary tree of height $k$. This tree will have a total of $2^{k+1} - 1$ nodes, and each layer will have $2^i$ nodes in it. This means each perimeter of the BFS will require an exponentially more number of nodes (first 1, then 2, then 4, then 8, etc.). On the same graph using DFS, the Stack of nodes will never exceed $k$ long since that is the length of the longest path in the graph.
Seattle → Any of [SF, Salt Lake City, Chicago] → Dallas → Austin
Seattle,Chicago,SaltLakeCity,SanFrancisco,Dallas,Austin