Graph Algorithms: BFS, DFS, Dijkstra, and More — Complete Guide

Graphs are everywhere — web links, road networks, social connections, dependency trees, and circuit boards all map naturally to graphs. Mastering graph algorithms means you can solve entire categories of problems by recognising the pattern and picking the right traversal.

This guide covers the core algorithms, when to use each, and working code in JavaScript, Python, and Go.

Quick reference

V = number of vertices, E = number of edges, α = inverse Ackermann (practically O(1)).

Graph representations

Adjacency list — use for sparse graphs

// JavaScript — undirected graph
const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 4],
  3: [1],
  4: [2],
};

// Weighted adjacency list
const weighted = {
  0: [{node: 1, w: 4}, {node: 2, w: 1}],
  1: [{node: 0, w: 4}, {node: 3, w: 1}],
  2: [{node: 0, w: 1}, {node: 4, w: 5}],
};

# Python — build from edge list
from collections import defaultdict

def build_graph(n, edges):
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)  # omit for directed
    return g

Adjacency matrix — use for dense graphs or when O(1) edge lookup matters

# n×n matrix; matrix[u][v] = 1 means edge u→v
n = 5
matrix = [[0] * n for _ in range(n)]
matrix[0][1] = 1
matrix[1][0] = 1  # undirected

When to use which:

BFS — Breadth-First Search

BFS explores layer by layer. Use it when you need:

• Shortest path in an unweighted graph (guaranteed optimal)
• Level-order traversal
• Finding all nodes within k hops

BFS shortest path

// JavaScript
function bfs(graph, start, end) {
  const queue = [[start, [start]]];
  const visited = new Set([start]);

  while (queue.length) {
    const [node, path] = queue.shift();
    if (node === end) return path;

    for (const neighbour of (graph[node] || [])) {
      if (!visited.has(neighbour)) {
        visited.add(neighbour);
        queue.push([neighbour, [...path, neighbour]]);
      }
    }
  }
  return null; // no path
}

// Distance-only BFS (more memory-efficient)
function bfsDistance(graph, start) {
  const dist = { [start]: 0 };
  const queue = [start];

  while (queue.length) {
    const node = queue.shift();
    for (const nb of (graph[node] || [])) {
      if (dist[nb] === undefined) {
        dist[nb] = dist[node] + 1;
        queue.push(nb);
      }
    }
  }
  return dist;
}

# Python
from collections import deque

def bfs(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}

    while queue:
        node, path = queue.popleft()
        if node == end:
            return path
        for nb in graph.get(node, []):
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, path + [nb]))
    return None

// Go
func bfs(graph map[int][]int, start, end int) []int {
	type state struct {
		node int
		path []int
	}
	visited := map[int]bool{start: true}
	queue := []state{{start, []int{start}}}

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		if cur.node == end {
			return cur.path
		}
		for _, nb := range graph[cur.node] {
			if !visited[nb] {
				visited[nb] = true
				newPath := append(append([]int{}, cur.path...), nb)
				queue = append(queue, state{nb, newPath})
			}
		}
	}
	return nil
}

Multi-source BFS

Start BFS from multiple nodes simultaneously — useful for "nearest X" problems.

# Distance from any rotten orange to every fresh orange (LeetCode 994)
def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, minutes)
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    for r, c, t in queue:  # BFS from all rotten oranges at once
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                minutes = max(minutes, t + 1)
                queue.append((nr, nc, t + 1))

    return minutes if fresh == 0 else -1

DFS — Depth-First Search

DFS explores as deep as possible before backtracking. Use it for:

• Cycle detection
• Connected components / flood fill
• Topological sort (DFS post-order)
• Path existence (not shortest)
• Tree problems (preorder, inorder, postorder)

Iterative DFS

// JavaScript — iterative (avoids call stack overflow on large graphs)
function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);
    for (const nb of (graph[node] || [])) {
      if (!visited.has(nb)) stack.push(nb);
    }
  }
  return order;
}

