Graphs in Data Structures

What is a Graph?

A Graph is a non-linear data structure that models relationships between objects. Unlike arrays or linked lists which are sequential, a graph captures many-to-many relationships — each element (called a vertex or node) can connect to any number of other vertices through edges.

Graphs are the most powerful and general-purpose data structure in computer science. If you understand graphs, you understand the foundation of:

• How Google ranks web pages (PageRank)
• How GPS finds your fastest route (Dijkstra's algorithm)
• How social networks suggest friends (BFS on friend graphs)
• How compilers resolve dependencies (Topological Sort)

Example Graph (Social Network):
   Alice ──── Bob
     │          │
     │          │
   Carol ──── Dave ──── Eve

Alice is connected to Bob and Carol.
Bob is connected to Alice and Dave.
Dave is connected to Bob, Carol, and Eve.

Types of Graphs

1. Directed vs. Undirected

Undirected (friendship):     Directed (follows on Twitter):
  A ──── B                     A ──→ B
  A ──── C                     B ──→ C (B follows C, but C doesn't follow B)

2. Weighted vs. Unweighted

Weighted (road distances):   Unweighted:
  A ──5── B                    A ──── B
  A ──3── C                    A ──── C
  B ──2── C                    B ──── C

3. Cyclic vs. Acyclic

• Cyclic Graph: Contains at least one cycle (A → B → C → A)
• DAG (Directed Acyclic Graph): No cycles — used for task dependencies, build systems

Graph Representations

Adjacency List (Preferred for Sparse Graphs)

Graph: 0──1, 0──2, 1──3, 2──3

Adjacency List:
0 → [1, 2]
1 → [0, 3]
2 → [0, 3]
3 → [1, 2]

JavaScript:

javascript
// Building an undirected graph with adjacency list
function buildGraph(n, edges) {
    const graph = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);  // undirected: add both directions
    }
    return graph;
}

const g = buildGraph(4, [[0,1],[0,2],[1,3],[2,3]]);
// g = [[1,2], [0,3], [0,3], [1,2]]

Python:

python
from collections import defaultdict

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

C++:

cpp
#include <vector>
using namespace std;

vector<vector<int>> buildGraph(int n, vector<pair<int,int>>& edges) {
    vector<vector<int>> graph(n);
    for (auto& [u, v] : edges) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    return graph;
}

Adjacency Matrix (Preferred for Dense Graphs)

Graph: 0──1, 0──2, 1──3, 2──3

Matrix (row i, col j = 1 if edge i→j exists):
   0  1  2  3
0 [0, 1, 1, 0]
1 [1, 0, 0, 1]
2 [1, 0, 0, 1]
3 [0, 1, 1, 0]

Complexity Comparison

Rule of thumb: Use adjacency list for sparse graphs (E << V²), matrix for dense graphs.

Algorithm 1: Breadth-First Search (BFS)

BFS explores the graph level by level using a queue. It finds the shortest path (in terms of number of edges) in unweighted graphs.

BFS from node 0:
Graph: 0──1, 0──2, 1──3, 2──4

Level 0: [0]
Level 1: [1, 2]      ← neighbors of 0
Level 2: [3, 4]      ← neighbors of 1 and 2

Implementation:

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

    while (queue.length > 0) {
        const node = queue.shift();   // dequeue from front
        order.push(node);

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

Python:

python
from collections import deque

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

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

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

    return order

🟢 Solved Problem 1: Number of Islands (BFS)

Problem: 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:

grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]

Output: 3

Approach: For each unvisited land cell '1', run BFS to mark all connected land cells as visited. Each BFS call = one island.

Dry-Run Trace:

Start at (0,0)='1': BFS marks (0,0),(0,1),(1,0),(1,1) → island #1
Find next unvisited '1' at (2,2): BFS marks (2,2) → island #2  
Find next unvisited '1' at (3,3): BFS marks (3,3),(3,4) → island #3
Answer: 3 islands

JavaScript Solution:

