Graphs

1. What is a Graph?

A graph is a collection of vertices (nodes) connected by edges (links). Unlike trees, graphs can have cycles, multiple paths between nodes, and no required root.

Visual Example

    An undirected graph with 5 vertices and 6 edges:

        (A)-----(B)
        / \       |
       /   \      |
     (C)   (D)---(E)
       \         /
        \-------/

    V = {A, B, C, D, E}
    E = {(A,B), (A,C), (A,D), (B,E), (D,E), (C,E)}

Directed vs Undirected

Undirected: Edges have no direction. If A connects to B, then B connects to A.

Directed (Digraph): Edges have direction. A → B does NOT mean B → A.

    Undirected:              Directed:

     (A)---(B)              (A)--->(B)
      |     |                |       |
     (C)---(D)              (C)<---(D)
                                ^
                              A->B, A->C, D->B, D->C

Weighted vs Unweighted

Unweighted: All edges are equal. Weighted: Edges carry a cost/distance/value.

    Weighted graph (think road distances):

       (A)---5---(B)
        |         |
        2         3
        |         |
       (C)---1---(D)

    Shortest A->D: A->C->D = 2+1 = 3  (not A->B->D = 5+3 = 8)

Cyclic vs Acyclic

Cyclic: Contains at least one cycle (a path that starts and ends at the same vertex). Acyclic: No cycles.

    Cyclic:                 Acyclic:

     (A)--->(B)              (A)--->(B)
      ^      |                       |
      |      v                       v
     (D)<---(C)              (C)    (D)

Connected vs Disconnected

Connected: There is a path between every pair of vertices. Disconnected: Some vertices are unreachable from others.

    Connected:              Disconnected (2 components):

     (A)---(B)               (A)---(B)     (D)---(E)
      |     |                  |
     (C)---(D)               (C)

DAG (Directed Acyclic Graph)

    A DAG representing course prerequisites:

     (Math101)--->(Math201)--->(Math301)
                      |
                      v
     (CS101)---->(CS201)---->(CS301)
                      |
                      v
                  (CS250)

2. Graph Representations

There are three main ways to represent a graph in code. Your choice depends on the problem constraints.

    Reference graph for all examples below:

        (0)----(1)
         |    / |
         |   /  |
         |  /   |
        (2)----(3)

Adjacency Matrix

A 2D array where matrix[i][j] = 1 if there is an edge from vertex i to vertex j.

         0  1  2  3
    0 [  0  1  1  0 ]
    1 [  1  0  1  1 ]
    2 [  1  1  0  1 ]
    3 [  0  1  1  0 ]

Pros: O(1) edge lookup — just check matrix[i][j]. Simple to implement.

Cons: O(V²) space regardless of edge count. Wasteful for sparse graphs.

Pythonclass GraphMatrix:
    def __init__(self, num_vertices):
        self.V = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]

    def add_edge(self, u, v):
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1  # remove for directed

    def has_edge(self, u, v):
        return self.matrix[u][v] == 1

    def get_neighbors(self, v):
        return [i for i in range(self.V) if self.matrix[v][i]]

g = GraphMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g.has_edge(0, 3))   # False
print(g.get_neighbors(1))  # [0, 2, 3]

JavaScriptclass GraphMatrix {
  constructor(numVertices) {
    this.V = numVertices;
    this.matrix = Array.from({ length: numVertices },
      () => new Array(numVertices).fill(0));
  }

  addEdge(u, v) {
    this.matrix[u][v] = 1;
    this.matrix[v][u] = 1;  // remove for directed
  }

  hasEdge(u, v) {
    return this.matrix[u][v] === 1;
  }

  getNeighbors(v) {
    return this.matrix[v]
      .map((val, idx) => val ? idx : -1)
      .filter(idx => idx !== -1);
  }
}

