Where it runs
1. The problem
In the last lesson you used BFS. BFS walks a graph (a set of dots joined by lines) in rings: first the start dot, then every dot one step away, then every dot two steps away. It spreads outward with a queue (a waiting line where the first one in is the first one out). Use it when you want the nearest dots first.
Depth-first search walks the same graph in another way. It does not spread in rings. You pick one path and follow it all the way to a dead end. Then you go back to the last fork and try the next branch. You still reach every dot you can; only the order is different.
You want the same two things as with BFS: reach every dot you can from the start, and do not go in circles when the lines loop back. This lesson answers one question: in what order do the dots come out when you go deep instead of wide?
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Graph problems that walk every path or must finish a whole branch before moving on. DFS goes as deep as it can, marks nodes as visited, and backs up to try the next neighbour.
The graph has no cycles, so DFS needs no visited set, and you add a node to the path on the way down and remove it on the way back.
Store each road in both directions with a flag for its real direction, DFS from 0, and count the roads that point away from 0.
DFS down the reporting tree from the head and return the longest total of inform times along any branch.
Each equation is an edge with a weight in both directions, and a DFS from one variable multiplies weights until it reaches the other.