Graphs in DSA — BFS, DFS, Number of Islands, Topological Sort, Dijkstra with Code

A graph is a set of nodes (vertices) connected by edges. Cities and roads, people and friendships, courses and prerequisites — all graphs. Trees are a special graph with no cycles. Graph questions look scary, but BFS and DFS solve most of them.

Representing a graph

Interviews usually give you an edge list like [[0,1],[1,2],[2,0]]. Convert it to an adjacency list — each node maps to its neighbours:

from collections import defaultdict

def build_graph(n, edges, directed=False):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        if not directed:
            graph[v].append(u)
    return graph

List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (int[] e : edges) { graph.get(e[0]).add(e[1]); graph.get(e[1]).add(e[0]); }

A grid is also a graph: each cell is a node connected to its 4 neighbours (up, down, left, right).

Always keep a visited set. Unlike trees, graphs can have cycles — without it you loop forever.

DFS — go deep first

def dfs(node, graph, visited):
    visited.add(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(nxt, graph, visited)

Number of Islands (count groups of connected '1' cells): scan the grid; each time you find unvisited land, that's a new island — run DFS to "sink" all its cells.

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
            return
        grid[r][c] = '0'                          # mark visited
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

O(rows × cols) — every cell is visited once. Number of Provinces, Flood Fill and Surrounded Regions are the same idea.

BFS — go level by level (shortest steps)

BFS explores nodes in order of distance from the start, so in an unweighted graph it finds the shortest path (fewest edges).

from collections import deque

def shortest_steps(graph, start, target):
    q, dist = deque([start]), {start: 0}
    while q:
        node = q.popleft()
        if node == target:
            return dist[node]
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return -1

Rotting Oranges uses multi-source BFS: put all rotten oranges in the queue at the start, then spread one minute (one level) at a time. Word Ladder is BFS where each word connects to words one letter away.

Topological sort — ordering with prerequisites

Course Schedule: can you finish all courses if some must come before others? That's asking whether the directed graph has a cycle. Kahn's algorithm: repeatedly take courses with no remaining prerequisites (in-degree 0).

def can_finish(n, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * n
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1

    q = deque(i for i in range(n) if indegree[i] == 0)
    taken = 0
    while q:
        c = q.popleft()
        taken += 1
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return taken == n          # if a cycle exists, some courses never reach in-degree 0

The order in which courses leave the queue is a valid topological order (Course Schedule II). O(V + E).

Union-Find (Disjoint Set Union)

Union-Find tracks which nodes belong to the same group, with near-O(1) union and find. Perfect for "are these connected?" and "which edge creates a cycle?" (Redundant Connection).

parent = list(range(n))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path compression
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                    # already connected → this edge makes a cycle
    parent[ra] = rb
    return True

Dijkstra — shortest path with weights

When edges have weights (travel time, cost), BFS isn't enough. Dijkstra's algorithm uses a min-heap to always expand the closest unfinished node.

import heapq

def dijkstra(graph, src, n):            # graph[u] = [(v, w), ...]
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                    # stale entry
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

O((V + E) log V). Works only with non-negative weights. Network Delay Time is Dijkstra directly.

Which algorithm when?

Question	Use
count connected groups / islands	DFS or BFS (or Union-Find)
shortest path, unweighted / fewest steps	BFS
spreading from many sources at once	multi-source BFS
order with prerequisites / detect cycle in directed graph	topological sort
dynamic connectivity, redundant edge	Union-Find
shortest path with non-negative weights	Dijkstra

Common mistakes

No visited tracking → infinite loops.
Marking visited when popping in BFS instead of when pushing → the same node enters the queue many times.
Grid bounds checks in the wrong order (check bounds before reading grid[r][c]).
Using BFS for weighted shortest paths.

Key takeaways

Convert input to an adjacency list; grids are implicit graphs.
DFS for exploring/connectivity, BFS for shortest steps.
Topological sort for prerequisites, Union-Find for grouping, Dijkstra for weighted shortest paths.

Graphs — BFS, DFS, Topological Sort, Union-Find and Dijkstra