const g = new GraphMatrix(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
console.log(g.hasEdge(0, 3));   // false
console.log(g.getNeighbors(1));  // [0, 2, 3]

Adjacency List

A dictionary/map where each vertex maps to a list of its neighbors.

    Adjacency list for our reference graph:

    0: [1, 2]
    1: [0, 2, 3]
    2: [0, 1, 3]
    3: [1, 2]

Pros: O(V + E) space. Efficient for sparse graphs. Easy to iterate neighbors.

Cons: O(V) edge lookup in worst case (check if neighbor exists in list).

Pythonfrom collections import defaultdict

class Graph:
    def __init__(self):
        self.adj = defaultdict(list)

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)  # remove for directed

    def get_neighbors(self, v):
        return self.adj[v]

    def has_edge(self, u, v):
        return v in self.adj[u]

g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g.get_neighbors(1))  # [0, 2, 3]

JavaScriptclass Graph {
  constructor() {
    this.adj = new Map();
  }

  addVertex(v) {
    if (!this.adj.has(v)) this.adj.set(v, []);
  }

  addEdge(u, v) {
    this.addVertex(u);
    this.addVertex(v);
    this.adj.get(u).push(v);
    this.adj.get(v).push(u);  // remove for directed
  }

  getNeighbors(v) {
    return this.adj.get(v) || [];
  }

  hasEdge(u, v) {
    return this.adj.has(u) && this.adj.get(u).includes(v);
  }
}

const g = new Graph();
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
console.log(g.getNeighbors(1));  // [0, 2, 3]

Edge List

A simple list of [from, to, weight] tuples. Rarely used for traversal, but essential for Kruskal's MST algorithm (sort edges by weight).

Python# Edge list: [(from, to, weight), ...]
edges = [
    (0, 1, 5),
    (0, 2, 2),
    (1, 2, 4),
    (1, 3, 3),
    (2, 3, 1),
]

# Sort by weight (useful for Kruskal's)
edges.sort(key=lambda e: e[2])
print(edges)
# [(2,3,1), (0,2,2), (1,3,3), (1,2,4), (0,1,5)]

JavaScriptconst edges = [
  [0, 1, 5],
  [0, 2, 2],
  [1, 2, 4],
  [1, 3, 3],
  [2, 3, 1],
];

// Sort by weight (useful for Kruskal's)
edges.sort((a, b) => a[2] - b[2]);
console.log(edges);
// [[2,3,1], [0,2,2], [1,3,3], [1,2,4], [0,1,5]]

Representation Comparison

3. Graph Traversals

The two fundamental ways to explore a graph. Both visit every reachable vertex exactly once.

    Reference graph for traversal walkthroughs:

        (0)----(1)
        / \      \
       /   \      \
     (2)   (3)---(4)
       \         /
        \       /
         (5)--/

BFS (Breadth-First Search)

Explores level by level. Uses a queue. Think of it like ripples spreading from a stone dropped in water.

Starting from vertex 0:

Queue: [0]          Visited: {0}
Process 0 -> add neighbors 1, 2, 3

Queue: [1, 2, 3]   Visited: {0, 1, 2, 3}
Process 1 -> add neighbor 4 (0 already visited)

Queue: [2, 3, 4]   Visited: {0, 1, 2, 3, 4}
Process 2 -> add neighbor 5 (0 already visited)

Queue: [3, 4, 5]   Visited: {0, 1, 2, 3, 4, 5}
Process 3 -> neighbor 4 already visited

Queue: [4, 5]      Visited: {0, 1, 2, 3, 4, 5}
Process 4 -> neighbors 3, 5 already visited

Queue: [5]          Visited: {0, 1, 2, 3, 4, 5}
Process 5 -> neighbors 2, 4 already visited

Queue: []           DONE!

BFS Order: 0 -> 1 -> 2 -> 3 -> 4 -> 5
Level 0: {0}  |  Level 1: {1,2,3}  |  Level 2: {4,5}

Pythonfrom collections import deque

def bfs(graph, start):
    """BFS traversal from a starting vertex."""
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

# Adjacency list representation
graph = {
    0: [1, 2, 3],
    1: [0, 4],
    2: [0, 5],
    3: [0, 4],
    4: [1, 3, 5],
    5: [2, 4],
}

print(bfs(graph, 0))  # [0, 1, 2, 3, 4, 5]