Recursive DFS with cycle detection (directed graph)

# Python — WHITE/GRAY/BLACK colouring
WHITE, GRAY, BLACK = 0, 1, 2

def has_cycle(graph, n):
    colour = [WHITE] * n

    def dfs(u):
        colour[u] = GRAY          # currently exploring
        for v in graph.get(u, []):
            if colour[v] == GRAY:  # back edge → cycle
                return True
            if colour[v] == WHITE and dfs(v):
                return True
        colour[u] = BLACK          # fully explored
        return False

    return any(dfs(u) for u in range(n) if colour[u] == WHITE)

Connected components

def count_components(n, edges):
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    visited = set()
    components = 0

    def dfs(node):
        visited.add(node)
        for nb in g[node]:
            if nb not in visited:
                dfs(nb)

    for node in range(n):
        if node not in visited:
            dfs(node)
            components += 1

    return components

Dijkstra's Algorithm

Finds the shortest path from a source to all nodes in a weighted graph with non-negative edges.

Key idea: always expand the cheapest unvisited node (greedy via min-heap).

// JavaScript — priority queue with min-heap simulation
class MinHeap {
  constructor() { this.heap = []; }
  push([cost, node]) {
    this.heap.push([cost, node]);
    this.heap.sort((a, b) => a[0] - b[0]); // toy impl; use a real heap in prod
  }
  pop() { return this.heap.shift(); }
  get size() { return this.heap.length; }
}

function dijkstra(graph, start) {
  // graph: { node: [{node, w}] }
  const dist = {};
  const heap = new MinHeap();

  heap.push([0, start]);
  dist[start] = 0;

  while (heap.size) {
    const [cost, u] = heap.pop();
    if (cost > (dist[u] ?? Infinity)) continue; // stale entry

    for (const {node: v, w} of (graph[u] || [])) {
      const newCost = cost + w;
      if (newCost < (dist[v] ?? Infinity)) {
        dist[v] = newCost;
        heap.push([newCost, v]);
      }
    }
  }
  return dist;
}

# Python — heapq (proper min-heap)
import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    heap = [(0, start)]  # (cost, node)

    while heap:
        cost, u = heapq.heappop(heap)
        if cost > dist.get(u, float('inf')):
            continue  # stale entry
        for v, w in graph.get(u, []):
            new_cost = cost + w
            if new_cost < dist.get(v, float('inf')):
                dist[v] = new_cost
                heapq.heappush(heap, (new_cost, v))

    return dist

# With path reconstruction
def dijkstra_path(graph, start, end):
    dist = {start: 0}
    prev = {}
    heap = [(0, start)]

    while heap:
        cost, u = heapq.heappop(heap)
        if cost > dist.get(u, float('inf')):
            continue
        for v, w in graph.get(u, []):
            new_cost = cost + w
            if new_cost < dist.get(v, float('inf')):
                dist[v] = new_cost
                prev[v] = u
                heapq.heappush(heap, (new_cost, v))

    # Reconstruct path
    path, node = [], end
    while node in prev:
        path.append(node)
        node = prev[node]
    path.append(start)
    return list(reversed(path)), dist.get(end, float('inf'))

// Go
import "container/heap"

type Item struct{ cost, node int }
type PQ []Item
func (pq PQ) Len() int            { return len(pq) }
func (pq PQ) Less(i, j int) bool  { return pq[i].cost < pq[j].cost }
func (pq PQ) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PQ) Pop() interface{} {
	old := *pq; n := len(old); x := old[n-1]; *pq = old[:n-1]; return x
}

func dijkstra(graph map[int][][2]int, start int) map[int]int {
	dist := map[int]int{start: 0}
	pq := &PQ{{0, start}}
	heap.Init(pq)

	for pq.Len() > 0 {
		cur := heap.Pop(pq).(Item)
		if d, ok := dist[cur.node]; ok && cur.cost > d {
			continue
		}
		for _, edge := range graph[cur.node] {
			v, w := edge[0], edge[1]
			newCost := cur.cost + w
			if d, ok := dist[v]; !ok || newCost < d {
				dist[v] = newCost
				heap.Push(pq, Item{newCost, v})
			}
		}
	}
	return dist
}

