08-graphs.md

Module 08: Graphs — Traversals, TopoSort, Shortest Paths & MST

Goal: Master graph representations, BFS/DFS traversals, multi-source BFS, 3-state cycle detection, Kahn's Topological Sort, Dijkstra's, Bellman-Ford, Floyd-Warshall, and Minimum Spanning Trees (Kruskal & Prim).
Language: C++ (C++17/C++20)
Prerequisites: Modules 01 to 07.

📑 Table of Contents

  1. Under the Hood: Graph Representations & Memory Layout
  2. Graph Traversals: BFS, Multi-Source BFS & DFS
  3. Cycle Detection Mechanics (Directed vs Undirected)
  4. Topological Sorting (Kahn's Algorithm & DFS)
  5. Shortest Path Algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS)
  6. Minimum Spanning Trees (Kruskal's & Prim's)
  7. Bipartite Graphs & 2-Coloring
  8. 6 Practice Problems with Detailed Solutions
  9. Top 10 FAANG Interview Questions

1. Under the Hood: Graph Representations & Memory Layout

A Graph $G = (V, E)$ consists of vertices $V$ and edges $E$.

Graph: (0) ───[weight 4]───► (1) │ │ [2] [3] ▼ ▼ (2) ◄──[weight 1]──── (3)

1.1 Comparison of Graph Storage Models

FeatureAdjacency Matrix (vector<vector<int>>)Adjacency List (vector<vector<pair<int,int>>>)Edge List (vector<Edge>)
Space Complexity$O(V^2)$$O(V + E)$ (Optimal for sparse graphs)$O(E)$
Edge Existence Query $(u, v)$$O(1)$$O(\text{deg}(u))$$O(E)$
Iterate Neighbors of $u$$O(V)$$O(\text{deg}(u))$$O(E)$
Best ForDense graphs ($E \approx V^2$)Sparse graphs ($E \ll V^2$, 99% of interview problems)Kruskal's MST, Bellman-Ford

1.2 C++ Adjacency List Definition

#include <vector> // Weighted Directed Graph: adj[u] contains pairs {v, weight} using WeightedGraph = std::vector<std::vector<std::pair<int, int>>>;

2. Graph Traversals: BFS, Multi-Source BFS & DFS

2.1 Breadth-First Search (Shortest Path in Unweighted Graphs)

#include <vector> #include <queue> void bfs(int startNode, const std::vector<std::vector<int>>& adj, std::vector<int>& dist) { int n = adj.size(); dist.assign(n, -1); std::queue<int> q; dist[startNode] = 0; q.push(startNode); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] == -1) { // Unvisited dist[v] = dist[u] + 1; q.push(v); } } } } // Time Complexity: O(V + E) // Space Complexity: O(V)

2.2 Multi-Source BFS Pattern (Rotting Oranges, Distance to 0)

Push all source nodes simultaneously into the queue at $t = 0$ with dist[src] = 0. BFS expands outward in concentric rings, computing the minimum distance from any source.

3. Cycle Detection Mechanics (Directed vs Undirected)

3.1 Undirected Graph Cycle Detection (DFS with Parent Tracker)