javascript
function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;
    const rows = grid.length;
    const cols = grid[0].length;
    let islands = 0;

    function bfs(r, c) {
        const queue = [[r, c]];
        grid[r][c] = '0';  // mark visited by sinking the island

        while (queue.length > 0) {
            const [row, col] = queue.shift();
            const directions = [[1,0],[-1,0],[0,1],[0,-1]];
            for (const [dr, dc] of directions) {
                const nr = row + dr;
                const nc = col + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
                    grid[nr][nc] = '0';
                    queue.push([nr, nc]);
                }
            }
        }
    }

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

    return islands;
}

// Test
console.log(numIslands([
    ['1','1','0','0'],
    ['1','1','0','0'],
    ['0','0','1','0'],
    ['0','0','0','1']
])); // Output: 3

Time: O(M × N) — every cell visited once
Space: O(min(M, N)) — max queue size is the shorter dimension

Algorithm 2: Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It naturally uses recursion (the call stack acts as an implicit stack).

DFS from node 0:
Graph: 0──1──3
       │
       2──4

Path: 0 → 1 → 3 (backtrack) → 0 → 2 → 4

Implementation:

javascript
function dfs(graph, node, visited = new Set()) {
    visited.add(node);
    console.log(node);  // process current node

    for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
    return visited;
}

Iterative DFS (using explicit stack):

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

    while (stack.length > 0) {
        const node = stack.pop();  // pop from back
        if (visited.has(node)) continue;
        visited.add(node);
        order.push(node);
        for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) stack.push(neighbor);
        }
    }
    return order;
}

🟡 Solved Problem 2: Course Schedule (Cycle Detection with DFS)

Problem: You have numCourses courses (0 to n-1). Given a list of prerequisites[i] = [a, b] (to take course a, you must first take b), determine if you can finish all courses.

Why it's a graph problem: Build a directed graph where b → a (b is prerequisite of a). If this directed graph has a cycle, it's impossible (deadlock). Return false if cycle exists.

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true (no cycles — all courses can be completed)

Approach: DFS with 3 states per node:

• 0 = unvisited
• 1 = currently in DFS path (gray — in-progress)
• 2 = fully processed (black — done)

If we reach a node that is 1 (gray), we found a back-edge → cycle!

JavaScript Solution:

javascript
function canFinish(numCourses, prerequisites) {
    // Build adjacency list
    const graph = Array.from({ length: numCourses }, () => []);
    for (const [course, prereq] of prerequisites) {
        graph[prereq].push(course);
    }

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

    function hasCycle(node) {
        if (state[node] === 1) return true;   // back-edge → cycle!
        if (state[node] === 2) return false;  // already fully processed

        state[node] = 1;  // mark as in-progress (gray)

        for (const neighbor of graph[node]) {
            if (hasCycle(neighbor)) return true;
        }

        state[node] = 2;  // mark as done (black)
        return false;
    }

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

    return true;
}

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

Python Solution:

python
def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # 0=unvisited, 1=visiting, 2=done
    state = [0] * num_courses

    def has_cycle(node):
        if state[node] == 1: return True
        if state[node] == 2: return False

        state[node] = 1
        for neighbor in graph[node]:
            if has_cycle(neighbor):
                return True
        state[node] = 2
        return False

    return not any(has_cycle(i) for i in range(num_courses))

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

Algorithm 3: Dijkstra's Shortest Path

Dijkstra's algorithm finds the shortest path from a source to all other vertices in a weighted graph with non-negative edges.

Core Idea: Greedily pick the unvisited vertex with the smallest known distance, then relax all its neighbors.

Graph (weighted):
  0 ──2── 1
  │       │
  6       3
  │       │
  2 ──1── 3

Shortest paths from 0:
  0→0: 0
  0→1: 2
  0→3: 5  (via 0→1→3)
  0→2: 6  (direct), but 0→1→3→2: 2+3+1=6 same

JavaScript (using Min Heap via sorted array — interview-style):