Bellman-Ford

Handles negative edge weights. Slower than Dijkstra but also detects negative weight cycles.

def bellman_ford(n, edges, src):
    # edges: list of (u, v, w)
    dist = [float('inf')] * n
    dist[src] = 0

    # Relax all edges V-1 times
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # early exit

    # Check for negative cycles (one more round)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle detected

    return dist

When Dijkstra fails, use Bellman-Ford:

• Currency arbitrage detection (negative cycle = profit loop)
• Graphs with price discounts that reduce path cost

Topological Sort

Orders nodes of a DAG (Directed Acyclic Graph) so every edge u→v has u before v. Used for build systems, package dependency resolution, task scheduling.

Kahn's Algorithm (BFS-based) — preferred

from collections import deque

def topo_sort(n, edges):
    # edges: list of (u, v) meaning u must come before v
    in_degree = [0] * n
    adj = defaultdict(list)

    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(order) != n:
        return None  # cycle exists — no valid topological order

    return order

// JavaScript
function topoSort(n, edges) {
  const inDegree = new Array(n).fill(0);
  const adj = Array.from({length: n}, () => []);

  for (const [u, v] of edges) {
    adj[u].push(v);
    inDegree[v]++;
  }

  const queue = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of adj[u]) {
      if (--inDegree[v] === 0) queue.push(v);
    }
  }

  return order.length === n ? order : null; // null = cycle
}

DFS post-order (alternative)

def topo_sort_dfs(n, adj):
    visited = [False] * n
    stack = []

    def dfs(u):
        visited[u] = True
        for v in adj.get(u, []):
            if not visited[v]:
                dfs(v)
        stack.append(u)

    for i in range(n):
        if not visited[i]:
            dfs(i)

    return list(reversed(stack))

Union-Find (Disjoint Set Union)

Efficiently tracks connected components. Supports two operations:

• find(x) — which component is x in?
• union(x, y) — merge components of x and y

With path compression and union by rank, both operations are effectively O(1).

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already in same component
        # union by rank
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)


# Cycle detection in undirected graph
def has_cycle_undirected(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):  # u and v already connected → cycle
            return True
    return False

// JavaScript
class UnionFind {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return false;
    if (this.rank[px] < this.rank[py]) {
      this.parent[px] = py;
    } else if (this.rank[px] > this.rank[py]) {
      this.parent[py] = px;
    } else {
      this.parent[py] = px;
      this.rank[px]++;
    }
    return true;
  }
}

Minimum Spanning Tree

An MST connects all V vertices with exactly V−1 edges and minimum total weight.

Kruskal's Algorithm (sort edges, use Union-Find)

def kruskal(n, edges):
    # edges: list of (w, u, v)
    edges.sort()                 # sort by weight
    uf = UnionFind(n)
    mst_cost = 0
    mst_edges = []

    for w, u, v in edges:
        if uf.union(u, v):       # only add if it doesn't form a cycle
            mst_cost += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break            # MST is complete

    return mst_cost, mst_edges

Prim's Algorithm (grow MST from a starting node)

def prim(graph, start=0):
    # graph: {node: [(neighbor, weight)]}
    visited = set([start])
    heap = [(w, start, nb) for nb, w in graph[start]]
    heapq.heapify(heap)
    mst_cost = 0

    while heap and len(visited) < len(graph):
        w, u, v = heapq.heappop(heap)
        if v in visited:
            continue
        visited.add(v)
        mst_cost += w
        for nb, weight in graph[v]:
            if nb not in visited:
                heapq.heappush(heap, (weight, v, nb))

    return mst_cost

Floyd-Warshall — All-Pairs Shortest Path

Finds shortest paths between every pair of vertices. Works with negative edges (but not negative cycles).

