28  Graphs I — Representation, BFS, DFS

29 Graphs I — Representation, BFS, DFS

Week 3, Session 2. CSS 343.

29.1 Warmup

Number of Islands (#200). Given a 2D grid of ‘1’ (land) and ‘0’ (water), count distinct islands.

class Solution {
 public:
  int numIslands(vector<vector<char>>& grid) {
    int rows = grid.size(), cols = grid[0].size();
    int count = 0;
    for (int r = 0; r < rows; ++r) {
      for (int c = 0; c < cols; ++c) {
        if (grid[r][c] == '1') {
          ++count;
          dfs(grid, r, c, rows, cols);
        }
      }
    }
    return count;
  }
 private:
  void dfs(vector<vector<char>>& grid, int r, int c, int rows, int cols) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;
    grid[r][c] = '0';        // mark visited by sinking the island
    dfs(grid, r+1, c, rows, cols);
    dfs(grid, r-1, c, rows, cols);
    dfs(grid, r, c+1, rows, cols);
    dfs(grid, r, c-1, rows, cols);
  }
};

Grid is an implicit graph. Each ‘1’ is a vertex; neighbors are adjacent ‘1’ cells. DFS from every unvisited ‘1’ marks one whole island, then increment the count.

29.2 Learning objectives

1. Choose between adjacency matrix and adjacency list based on graph density.
2. Implement BFS using a queue and trace its execution.
3. Implement DFS recursively and iteratively.
4. Use BFS/DFS to identify all connected components.
5. State the time complexity of BFS and DFS in V and E.

29.3 Terminology

A graph G = (V, E) is a set of vertices and edges. Edges connect pairs of vertices.

• Directed vs. undirected: edges have direction (one-way) or not.
• Weighted vs. unweighted: edges carry a numeric weight (cost, distance).
• Connected: every pair of vertices has a path between them.
• Degree: number of edges incident to a vertex (in/out for directed).
• Cycle: a path that starts and ends at the same vertex.
• Tree: a connected undirected graph with no cycles. Or equivalently: n vertices and n-1 edges.

29.4 Representations

29.4.1 Adjacency matrix

A V×V grid where m[i][j] = 1 if there’s an edge from i to j.

vector<vector<int>> adjMat(V, vector<int>(V, 0));
adjMat[0][1] = 1;       // edge 0 → 1

• Space: O(V²).
• Edge check: O(1).
• Iterate neighbors of v: O(V).

Best for dense graphs.

29.4.2 Adjacency list

For each vertex, a list of its neighbors.

vector<vector<int>> adjList(V);
adjList[0].push_back(1);   // edge 0 → 1
adjList[1].push_back(0);   // (if undirected)

• Space: O(V + E).
• Edge check: O(degree).
• Iterate neighbors of v: O(degree).

Best for sparse graphs. Default to this unless V² is small or you need fast edge lookups.

29.5 BFS

Explore in layers — visit all neighbors first, then their neighbors.

void bfs(const vector<vector<int>>& adj, int start) {
  vector<bool> visited(adj.size(), false);
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    cout << v << " ";
    for (int u : adj[v]) {
      if (!visited[u]) {
        visited[u] = true;
        q.push(u);
      }
    }
  }
}

Each vertex is enqueued once. Each edge is examined twice (in undirected) or once (directed). Total: O(V + E).

BFS finds shortest paths in unweighted graphs — the first time you reach a vertex is via the fewest edges.

29.6 DFS

Go deep before backtracking.

void dfs(const vector<vector<int>>& adj, int v, vector<bool>& visited) {
  visited[v] = true;
  cout << v << " ";
  for (int u : adj[v]) {
    if (!visited[u]) dfs(adj, u, visited);
  }
}

Recursive form is idiomatic. The iterative form uses a stack:

void dfsIter(const vector<vector<int>>& adj, int start) {
  vector<bool> visited(adj.size(), false);
  stack<int> stk;
  stk.push(start);
  while (!stk.empty()) {
    int v = stk.top();
    stk.pop();
    if (visited[v]) continue;
    visited[v] = true;
    cout << v << " ";
    for (int u : adj[v]) {
      if (!visited[u]) stk.push(u);
    }
  }
}

Complexity: same as BFS, O(V + E).

BFS uses a queue; DFS uses a stack (explicit or recursion’s call stack). That is the only structural difference. Internalize that and you have internalized graph traversal.

29.7 Connected components

int countComponents(const vector<vector<int>>& adj) {
  int n = adj.size();
  vector<bool> visited(n, false);
  int count = 0;
  for (int v = 0; v < n; ++v) {
    if (!visited[v]) {
      ++count;
      dfs(adj, v, visited);
    }
  }
  return count;
}

Sweep all vertices. Every time you find an unvisited one, start a fresh DFS — that DFS marks one entire component. Count the number of starts.

29.8 DFS as backtracking

DFS on a graph + undoing visited status on return = backtracking. This is the airline route / 8-queens shape:

bool dfsPath(const vector<vector<int>>& adj, int source, int dest,
             vector<bool>& visited) {
  if (source == dest) return true;
  visited[source] = true;
  for (int n : adj[source]) {
    if (!visited[n]) {
      if (dfsPath(adj, n, dest, visited)) return true;
    }
  }
  return false;
}

If your problem is “find one path” you stop as soon as you find it. If your problem is “find all paths” you mark, recurse, then unmark on return:

visited[source] = true;
for (int n : adj[source]) {
  // ... recurse
}
visited[source] = false;    // backtrack

29.9 Try it

Implement BFS and print the order vertices are visited starting from vertex 0 on the graph {0→1, 0→2, 1→3, 2→3, 3→4}. Then DFS the same graph. Compare orders.

BFS order (from 0): 0 1 2 3 4. DFS order (from 0, depending on recursion order): 0 1 3 4 2.

29.10 Self-check

1. To find the shortest path (fewest edges) in an unweighted graph, use:

• a. DFS
• b. BFS
• c. Dijkstra
• d. Bellman-Ford

b. BFS visits vertices in order of distance from source.

2. For a sparse graph with V = 1000, E = 3000, prefer:

• a. Adjacency matrix
• b. Either is fine
• c. Adjacency list
• d. Edge list

c. Matrix would use 10⁶ entries for 3000 edges. List uses ~6000 entries (E for directed, 2E undirected).

29.11 Challenges

1. Number of Islands (#200) — the warmup.
2. Flood Fill (#733).
3. Number of Connected Components in an Undirected Graph (#323).
4. Course Schedule (#207) — DFS for cycle detection.

29.12 Where this fits

We have unweighted graph traversal. Next chapter adds weights — Dijkstra’s shortest path and minimum spanning trees.

You are here	Coming up
Graph representation, BFS, DFS, connected components	Chapter 27: Dijkstra, MST, topological sort