bool dfsUndirectedCycle(int u, int parent, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) { if (dfsUndirectedCycle(v, u, adj, visited)) return true; } else if (v != parent) { return true; // Visited neighbor that is not parent -> Cycle detected! } } return false; }

3.2 Directed Graph Cycle Detection (3-Coloring / Recursion Stack)

  • 0 (WHITE): Unvisited.
  • 1 (GRAY): Currently being visited (in the active recursion call stack).
  • 2 (BLACK): Completely visited and all descendants processed.
bool dfsDirectedCycle(int u, const std::vector<std::vector<int>>& adj, std::vector<int>& color) { color[u] = 1; // Mark GRAY (in stack) for (int v : adj[u]) { if (color[v] == 1) return true; // Back-edge found -> Cycle! if (color[v] == 0 && dfsDirectedCycle(v, adj, color)) return true; } color[u] = 2; // Mark BLACK (finished) return false; }

4. Topological Sorting (Kahn's Algorithm & DFS)

A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $u \to v$, $u$ comes before $v$.

4.1 Kahn's Algorithm (In-Degree BFS)

std::vector<int> kahnsTopoSort(int numCourses, const std::vector<std::vector<int>>& adj) { std::vector<int> inDegree(numCourses, 0); for (int u = 0; u < numCourses; ++u) { for (int v : adj[u]) inDegree[v]++; } std::queue<int> q; for (int i = 0; i < numCourses; ++i) { if (inDegree[i] == 0) q.push(i); } std::vector<int> topoOrder; while (!q.empty()) { int u = q.front(); q.pop(); topoOrder.push_back(u); for (int v : adj[u]) { inDegree[v]--; if (inDegree[v] == 0) q.push(v); } } // If order size < numCourses, a cycle exists (not a DAG)! if (topoOrder.size() != numCourses) return {}; return topoOrder; } // Time Complexity: O(V + E) // Space Complexity: O(V + E)

5. Shortest Path Algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS)

┌─────────────────┬──────────────────────┬────────────────────────┬──────────────────────────────────────────┐ │ Algorithm │ Time Complexity │ Space Complexity │ Graph Type & Constraints │ ├─────────────────┼──────────────────────┼────────────────────────┼──────────────────────────────────────────┤ │ BFS │ O(V + E) │ O(V) │ Unweighted edges only │ │ 0-1 BFS (Deque) │ O(V + E) │ O(V) │ Edge weights only 0 or 1 │ │ Dijkstra │ O((V + E) log V) │ O(V) │ Non-negative edge weights │ │ Bellman-Ford │ O(V · E) │ O(V) │ Negative edge weights & cycle detection │ │ Floyd-Warshall │ O(V³) │ O(V²) │ All-pairs shortest paths (Dense graphs) │ └─────────────────┴──────────────────────┴────────────────────────┴──────────────────────────────────────────┘

5.1 Dijkstra's Algorithm Implementation

#include <vector> #include <queue> std::vector<int> dijkstra(int startNode, int n, const std::vector<std::vector<std::pair<int, int>>>& adj) { const int INF = 1e9; std::vector<int> dist(n, INF); // Min-Heap storing pair: (distance, node) std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq; dist[startNode] = 0; pq.push({0, startNode}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); // Skip stale pairs if (d > dist[u]) continue; for (const auto& [v, weight] : adj[u]) { if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } return dist; }

6. Minimum Spanning Trees (Kruskal's & Prim's)

A Minimum Spanning Tree (MST) connects all $V$ vertices in an undirected graph with $V - 1$ edges having minimum total weight without forming cycles.

// Kruskal's Algorithm with DSU struct Edge { int u, v, weight; bool operator<(const Edge& other) const { return weight < other.weight; } }; struct DSU { std::vector<int> parent, rank; DSU(int n) : parent(n), rank(n, 0) { for (int i = 0; i < n; ++i) parent[i] = i; } int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); // Path compression } bool unite(int i, int j) { int rootI = find(i), rootJ = find(j); if (rootI != rootJ) { if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ); parent[rootJ] = rootI; if (rank[rootI] == rank[rootJ]) rank[rootI]++; return true; } return false; } }; int kruskalMST(int n, std::vector<Edge>& edges) { std::sort(edges.begin(), edges.end()); DSU dsu(n); int mstWeight = 0, edgesCount = 0; for (const auto& edge : edges) { if (dsu.unite(edge.u, edge.v)) { mstWeight += edge.weight; edgesCount++; if (edgesCount == n - 1) break; } } return (edgesCount == n - 1) ? mstWeight : -1; }

7. Bipartite Graphs & 2-Coloring

A graph is Bipartite if its vertices can be partitioned into two disjoint sets such that no two graph neighbors share the same set.
Theorem: A graph is bipartite if and only if it contains no odd-length cycles.

8. 6 Practice Problems with Detailed Solutions

Problem 1: Course Schedule II (LeetCode #210 - Medium)

Problem: Return the ordering of courses you should take to finish all courses given prerequisite pairs.

#include <vector> #include <queue> std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites) { std::vector<std::vector<int>> adj(numCourses); std::vector<int> inDegree(numCourses, 0); for (const auto& pre : prerequisites) { adj[pre[1]].push_back(pre[0]); inDegree[pre[0]]++; } std::queue<int> q; for (int i = 0; i < numCourses; ++i) { if (inDegree[i] == 0) q.push(i); } std::vector<int> order; while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (int v : adj[u]) { inDegree[v]--; if (inDegree[v] == 0) q.push(v); } } return (order.size() == numCourses) ? order : std::vector<int>{}; } // Time: O(V + E), Space: O(V + E)

Problem 2: Word Ladder (LeetCode #127 - Hard)

Problem: Return the minimum number of words in the shortest transformation sequence from beginWord to endWord changing one letter at a time.

#include <string> #include <vector> #include <unordered_set> #include <queue> int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) { std::unordered_set<std::string> dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return 0; std::queue<std::pair<std::string, int>> q; q.push({beginWord, 1}); dict.erase(beginWord); while (!q.empty()) { auto [word, length] = q.front(); q.pop(); if (word == endWord) return length; for (int i = 0; i < word.length(); ++i) { char originalChar = word[i]; for (char c = 'a'; c <= 'z'; ++c) { word[i] = c; if (dict.count(word)) { q.push({word, length + 1}); dict.erase(word); // Mark visited } } word[i] = originalChar; } } return 0; } // Time Complexity: O(M^2 * N) where M = word length, N = dictionary size // Space Complexity: O(M * N)

Problem 3: Network Delay Time (LeetCode #743 - Medium)

Problem: Given travel times as directed edges, return minimum time for all $N$ nodes to receive signal.

#include <vector> #include <queue> #include <algorithm> int networkDelayTime(std::vector<std::vector<int>>& times, int n, int k) { std::vector<std::vector<std::pair<int, int>>> adj(n + 1); for (const auto& t : times) { adj[t[0]].push_back({t[1], t[2]}); } std::vector<int> dist(n + 1, 1e9); std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq; dist[k] = 0; pq.push({0, k}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dist[u]) continue; for (const auto& [v, w] : adj[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } int maxTime = 0; for (int i = 1; i <= n; ++i) { if (dist[i] == 1e9) return -1; maxTime = std::max(maxTime, dist[i]); } return maxTime; } // Time Complexity: O(E log V) // Space Complexity: O(V + E)

Problem 4: Number of Islands (LeetCode #200 - Medium)

Problem: Given an $m \times n$ 2D binary grid, return the number of islands.

#include <vector> void dfsGrid(std::vector<std::vector<char>>& grid, int r, int c) { int rows = grid.size(), cols = grid[0].size(); if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return; grid[r][c] = '0'; // Sink island in-place dfsGrid(grid, r + 1, c); dfsGrid(grid, r - 1, c); dfsGrid(grid, r, c + 1); dfsGrid(grid, r, c - 1); } int numIslands(std::vector<std::vector<char>>& grid) { if (grid.empty()) return 0; int count = 0; for (int r = 0; r < grid.size(); ++r) { for (int c = 0; c < grid[0].size(); ++c) { if (grid[r][c] == '1') { count++; dfsGrid(grid, r, c); } } } return count; } // Time Complexity: O(R * C) // Space Complexity: O(R * C) call stack

Problem 5: Is Graph Bipartite? (LeetCode #785 - Medium)

#include <vector> #include <queue> bool isBipartite(std::vector<std::vector<int>>& graph) { int n = graph.size(); std::vector<int> color(n, 0); // 0: uncolored, 1: blue, -1: red for (int i = 0; i < n; ++i) { if (color[i] != 0) continue; std::queue<int> q; q.push(i); color[i] = 1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (color[v] == 0) { color[v] = -color[u]; // Alternate color q.push(v); } else if (color[v] == color[u]) { return false; // Same color neighbor -> Odd cycle! } } } } return true; } // Time Complexity: O(V + E) // Space Complexity: O(V)

Problem 6: Alien Dictionary (LeetCode #269 - Hard)

#include <string> #include <vector> #include <unordered_map> #include <unordered_set> #include <queue> std::string alienOrder(std::vector<std::string>& words) { std::unordered_map<char, std::unordered_set<char>> adj; std::unordered_map<char, int> inDegree; for (const auto& w : words) { for (char c : w) inDegree[c] = 0; } for (size_t i = 0; i < words.size() - 1; ++i) { const std::string& w1 = words[i]; const std::string& w2 = words[i + 1]; if (w1.length() > w2.length() && w1.substr(0, w2.length()) == w2) return ""; for (size_t j = 0; j < std::min(w1.length(), w2.length()); ++j) { if (w1[j] != w2[j]) { if (!adj[w1[j]].count(w2[j])) { adj[w1[j]].insert(w2[j]); inDegree[w2[j]]++; } break; } } } std::queue<char> q; for (auto& [c, deg] : inDegree) { if (deg == 0) q.push(c); } std::string result = ""; while (!q.empty()) { char u = q.front(); q.pop(); result += u; for (char v : adj[u]) { if (--inDegree[v] == 0) q.push(v); } } return (result.length() == inDegree.size()) ? result : ""; }

9. Top 10 FAANG Interview Questions

Q1: Why does Dijkstra's Algorithm fail on graphs with negative edge weights?

Answer: Dijkstra is a greedy algorithm that assumes once a node is popped from the priority queue, its shortest distance is finalized and will never be improved. A negative edge encountered later could lower the distance to an already-settled node, violating the greedy invariant and leading to incorrect results or infinite loops.

Q2: How does the Bellman-Ford algorithm detect negative cycles?

Answer: In a graph with $V$ vertices and no negative cycles, any shortest simple path contains at most $V - 1$ edges. Bellman-Ford relaxes all edges $V - 1$ times. If a $V$-th relaxation is performed and any distance decreases (dist[u] + w < dist[v]), there must exist a negative cycle reachable from the source.

Q3: What is the difference between Kahn's algorithm and DFS for Topological Sorting?

Answer:

  • Kahn's: BFS-based, maintains in-degrees. Naturally detects cycles (if final sorted array size $< V$).
  • DFS: Post-order traversal with reverse. Requires a separate 3-color visited state to detect cycles before reversing the output list.

Q4: When is 0-1 BFS preferred over Dijkstra's Algorithm?

Answer: When graph edge weights are restricted to only ${0, 1}$. By using std::deque (push weight-0 edges to the front and weight-1 edges to the back), vertices remain naturally sorted by distance. Time complexity drops from $O(E \log V)$ to $O(V + E)$ linear time.

Q5: How do you find the Bridges and Articulation Points in a Graph?

Answer: Using Tarjan's Bridge-Finding Algorithm ($O(V + E)$). Maintain tin[u] (discovery time) and low[u] (lowest discovery time reachable via back-edges). An edge $(u, v)$ is a Bridge if low[v] > tin[u].

Q6: What is the difference between Prim's and Kruskal's MST algorithms?

Answer:

  • Kruskal's: Edge-centric. Sorts all edges and uses DSU to build spanning forest. Better for sparse graphs ($O(E \log E)$).
  • Prim's: Vertex-centric. Grows a single tree outwards from a root using a priority queue. Better for dense graphs ($O(V^2)$ or $O(E \log V)$).

Q7: Can a DAG have more than one valid Topological Order?

Answer: Yes. If at any point during Kahn's algorithm the queue contains more than 1 vertex with in-degree 0, those vertices can be ordered arbitrarily, yielding multiple valid topological sorts. If the queue always contains exactly 1 vertex at every step, the topological sort is unique (Hamiltonian Path exists).

Q8: What is a Strongly Connected Component (SCC)?

Answer: A maximal subgraph of a directed graph where every vertex is reachable from every other vertex within the component. Found in $O(V + E)$ using Kosaraju's Algorithm (2 DFS passes + graph transpose) or Tarjan's SCC Algorithm (single DFS + stack).

Q9: How do you solve All-Pairs Shortest Path for sparse graphs faster than Floyd-Warshall $O(V^3)$?

Answer: Johnson's Algorithm: Uses Bellman-Ford once to reweight all edges to non-negative values ($w'(u,v) = w(u,v) + h(u) - h(v)$), then runs Dijkstra from every vertex. Total time: $O(V \cdot E \log V)$, which is much faster than $O(V^3)$ when $E \ll V^2$.

Q10: How do you detect bipartite components in an unconnected graph?

Answer: Loop through all vertices $0 \dots V-1$. Whenever an unvisited vertex is found, initiate 2-coloring BFS/DFS from that vertex to check its entire connected component.