def floyd_warshall(n, edges):
    # edges: list of (u, v, w)
    INF = float('inf')
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w

    for k in range(n):           # intermediate node
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # Check for negative cycles
    for i in range(n):
        if dist[i][i] < 0:
            return None

    return dist

Algorithm selection guide

Classic interview patterns

Pattern 1 — Grid as implicit graph

Many 2D grid problems are graph problems in disguise:

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0

    def dfs(r, c):
        if (r, c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == '0':
            return
        visited.add((r, c))
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            dfs(r+dr, c+dc)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in visited:
                dfs(r, c)
                count += 1
    return count

Pattern 2 — Bidirectional BFS

Cuts BFS search space roughly in half for shortest path between two nodes:

def bidir_bfs(graph, start, end):
    if start == end:
        return 0

    front = {start: 0}    # {node: distance from start}
    back  = {end: 0}      # {node: distance from end}
    front_q = deque([start])
    back_q  = deque([end])

    def expand(queue, visited, other):
        node = queue.popleft()
        for nb in graph.get(node, []):
            if nb not in visited:
                visited[nb] = visited[node] + 1
                queue.append(nb)
            if nb in other:
                return visited[nb] + other[nb]
        return float('inf')

    best = float('inf')
    while front_q or back_q:
        if front_q:
            best = min(best, expand(front_q, front, back))
        if back_q:
            best = min(best, expand(back_q, back, front))
        if best < float('inf'):
            return best
    return -1

Pattern 3 — State space BFS

When the "graph" isn't given explicitly — nodes are states, edges are valid transitions:

# Word Ladder: change one letter at a time
# beginWord → ... → endWord, all intermediate words in wordList
def word_ladder(begin, end, word_list):
    word_set = set(word_list)
    if end not in word_set:
        return 0

    queue = deque([(begin, 1)])  # (word, steps)
    visited = {begin}

    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + c + word[i+1:]
                if next_word == end:
                    return steps + 1
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))
    return 0

Common LeetCode problems by algorithm

Common mistakes

FAQ

Q: When should I use BFS vs DFS?

Use BFS when you need the shortest path in an unweighted graph — BFS explores level by level and guarantees optimality. Use DFS when you need to explore all possibilities (cycle detection, all paths, connected components, topological sort). DFS is also usually simpler to implement recursively for tree problems.

Q: Why can't Dijkstra handle negative edges?

Dijkstra's greedy assumption: "once we've settled a node with cost X, no cheaper path can arrive later." A negative edge from an unsettled node can always create a cheaper path to an already-settled node, breaking this assumption. Example: node A settled at cost 5, but later we find A←B←C where B→A has weight -10, giving cost -5.

Q: What's the difference between topological sort and cycle detection?

They're closely related. Kahn's algorithm for topological sort inherently detects cycles: if the output order contains fewer nodes than the graph has, a cycle exists (some nodes' in-degrees never reached 0). Use len(order) != n as your cycle check.

Q: When should I use Union-Find vs BFS/DFS for connectivity?

If queries are static (graph is fixed, answer multiple queries), BFS/DFS once is O(V+E). If queries are dynamic (edges are added online, "are u and v connected after each edge?"), Union-Find handles each union and find in near-O(1), which BFS/DFS can't match.

Q: What does "sparse" vs "dense" mean for graphs?

• Sparse: E ≈ V (few edges per node) — use adjacency list
• Dense: E ≈ V² (almost all possible edges exist) — adjacency matrix may be better

Real-world graphs (social networks, road maps) are almost always sparse.

Q: How do I detect a negative cycle with Bellman-Ford?

After V−1 relaxation rounds, run one more round. If any distance can still be reduced in this extra round, a negative cycle is reachable from the source.

Graph algorithms reward pattern recognition. Once you can quickly classify a problem (shortest path? connectivity? ordering?), the algorithm choice becomes mechanical. The hardest part is realising the problem is a graph problem — grids, dependency lists, and state machines all reduce to the same primitives.