DSA Notes

Graphs

DFS

Go as deep as possible, then back up.

The idea

A graph is a set of vertices joined by edges: cities and roads, people and friendships, cells of a grid and their neighbours. Edges can be one-way (directed) or two-way, and are stored as an adjacency list: for each vertex, the list of its neighbours.

Depth-first search starts at a vertex, marks it visited, and recurses into each unvisited neighbour. It reaches everything connected to the start in O(V + E).

One DFS per unvisited vertex counts connected components. DFS is also the base of topological sorting, bridge finding and strongly connected components.

Sample problem

200. Number of Islands ↗ Medium

A grid contains land (1) and water (0). An island is a group of land cells connected horizontally or vertically. Count the islands.

grid = 11000
       11000
       00100
       00011
output = 3

Why the solution works

Think of the grid as a graph: every land cell is a vertex, and neighbouring land cells share an edge. An island is a connected component.

A depth-first search from one land cell reaches exactly the cells of its island. Marking them as visited means none of them can start another search.

So the number of islands is the number of times the outer scan finds unvisited land and has to launch a new DFS.

Complexity: O(R · C) time. The recursion can go as deep as the number of cells.

Watch out

  • For an undirected graph add each edge in both directions.
  • Mark a vertex before recursing from it, or cycles cause infinite recursion.
  • Recursion a million levels deep can overflow the stack: use an explicit stack for very long paths.
Watch it run

Practise on LeetCode