javascript
function dijkstra(graph, start) {
    const n = graph.length;
    const dist = new Array(n).fill(Infinity);
    dist[start] = 0;

    // Min-heap: [distance, node]
    const minHeap = [[0, start]];

    while (minHeap.length > 0) {
        // Sort to simulate min-heap (use proper PQ in production)
        minHeap.sort((a, b) => a[0] - b[0]);
        const [d, u] = minHeap.shift();

        if (d > dist[u]) continue;  // stale entry, skip

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

    return dist;
}

// graph[u] = [[v, weight], ...]
const g = [
    [[1, 2], [2, 6]],   // node 0
    [[0, 2], [3, 3]],   // node 1
    [[0, 6], [3, 1]],   // node 2
    [[1, 3], [2, 1]]    // node 3
];
console.log(dijkstra(g, 0)); // [0, 2, 6, 5]

🔴 Solved Problem 3: Network Delay Time (Dijkstra)

Problem: There are n network nodes labeled 1 to n. Given a list of travel times times[i] = [source, target, time], find the minimum time for all nodes to receive a signal sent from node k. If impossible, return -1.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
Output: 2

Network:
  1 ←1── 2 ──1→ 3 ──1→ 4

Signal from node 2:
  Node 2: 0ms (source)
  Node 1: 1ms (2→1)
  Node 3: 1ms (2→3)
  Node 4: 2ms (2→3→4)
  
Max time = 2ms

JavaScript:

javascript
function networkDelayTime(times, n, k) {
    // Build adjacency list
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [src, dst, time] of times) {
        graph[src].push([dst, time]);
    }

    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;
    const heap = [[0, k]];   // [distance, node]

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

        if (d > dist[u]) continue;

        for (const [v, w] of graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                heap.push([dist[v], v]);
            }
        }
    }

    const maxDist = Math.max(...dist.slice(1));  // ignore index 0
    return maxDist === Infinity ? -1 : maxDist;
}

console.log(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2)); // 2

Time: O((V + E) log V) Space: O(V + E)

Algorithm 4: Topological Sort

Topological sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge u → v, vertex u comes before v.

When to use: Task scheduling, build systems, course prerequisites, dependency resolution.

Kahn's Algorithm (BFS-based):

1. Compute in-degree for all nodes
2. Add all nodes with in-degree 0 to queue
3. While queue is not empty:
   a. Dequeue a node, add to result
   b. Decrease in-degree of all neighbors
   c. If any neighbor's in-degree becomes 0, enqueue it
4. If result has all nodes → valid topo sort. Else → cycle exists.

javascript
function topologicalSort(numNodes, edges) {
    const graph = Array.from({ length: numNodes }, () => []);
    const inDegree = new Array(numNodes).fill(0);

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

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

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

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

    return result.length === numNodes ? result : [];  // empty = cycle detected
}

// Example: tasks [0,1,2,3], 0 must before 1 and 2, 1 must before 3
console.log(topologicalSort(4, [[0,1],[0,2],[1,3],[2,3]]));
// Output: [0, 1, 2, 3] or [0, 2, 1, 3] (both valid)

Algorithm 5: Union-Find (Disjoint Set)

Union-Find efficiently tracks which nodes are in the same connected component. It's the fastest algorithm for detecting cycles in undirected graphs.

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]);  // path compression
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX === rootY) return false;  // already connected → cycle!

        // Union by rank
        if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
        } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
        } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        return true;
    }
}

// Detect cycle in undirected graph
function hasCycle(n, edges) {
    const uf = new UnionFind(n);
    for (const [u, v] of edges) {
        if (!uf.union(u, v)) return true;  // same component → cycle!
    }
    return false;
}

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

Time: Nearly O(1) per operation (amortized O(α(n)) — inverse Ackermann)

Complexity Reference

BFS vs DFS — When to Use Which?

Common Mistakes in Graph Problems

1. Forgetting to mark visited before enqueue (BFS): If you mark visited after dequeue, nodes get added to the queue multiple times, causing O(V²) time or infinite loops.

2. Not handling disconnected components: Always loop through all nodes (for i in range(n): if not visited[i]: bfs(i)) — a single BFS/DFS only covers one connected component.