JavaScriptfunction bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const order = [];

  while (queue.length > 0) {
    const vertex = queue.shift();
    order.push(vertex);

    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return order;
}

const graph = {
  0: [1, 2, 3],
  1: [0, 4],
  2: [0, 5],
  3: [0, 4],
  4: [1, 3, 5],
  5: [2, 4],
};

console.log(bfs(graph, 0));  // [0, 1, 2, 3, 4, 5]

DFS (Depth-First Search)

Explores as deep as possible before backtracking. Uses a stack (or recursion, which uses the call stack). Think of it like exploring a maze — go down a path until you hit a dead end, then backtrack.

Starting from vertex 0 (recursive):

Visit 0 -> go to neighbor 1
  Visit 1 -> go to neighbor 4
    Visit 4 -> go to neighbor 3
      Visit 3 -> neighbor 0 visited, neighbor 4 visited, backtrack
    back to 4 -> go to neighbor 5
      Visit 5 -> go to neighbor 2
        Visit 2 -> neighbor 0 visited, backtrack
      back to 5 -> backtrack
    back to 4 -> backtrack
  back to 1 -> backtrack
back to 0 -> neighbors 2,3 already visited -> DONE

DFS Order: 0 -> 1 -> 4 -> 3 -> 5 -> 2

DFS - Recursive

Pythondef dfs_recursive(graph, vertex, visited=None):
    """DFS traversal using recursion."""
    if visited is None:
        visited = set()

    visited.add(vertex)
    print(vertex, end=" ")

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited

# Usage
graph = {
    0: [1, 2, 3],
    1: [0, 4],
    2: [0, 5],
    3: [0, 4],
    4: [1, 3, 5],
    5: [2, 4],
}
dfs_recursive(graph, 0)  # 0 1 4 3 5 2

JavaScriptfunction dfsRecursive(graph, vertex, visited = new Set()) {
  visited.add(vertex);
  const order = [vertex];

  for (const neighbor of graph[vertex]) {
    if (!visited.has(neighbor)) {
      order.push(...dfsRecursive(graph, neighbor, visited));
    }
  }

  return order;
}

console.log(dfsRecursive(graph, 0));  // [0, 1, 4, 3, 5, 2]

DFS - Iterative (Using Explicit Stack)

Pythondef dfs_iterative(graph, start):
    """DFS traversal using explicit stack."""
    visited = set()
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)

        # Add neighbors in reverse for same order as recursive
        for neighbor in reversed(graph[vertex]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order

print(dfs_iterative(graph, 0))  # [0, 1, 4, 3, 5, 2]

JavaScriptfunction dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const order = [];

  while (stack.length > 0) {
    const vertex = stack.pop();
    if (visited.has(vertex)) continue;
    visited.add(vertex);
    order.push(vertex);

    // Add neighbors in reverse for same order as recursive
    for (const neighbor of [...graph[vertex]].reverse()) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }

  return order;
}

console.log(dfsIterative(graph, 0));  // [0, 1, 4, 3, 5, 2]

BFS vs DFS Comparison

4. Common Graph Algorithms

Shortest Path - BFS (Unweighted)

In an unweighted graph, BFS naturally finds the shortest path because it explores nodes level by level. Track parent pointers to reconstruct the actual path.

    Finding shortest path from A to E:

        (A)---(B)---(E)
         |         /
        (C)---(D)-/

    BFS from A:
    Level 0: A
    Level 1: B, C
    Level 2: E, D     <-- E found at level 2 = distance 2

    Shortest path: A -> B -> E

Pythonfrom collections import deque

def bfs_shortest_path(graph, start, end):
    """Find shortest path in unweighted graph using BFS."""
    if start == end:
        return [start]

    visited = set([start])
    queue = deque([(start, [start])])  # (vertex, path)

    while queue:
        vertex, path = queue.popleft()

        for neighbor in graph[vertex]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return []  # no path found

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'E'],
    'C': ['A', 'D'],
    'D': ['C', 'E'],
    'E': ['B', 'D'],
}

