🗺️ Graphs

One-line summary: Nodes connected by edges — BFS for shortest path, DFS for connectivity/cycle, topological sort for dependencies, Union-Find for dynamic connectivity.

---

Enhanced Visualization

Interactive demonstration of BFS, DFS, and Dijkstra's algorithm with path finding and performance analysis

Core Graph Concepts

The enhanced animation above demonstrates three fundamental graph algorithms:

🔵 Breadth-First Search (BFS)

• Strategy: Explores nodes level by level using a queue
• Path: A → B → C → F (shortest in unweighted graphs)
• Time: O(V + E) | Space: O(V)
• Use Cases: Shortest path, social networks, web crawling

🟣 Depth-First Search (DFS)

• Strategy: Explores as far as possible using recursion/stack
• Path: A → D → E → F (explores deeply first)
• Time: O(V + E) | Space: O(V)
• Use Cases: Topological sorting, cycle detection, connectivity

🟡 Dijkstra's Algorithm

• Strategy: Uses priority queue for weighted shortest paths
• Path: A → B → E → F (Distance: 7 - optimal weighted path)
• Time: O((V + E) log V) | Space: O(V)
• Use Cases: GPS navigation, network routing, flight planning

Graph Fundamentals

G = (V, E). Types: directed, undirected, weighted, DAG.

Representations:

• Adjacency List: Map<node, neighbors[]> — O(V+E) space — preferred.
• Adjacency Matrix: matrix[u][v] — O(V²) — dense graphs.

Also covers: BFS pattern, DFS pattern, topological sort, Union-Find, Dijkstra, Bellman-Ford.

---

Time & Space Complexity

Algorithm	Time	Space
BFS / DFS	O(V + E)	O(V)
Dijkstra (min-heap)	O((V+E) log V)	O(V)
Topological Sort (Kahn)	O(V + E)	O(V)
Union-Find (with compression)	O(α(n)) per op	O(n)

---

Common Patterns

BFS (Shortest Path)

function bfs(graph, start) {
  const visited = new Set([start]),
    queue = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const nb of graph.get(node) || [])
      if (!visited.has(nb)) {
        visited.add(nb);
        queue.push(nb);
      }
  }
}

DFS (Connected Components)

function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  for (const nb of graph.get(node) || []) if (!visited.has(nb)) dfs(graph, nb, visited);
}

Topological Sort (Kahn's BFS)

function topoSort(n, edges) {
  const inDeg = new Array(n).fill(0),
    adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[b].push(a);
    inDeg[a]++;
  }
  const queue = [],
    order = [];
  for (let i = 0; i < n; i++) if (!inDeg[i]) queue.push(i);
  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const nb of adj[node]) if (--inDeg[nb] === 0) queue.push(nb);
  }
  return order.length === n ? order : []; // empty = cycle
}

Union-Find

const parent = Array.from({ length: n }, (_, i) => i);
function find(x) {
  return parent[x] === x ? x : (parent[x] = find(parent[x]));
}
function union(x, y) {
  parent[find(x)] = find(y);
}

---

Pitfalls

• Forgetting to mark visited before enqueuing (BFS) — causes duplicates
• Cycle detection: in undirected graph pass parent to DFS to avoid false positives
• Topological sort only valid on DAG — if cycle exists, output length < n

---

Practice Problems

Problem	Difficulty	Solution
LC 200 — Number of Islands	Medium
LC 207 — Course Schedule	Medium
LC 210 — Course Schedule II	Medium
LC 323 — Number of Connected Components	Medium
LC 127 — Word Ladder	Hard
LC 743 — Network Delay Time (Dijkstra)	Medium
LC 684 — Redundant Connection (Union-Find)	Medium
CC — Grid Escape (GRIDECP)	Medium
CC — Dijkstra (DIJKST)	Hard
LC 1584 — Min Cost to Connect All Points	Medium
LC 787 — Cheapest Flights Within K Stops	Medium
LC 133 — Clone Graph	Medium
LC 695 — Max Area of Island	Medium
LC 130 — Surrounded Regions	Medium
LC 417 — Pacific Atlantic Water Flow	Medium
LC 547 — Number of Provinces	Medium
LC 1020 — Number of Enclaves	Medium
LC 1905 — Count Sub Islands	Medium
LC 797 — All Paths From Source to Target	Medium
LC 785 — Is Graph Bipartite?	Medium
LC 886 — Possible Bipartition	Medium
LC 399 — Evaluate Division	Medium
LC 1319 — Number of Operations to Make Network Connected	Medium
LC 1466 — Reorder Routes to Make All Paths Lead to Zero	Medium
LC 1557 — Minimum Number of Vertices to Reach All Nodes	Medium
CC — Chef and Graph Queries (CHEFGRAPH)	Hard
CC — Roads and Libraries (ROADS)	Medium
CC — Shortest Path (SHORTPATH)	Medium

---

Related Topics

• Trees — trees are acyclic connected graphs
• Heap — Dijkstra requires min-heap
• Dynamic Programming — DP on DAGs

← Back to Home · © sparshjaswal