Graph DFS and components
A graph has more than one route to the same place, so a walk can arrive where it has already been. Mark every cell the moment you enter it, and it never happens twice.
Problems worked on this page, and more to practise
- 200. Number of Islands
- 417. Pacific Atlantic Water Flow
- 329. Longest Increasing Path in a Matrix
- 733. Flood Fill
- 695. Max Area of Island
- 1020. Number of Enclaves
- 1254. Number of Closed Islands
- 130. Surrounded Regions
- 547. Number of Provinces
- 133. Clone Graph
- 797. All Paths From Source to Target
- 207. Course Schedule
- 79. Word Search
Why does a graph traversal need a visited set when a tree traversal does not?
A tree has exactly one route from the root to any node, so recursion can never arrive somewhere it has already been. A graph has several routes to the same node, and in an undirected graph every edge is a route in both directions. Without a mark, the walk steps from a cell to its neighbour and straight back, forever. The visited set is what turns the graph back into a tree: the first arrival at a node keeps it, and every later arrival is refused.
Should I mark a cell when I enter it or when I leave it?
On entry, always, on the line straight after the guards. A cell marked on entry can never be entered a second time, which is what makes the traversal linear and what makes it terminate at all. Marking on the way out is the backtracking habit, and it belongs to problems where the answer is a path rather than a set of reached nodes, such as Word Search. Use it there and nowhere else.
Why is graph DFS O(V + E)?
Each node is marked once, so the body of the walk runs once per node. Each edge is looked at once from each of its ends, so the neighbour loops cost O(E) in total across the whole run. Adding the two gives O(V + E). On a grid every cell has at most four neighbours, so adding up the neighbours of every cell gives at most 4V, and since that total counts each edge twice, E is at most 2V. V + 2V is still linear, so on a grid the whole traversal is O(rows x cols).
Can I mark cells by overwriting the input grid instead of keeping a set?
Yes, and it saves the O(V) space the set costs. Write the water value over each land cell as you enter it and the grid itself becomes the visited set. Ask the interviewer first: destroying the input is fine in some rounds and a defect in others, and asking is worth more than the saving. If the answer is no, keep the set.
How do I detect a cycle in a directed graph with DFS?
Use three states rather than two: untouched, on the current path, and finished. An edge into a node on the current path closes a cycle. An edge into a finished node is only a second way in, which is perfectly legal in a directed acyclic graph. One visited set cannot tell those two apart, so it reports a cycle on any diamond shape.