print(bfs_shortest_path(graph, 'A', 'E'))  # ['A', 'B', 'E']

JavaScriptfunction bfsShortestPath(graph, start, end) {
  if (start === end) return [start];

  const visited = new Set([start]);
  const queue = [[start, [start]]];  // [vertex, path]

  while (queue.length > 0) {
    const [vertex, path] = queue.shift();

    for (const neighbor of graph[vertex]) {
      if (neighbor === end) {
        return [...path, neighbor];
      }
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return [];  // no path found
}

console.log(bfsShortestPath(graph, 'A', 'E'));  // ['A', 'B', 'E']

Dijkstra's Algorithm (Weighted Shortest Path)

Finds the shortest path in a weighted graph with non-negative edges. Uses a priority queue (min heap) to always process the closest unvisited vertex next.

    Graph:
        (A)---5---(B)
         |  \      |
         2   8     3
         |    \    |
        (C)--1-(D)-+

    Find shortest path from A to all vertices:

    Init:   dist = {A:0, B:inf, C:inf, D:inf}
            heap = [(0, A)]

    Step 1: Pop (0, A) -> process A
            Update B: 0+5=5, C: 0+2=2, D: 0+8=8
            dist = {A:0, B:5, C:2, D:8}
            heap = [(2,C), (5,B), (8,D)]

    Step 2: Pop (2, C) -> process C
            Update D: 2+1=3 < 8 -> update!
            dist = {A:0, B:5, C:2, D:3}
            heap = [(3,D), (5,B), (8,D)]

    Step 3: Pop (3, D) -> process D
            Update B: 3+3=6 > 5 -> no update
            dist = {A:0, B:5, C:2, D:3}

    Step 4: Pop (5, B) -> process B
            No better paths found

    Final: A->A:0, A->B:5, A->C:2, A->D:3
    Shortest A->D: A -> C -> D  (cost 3)

Pythonimport heapq

def dijkstra(graph, start):
    """
    Dijkstra's shortest path algorithm.
    graph: {vertex: [(neighbor, weight), ...]}
    Returns: {vertex: shortest_distance}
    """
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    prev = {v: None for v in graph}
    heap = [(0, start)]  # (distance, vertex)

    while heap:
        d, u = heapq.heappop(heap)

        # Skip if we already found a shorter path
        if d > dist[u]:
            continue

        for neighbor, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                prev[neighbor] = u
                heapq.heappush(heap, (new_dist, neighbor))

    return dist, prev

def reconstruct_path(prev, start, end):
    """Rebuild path from prev pointers."""
    path = []
    current = end
    while current is not None:
        path.append(current)
        current = prev[current]
    return path[::-1]

# Weighted adjacency list: vertex -> [(neighbor, weight), ...]
graph = {
    'A': [('B', 5), ('C', 2), ('D', 8)],
    'B': [('A', 5), ('D', 3)],
    'C': [('A', 2), ('D', 1)],
    'D': [('A', 8), ('B', 3), ('C', 1)],
}

dist, prev = dijkstra(graph, 'A')
print(dist)  # {'A': 0, 'B': 5, 'C': 2, 'D': 3}
print(reconstruct_path(prev, 'A', 'D'))  # ['A', 'C', 'D']

JavaScriptfunction dijkstra(graph, start) {
  const dist = {};
  const prev = {};

  for (const v of Object.keys(graph)) {
    dist[v] = Infinity;
    prev[v] = null;
  }
  dist[start] = 0;

  // Simple priority queue using sorted array
  // (for production, use a real min-heap)
  const pq = [[0, start]];  // [distance, vertex]

  while (pq.length > 0) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift();

    if (d > dist[u]) continue;

    for (const [neighbor, weight] of graph[u]) {
      const newDist = dist[u] + weight;
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        prev[neighbor] = u;
        pq.push([newDist, neighbor]);
      }
    }
  }

  return { dist, prev };
}

function reconstructPath(prev, start, end) {
  const path = [];
  let current = end;
  while (current !== null) {
    path.unshift(current);
    current = prev[current];
  }
  return path;
}