3. Confusing directed and undirected: In undirected graphs, always add both directions graph[u].push(v); graph[v].push(u). In directed, only one direction.

4. Using wrong algorithm for negative weights: Dijkstra fails with negative edge weights. Use Bellman-Ford instead.

5. Off-by-one in grid BFS: Always check bounds 0 <= nr < rows && 0 <= nc < cols before accessing grid[nr][nc].

Real World Usages

• Google Maps / GPS Navigation: Dijkstra's algorithm on a weighted road network (vertices = intersections, edges = roads with travel times). A* adds a heuristic to speed this up.
• Social Network Friend Suggestions: BFS from your profile node — "people you may know" are nodes 2-3 hops away.
• Package Dependency Managers: npm, pip, Maven use topological sort to install packages in correct order — if circular dependencies exist, they throw an error (cycle detection).
• Google PageRank: Models the web as a directed graph. Pages with more inbound edges (backlinks) from high-PageRank pages rank higher.
• Airline Route Optimization: Minimize layovers or cost using Dijkstra on a graph where airports are vertices and flights are weighted edges.
• Fraud Detection: Banks model transaction patterns as graphs. Unusual cycles or clusters indicate potential fraud.

Common Interview Patterns

1. Island counting / flood fill: BFS/DFS on a 2D grid. "Number of Islands", "Max Area of Island"
2. Shortest path problems: BFS for unweighted, Dijkstra for weighted, Bellman-Ford for negative weights
3. Cycle detection: DFS with 3-state coloring for directed graphs, Union-Find for undirected
4. Topological sort problems: "Course Schedule", "Alien Dictionary", "Task Scheduler"
5. Connected components: DFS/BFS counting, Union-Find for dynamic connectivity
6. Bipartite graph check: BFS with 2-coloring — can you color the graph with 2 colors such that no two adjacent nodes share a color?
7. Minimum Spanning Tree: Kruskal's (with Union-Find) or Prim's algorithm

Frequently Asked Questions

Q: When should I use an adjacency matrix vs. adjacency list?
A: Use an adjacency matrix when the graph is dense (E ≈ V²) or when you need O(1) edge existence queries. Use an adjacency list for sparse graphs (most real-world graphs) because it uses O(V+E) space instead of O(V²) and iterating neighbors is proportional to actual degree instead of all vertices.

Q: What is a DAG and why does it matter?
A: A Directed Acyclic Graph (DAG) is a directed graph with no cycles. It matters because many real-world dependency problems (course prerequisites, build systems, data pipelines) are naturally DAGs. DAGs can be topologically sorted, which directed graphs with cycles cannot.

Q: How does Dijkstra's algorithm fail with negative edge weights?
A: Dijkstra's greedy assumption is that once a node's shortest distance is finalized, no shorter path exists. With negative edges, a later path through a negative edge could be shorter, breaking this assumption. Example: if there's a path 0→1 (weight 5) and 0→2→1 (weights 1, -10), Dijkstra might finalize node 1's distance as 5 before discovering the -9 path.

Q: What is the difference between connected and strongly connected components?
A: In an undirected graph, a connected component is a group where every node can reach every other. In a directed graph, a strongly connected component (SCC) requires that every node can reach every other following edge directions. Kosaraju's or Tarjan's algorithms find SCCs in O(V+E).

Q: Why does BFS guarantee the shortest path in unweighted graphs?
A: BFS explores nodes level by level — first all nodes at distance 1, then distance 2, and so on. Since it expands nodes in non-decreasing order of distance, the first time it reaches a target node, it's guaranteed that no shorter path (in terms of edges) exists. This property doesn't hold for DFS, which can take a very long path before finding the target.

Q: What is the time complexity of Dijkstra's algorithm?
A: With a binary min-heap (priority queue): O((V + E) log V). With a Fibonacci heap: O(E + V log V). With a simple array (no heap): O(V²) — suitable only for dense graphs. In competitive programming and interviews, the binary heap version is standard.