const graph = {
  A: [['B', 5], ['C', 2], ['D', 8]],
  B: [['A', 5], ['D', 3]],
  C: [['A', 2], ['D', 1]],
  D: [['A', 8], ['B', 3], ['C', 1]],
};

const { dist, prev } = dijkstra(graph, 'A');
console.log(dist);  // {A: 0, B: 5, C: 2, D: 3}
console.log(reconstructPath(prev, 'A', 'D'));  // ['A', 'C', 'D']

Topological Sort

A linear ordering of vertices in a DAG such that for every edge u → v, vertex u comes before v. Think of it as a valid task execution order where all dependencies are satisfied first.

    DAG of course prerequisites:

     (Calc1)--->(Calc2)--->(Calc3)
                  |
                  v
     (CS101)-->(CS201)--->(CS301)

    Valid topological orderings:
    Calc1, CS101, Calc2, CS201, Calc3, CS301
    CS101, Calc1, Calc2, CS201, CS301, Calc3
    (many valid orderings exist)

Kahn's Algorithm (BFS / Indegree Approach)

Pythonfrom collections import deque, defaultdict

def topological_sort_bfs(num_vertices, edges):
    """
    Kahn's algorithm for topological sort.
    edges: list of (u, v) meaning u must come before v.
    Returns: topological order, or [] if cycle exists.
    """
    graph = defaultdict(list)
    indegree = [0] * num_vertices

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

    # Start with all vertices that have no prerequisites
    queue = deque()
    for i in range(num_vertices):
        if indegree[i] == 0:
            queue.append(i)

    order = []
    while queue:
        vertex = queue.popleft()
        order.append(vertex)

        for neighbor in graph[vertex]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # If we processed all vertices, no cycle exists
    if len(order) == num_vertices:
        return order
    return []  # cycle detected!

# 0=Calc1, 1=Calc2, 2=Calc3, 3=CS101, 4=CS201, 5=CS301
edges = [(0,1), (1,2), (3,4), (1,4), (4,5)]
print(topological_sort_bfs(6, edges))
# [0, 3, 1, 4, 2, 5]

JavaScriptfunction topologicalSortBFS(numVertices, edges) {
  const graph = Array.from({ length: numVertices }, () => []);
  const indegree = new Array(numVertices).fill(0);

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

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

  const order = [];
  while (queue.length > 0) {
    const vertex = queue.shift();
    order.push(vertex);

    for (const neighbor of graph[vertex]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return order.length === numVertices ? order : [];
}

const edges = [[0,1], [1,2], [3,4], [1,4], [4,5]];
console.log(topologicalSortBFS(6, edges));
// [0, 3, 1, 4, 2, 5]

Topological Sort - DFS Approach

Pythondef topological_sort_dfs(num_vertices, edges):
    """Topological sort using DFS post-order."""
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = set()
    stack = []  # result in reverse order

    def dfs(v):
        visited.add(v)
        for neighbor in graph[v]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(v)  # add AFTER processing all descendants

    for v in range(num_vertices):
        if v not in visited:
            dfs(v)

    return stack[::-1]  # reverse the post-order

print(topological_sort_dfs(6, edges))
# [3, 0, 1, 4, 5, 2]

JavaScriptfunction topologicalSortDFS(numVertices, edges) {
  const graph = Array.from({ length: numVertices }, () => []);
  for (const [u, v] of edges) graph[u].push(v);

  const visited = new Set();
  const stack = [];

  function dfs(v) {
    visited.add(v);
    for (const neighbor of graph[v]) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
    stack.push(v);  // add AFTER all descendants
  }

  for (let v = 0; v < numVertices; v++) {
    if (!visited.has(v)) dfs(v);
  }

  return stack.reverse();
}

console.log(topologicalSortDFS(6, edges));
// [3, 0, 1, 4, 5, 2]

Union-Find / Disjoint Set (Brief)

A data structure for tracking disjoint sets. Supports two operations: find (which set does element belong to?) and union (merge two sets). Optimized with path compression and union by rank.

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

    def find(self, x):
        """Find root with path compression."""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        """Union by rank. Returns True if merged."""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already same set (cycle!)
        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)

# Usage: detect cycles, count connected components
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(uf.connected(0, 1))  # True
print(uf.connected(0, 2))  # False
print(uf.components)        # 3
uf.union(1, 3)
print(uf.connected(0, 2))  # True (0-1-3-2)
print(uf.components)        # 2

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

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

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

  connected(x, y) {
    return this.find(x) === this.find(y);
  }
}

For more on Union-Find and advanced graph algorithms, see the Advanced page.

5. Cycle Detection

Undirected Graph - DFS with Parent Tracking

In an undirected graph, if we visit a neighbor that is already visited AND it is not the parent of the current node, we have found a cycle.

Pythondef has_cycle_undirected(graph, num_vertices):
    """Detect cycle in undirected graph using DFS."""
    visited = set()

    def dfs(vertex, parent):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor, vertex):
                    return True
            elif neighbor != parent:
                return True  # cycle found!
        return False

    # Check all components (disconnected graph)
    for v in range(num_vertices):
        if v not in visited:
            if dfs(v, -1):
                return True
    return False

# Has cycle: 0-1-2-0
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
print(has_cycle_undirected(graph, 3))  # True

# No cycle
graph = {0: [1], 1: [0, 2], 2: [1]}
print(has_cycle_undirected(graph, 3))  # False

Directed Graph - Three-Color Marking (White/Gray/Black)

For directed graphs, parent tracking is not enough. We use three states:

• White (0): Not visited yet
• Gray (1): Currently being processed (in the recursion stack)
• Black (2): Completely processed (all descendants finished)

A cycle exists if we encounter a gray node — that means we have found a back edge to an ancestor still being processed.

    Why parent tracking fails for directed graphs:

        (A)--->(B)
               |
               v
        (C)--->(D)

    A->B->D is fine. C->D is NOT a cycle, just another path to D.
    But with parent tracking, D looks "already visited" from C.
    Three-color fixes this: D is BLACK (done), not GRAY (in progress).

PythonWHITE, GRAY, BLACK = 0, 1, 2

def has_cycle_directed(graph, num_vertices):
    """Detect cycle in directed graph using 3-color DFS."""
    color = [WHITE] * num_vertices

    def dfs(vertex):
        color[vertex] = GRAY  # mark as in-progress

        for neighbor in graph.get(vertex, []):
            if color[neighbor] == GRAY:
                return True   # back edge = cycle!
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True

        color[vertex] = BLACK  # mark as done
        return False

    for v in range(num_vertices):
        if color[v] == WHITE:
            if dfs(v):
                return True
    return False

# Cycle: 0->1->2->0
graph = {0: [1], 1: [2], 2: [0]}
print(has_cycle_directed(graph, 3))  # True

# No cycle (DAG)
graph = {0: [1], 1: [2], 2: []}
print(has_cycle_directed(graph, 3))  # False

6. LeetCode Problems

200. Number of Islands - Full Solution

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

    Input:                     Islands = 3
    1 1 0 0 0                  X X . . .
    1 1 0 0 0                  X X . . .
    0 0 1 0 0      --->        . . X . .
    0 0 0 1 1                  . . . X X

Python - BFSfrom collections import deque

def numIslands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()
    islands = 0

    def bfs(r, c):
        queue = deque([(r, c)])
        visited.add((r, c))

        while queue:
            row, col = queue.popleft()
            # Check all 4 directions: right, left, down, up
            for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
                nr, nc = row + dr, col + dc
                if (0 <= nr < rows and
                    0 <= nc < cols and
                    grid[nr][nc] == "1" and
                    (nr, nc) not in visited):
                    visited.add((nr, nc))
                    queue.append((nr, nc))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visited:
                bfs(r, c)
                islands += 1

    return islands

# Time: O(M * N)  |  Space: O(M * N)

grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"],
]
print(numIslands(grid))  # 3

Python - DFS (alternative)def numIslands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    islands = 0

    def dfs(r, c):
        # Base case: out of bounds or water
        if (r < 0 or r >= rows or
            c < 0 or c >= cols or
            grid[r][c] != "1"):
            return

        grid[r][c] = "#"  # mark as visited (sink the island)
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                dfs(r, c)
                islands += 1

    return islands

JavaScript - BFSfunction numIslands(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const visited = new Set();
  let islands = 0;

  const directions = [[0,1], [0,-1], [1,0], [-1,0]];

  function bfs(r, c) {
    const queue = [[r, c]];
    visited.add(`${r},${c}`);

    while (queue.length > 0) {
      const [row, col] = queue.shift();

      for (const [dr, dc] of directions) {
        const nr = row + dr;
        const nc = col + dc;
        const key = `${nr},${nc}`;

        if (nr >= 0 && nr < rows &&
            nc >= 0 && nc < cols &&
            grid[nr][nc] === "1" &&
            !visited.has(key)) {
          visited.add(key);
          queue.push([nr, nc]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1" && !visited.has(`${r},${c}`)) {
        bfs(r, c);
        islands++;
      }
    }
  }

  return islands;
}

// Time: O(M * N)  |  Space: O(M * N)

JavaScript - DFS (alternative)function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let islands = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") {
      return;
    }
    grid[r][c] = "#";  // mark visited
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1") {
        dfs(r, c);
        islands++;
      }
    }
  }

  return islands;
}

207. Course Schedule - Full Solution

There are numCourses courses labeled 0 to numCourses-1. Some have prerequisites: prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses (no circular dependency).

    Input: numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
        0 -> 1 -> 2 -> 3    (take 0 first, then 1, then 2, then 3)
        Output: true

        Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
        0 -> 1 -> 0          (circular dependency!)
        Output: false

Python - Kahn's Algorithm (BFS)from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    """Can all courses be completed? (No cycles in prereq graph)"""
    graph = defaultdict(list)
    indegree = [0] * numCourses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    # Start with courses that have no prerequisites
    queue = deque()
    for i in range(numCourses):
        if indegree[i] == 0:
            queue.append(i)

    completed = 0
    while queue:
        course = queue.popleft()
        completed += 1

        for next_course in graph[course]:
            indegree[next_course] -= 1
            if indegree[next_course] == 0:
                queue.append(next_course)

    return completed == numCourses

# Time: O(V + E)  |  Space: O(V + E)

print(canFinish(4, [[1,0],[2,1],[3,2]]))  # True
print(canFinish(2, [[1,0],[0,1]]))        # False

Python - DFS Cycle Detectiondef canFinish(numCourses, prerequisites):
    """DFS approach with 3-color marking."""
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # 0 = unvisited, 1 = in progress, 2 = done
    state = [0] * numCourses

    def has_cycle(course):
        if state[course] == 1:
            return True   # cycle!
        if state[course] == 2:
            return False  # already processed

        state[course] = 1  # mark in progress

        for next_course in graph[course]:
            if has_cycle(next_course):
                return True

        state[course] = 2  # mark done
        return False

    for course in range(numCourses):
        if has_cycle(course):
            return False

    return True

JavaScript - Kahn's Algorithm (BFS)function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    indegree[course]++;
  }

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

  let completed = 0;
  while (queue.length > 0) {
    const course = queue.shift();
    completed++;

    for (const next of graph[course]) {
      indegree[next]--;
      if (indegree[next] === 0) queue.push(next);
    }
  }

  return completed === numCourses;
}

// Time: O(V + E)  |  Space: O(V + E)

console.log(canFinish(4, [[1,0],[2,1],[3,2]]));  // true
console.log(canFinish(2, [[1,0],[0,1]]));        // false

JavaScript - DFS Cycle Detectionfunction canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }

  // 0 = unvisited, 1 = in progress, 2 = done
  const state = new Array(numCourses).fill(0);

  function hasCycle(course) {
    if (state[course] === 1) return true;   // cycle!
    if (state[course] === 2) return false;  // done

    state[course] = 1;

    for (const next of graph[course]) {
      if (hasCycle(next)) return true;
    }

    state[course] = 2;
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }

  return true;
}

7. Practice Quiz