[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":93,"_73":94,"_35":95},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",38,"title","Graph Traversal","slug","algorithms-part-11-graph-traversal","excerpt","Learn graph representations (adjacency matrix/list), Depth-First Search, Breadth-First Search, cycle detection, and topological sorting fundamentals.","# Algorithms Compendium Part 11: Graph Representation & Traversal\n\nGraphs model relationships: social networks connect people, maps connect locations, dependencies connect tasks. This article covers the foundations: how to represent graphs efficiently and how to systematically explore them using Depth-First Search (DFS) and Breadth-First Search (BFS). These traversals are building blocks for shortest paths, cycle detection, topological sorting, and many other algorithms.\n\n## 📋 At a Glance\n\n| Representation | Space | Add Edge | Check Edge | Iterate Neighbors |\n|----------------|-------|----------|------------|-------------------|\n| Adjacency Matrix | O(V²) | O(1) | O(1) | O(V) |\n| Adjacency List | O(V+E) | O(1) | O(degree) | O(degree) |\n| Edge List | O(E) | O(1) | O(E) | O(E) |\n\n| Traversal | Time | Space | Best For |\n|-----------|------|-------|----------|\n| DFS | O(V+E) | O(V) | Cycle detection, topological sort, path finding |\n| BFS | O(V+E) | O(V) | Shortest path (unweighted), level-order traversal |\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Choose the right representation** based on graph density and operations\n- **Implement DFS** both recursively and iteratively\n- **Apply BFS** for shortest path in unweighted graphs\n- **Detect cycles** in directed and undirected graphs\n- **Perform topological sort** using DFS and Kahn's algorithm\n- **Recognize graph problems** disguised as other problems\n\n---\n\n## 🔥 Production Story: The Circular Dependency Disaster\n\nA build system managed 500+ microservices with complex dependencies. One day, a developer introduced a circular dependency, and the build hung indefinitely.\n\n```java\n// ❌ Initial build order calculation\npublic class BuildSystem {\n private final Map> dependencies;\n\n public List getBuildOrder() {\n List order = new ArrayList<>();\n Set built = new HashSet<>();\n\n for (String service : dependencies.keySet()) {\n build(service, built, order);\n }\n return order;\n }\n\n private void build(String service, Set built, List order) {\n if (built.contains(service)) return;\n\n // Build dependencies first\n for (String dep : dependencies.getOrDefault(service, List.of())) {\n build(dep, built, order); // No cycle detection!\n }\n\n built.add(service);\n order.add(service);\n }\n}\n// Circular dependency: A → B → C → A\n// Result: StackOverflowError or infinite loop!\n```\n\n**The problem:** No cycle detection. When A depends on B depends on C depends on A, the recursive build never terminates.\n\n**The solution:**\n\n```java\n// ✅ Build order with cycle detection\npublic class SafeBuildSystem {\n private final Map> dependencies;\n\n public List getBuildOrder() throws CyclicDependencyException {\n Set visited = new HashSet<>(); // Fully processed\n Set inStack = new HashSet<>(); // Currently being processed\n Deque order = new ArrayDeque<>();\n\n for (String service : dependencies.keySet()) {\n if (!visited.contains(service)) {\n if (hasCycle(service, visited, inStack, order)) {\n throw new CyclicDependencyException(\n \"Circular dependency detected involving: \" + service);\n }\n }\n }\n\n return new ArrayList<>(order);\n }\n\n private boolean hasCycle(String service, Set visited,\n Set inStack, Deque order) {\n visited.add(service);\n inStack.add(service); // Mark as \"in progress\"\n\n for (String dep : dependencies.getOrDefault(service, List.of())) {\n if (!visited.contains(dep)) {\n if (hasCycle(dep, visited, inStack, order)) {\n return true;\n }\n } else if (inStack.contains(dep)) {\n // Back edge found - cycle!\n return true;\n }\n }\n\n inStack.remove(service); // Done processing\n order.addFirst(service); // Add to front (reverse post-order)\n return false;\n }\n}\n```\n\n**Additional improvement - finding the actual cycle:**\n\n```java\n// ✅ Report the exact cycle path\npublic List findCycle() {\n Set visited = new HashSet<>();\n Map parent = new HashMap<>();\n\n for (String service : dependencies.keySet()) {\n if (!visited.contains(service)) {\n String cycleStart = detectCycle(service, visited, new HashSet<>(), parent);\n if (cycleStart != null) {\n return reconstructCycle(cycleStart, parent);\n }\n }\n }\n return null; // No cycle\n}\n\nprivate List reconstructCycle(String start, Map parent) {\n List cycle = new ArrayList<>();\n String current = start;\n\n do {\n cycle.add(current);\n current = parent.get(current);\n } while (!current.equals(start));\n\n cycle.add(start); // Complete the cycle\n Collections.reverse(cycle);\n return cycle;\n}\n```\n\n**The lesson:** Any system with dependencies is a graph. Cycle detection isn't optional - it's essential for reliability.\n\n---\n\n## 🧠 Mental Model: Graph Representations\n\n```text\nGRAPH REPRESENTATION COMPARISON\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nGraph: 4 vertices, 4 edges\n 0 ──→ 1\n │ │\n ↓ ↓\n 2 ──→ 3\n\nADJACENCY MATRIX:\n 0 1 2 3\n ┌──────────────┐\n 0 │ 0 1 1 0 │\n 1 │ 0 0 0 1 │\n 2 │ 0 0 0 1 │\n 3 │ 0 0 0 0 │\n └──────────────┘\nSpace: V² = 16 cells\n\nADJACENCY LIST:\n 0 → [1, 2]\n 1 → [3]\n 2 → [3]\n 3 → []\nSpace: V + E = 4 + 4 = 8 entries\n\nEDGE LIST:\n [(0,1), (0,2), (1,3), (2,3)]\nSpace: E = 4 entries\n```\n\n---\n\n## 🔬 Deep Dive: Graph Representation\n\n### Adjacency List (Most Common)\n\n```java\npublic class Graph {\n private final int vertices;\n private final List> adjList;\n private final boolean directed;\n\n public Graph(int vertices, boolean directed) {\n this.vertices = vertices;\n this.directed = directed;\n this.adjList = new ArrayList<>(vertices);\n\n for (int i = 0; i < vertices; i++) {\n adjList.add(new ArrayList<>());\n }\n }\n\n public void addEdge(int from, int to) {\n adjList.get(from).add(to);\n if (!directed) {\n adjList.get(to).add(from);\n }\n }\n\n public List neighbors(int vertex) {\n return adjList.get(vertex);\n }\n\n public int getVertices() {\n return vertices;\n }\n\n public int getEdges() {\n int count = adjList.stream()\n .mapToInt(List::size)\n .sum();\n return directed ? count : count / 2;\n }\n}\n```\n\n### Weighted Graph\n\n```java\npublic class WeightedGraph {\n private final int vertices;\n private final List> adjList;\n\n public record Edge(int to, int weight) {}\n\n public WeightedGraph(int vertices) {\n this.vertices = vertices;\n this.adjList = new ArrayList<>(vertices);\n for (int i = 0; i < vertices; i++) {\n adjList.add(new ArrayList<>());\n }\n }\n\n public void addEdge(int from, int to, int weight) {\n adjList.get(from).add(new Edge(to, weight));\n }\n\n public List neighbors(int vertex) {\n return adjList.get(vertex);\n }\n}\n```\n\n### Generic Graph with Labels\n\n```java\npublic class LabeledGraph {\n private final Map> adjList = new HashMap<>();\n\n public void addVertex(V vertex) {\n adjList.putIfAbsent(vertex, new HashSet<>());\n }\n\n public void addEdge(V from, V to) {\n addVertex(from);\n addVertex(to);\n adjList.get(from).add(to);\n }\n\n public Set neighbors(V vertex) {\n return adjList.getOrDefault(vertex, Collections.emptySet());\n }\n\n public Set vertices() {\n return adjList.keySet();\n }\n\n public boolean hasEdge(V from, V to) {\n return adjList.containsKey(from) && adjList.get(from).contains(to);\n }\n}\n```\n\n### Adjacency Matrix\n\n```java\npublic class GraphMatrix {\n private final int[][] matrix;\n private final int vertices;\n\n public GraphMatrix(int vertices) {\n this.vertices = vertices;\n this.matrix = new int[vertices][vertices];\n }\n\n public void addEdge(int from, int to) {\n matrix[from][to] = 1;\n }\n\n public void addEdge(int from, int to, int weight) {\n matrix[from][to] = weight;\n }\n\n public boolean hasEdge(int from, int to) {\n return matrix[from][to] != 0;\n }\n\n public int getWeight(int from, int to) {\n return matrix[from][to];\n }\n\n public List neighbors(int vertex) {\n List result = new ArrayList<>();\n for (int i = 0; i < vertices; i++) {\n if (matrix[vertex][i] != 0) {\n result.add(i);\n }\n }\n return result;\n }\n}\n```\n\n### When to Use Which\n\n| Representation | Best For |\n|----------------|----------|\n| Adjacency List | Sparse graphs (E << V²), iterating neighbors |\n| Adjacency Matrix | Dense graphs, checking edge existence |\n| Edge List | Algorithms that iterate all edges (Kruskal's MST) |\n| HashMap-based | Labeled vertices, dynamic graphs |\n\n---\n\n## 🔬 Deep Dive: Depth-First Search (DFS)\n\n### 🎮 Try It Yourself\n\nCompare DFS and BFS traversal visually. Watch how DFS explores deeply before backtracking, while BFS explores level by level:\n\n```visualizer-graph\nalgorithm: dfs\n```\n\n### Recursive DFS\n\n```java\npublic class DFS {\n /**\n * Recursive DFS traversal.\n *\n * Time: O(V + E)\n * Space: O(V) for recursion stack\n */\n public static List dfsRecursive(Graph graph, int start) {\n List result = new ArrayList<>();\n boolean[] visited = new boolean[graph.getVertices()];\n dfsHelper(graph, start, visited, result);\n return result;\n }\n\n private static void dfsHelper(Graph graph, int vertex,\n boolean[] visited, List result) {\n visited[vertex] = true;\n result.add(vertex);\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n dfsHelper(graph, neighbor, visited, result);\n }\n }\n }\n\n /**\n * DFS to visit ALL vertices (handles disconnected graphs).\n */\n public static List dfsAll(Graph graph) {\n List result = new ArrayList<>();\n boolean[] visited = new boolean[graph.getVertices()];\n\n for (int i = 0; i < graph.getVertices(); i++) {\n if (!visited[i]) {\n dfsHelper(graph, i, visited, result);\n }\n }\n return result;\n }\n}\n```\n\n### Iterative DFS\n\n```java\npublic class DFS {\n /**\n * Iterative DFS using explicit stack.\n * Avoids stack overflow for deep graphs.\n */\n public static List dfsIterative(Graph graph, int start) {\n List result = new ArrayList<>();\n boolean[] visited = new boolean[graph.getVertices()];\n Deque stack = new ArrayDeque<>();\n\n stack.push(start);\n\n while (!stack.isEmpty()) {\n int vertex = stack.pop();\n\n if (visited[vertex]) continue;\n visited[vertex] = true;\n result.add(vertex);\n\n // Add neighbors in reverse order for same traversal order as recursive\n List neighbors = graph.neighbors(vertex);\n for (int i = neighbors.size() - 1; i >= 0; i--) {\n int neighbor = neighbors.get(i);\n if (!visited[neighbor]) {\n stack.push(neighbor);\n }\n }\n }\n\n return result;\n }\n}\n```\n\n### DFS with Edge Classification\n\n```java\npublic class DFSEdgeClassification {\n enum EdgeType { TREE, BACK, FORWARD, CROSS }\n\n private final Graph graph;\n private final int[] discoveryTime;\n private final int[] finishTime;\n private final int[] parent;\n private int time;\n\n public Map classifyEdges() {\n int n = graph.getVertices();\n discoveryTime = new int[n];\n finishTime = new int[n];\n parent = new int[n];\n Arrays.fill(parent, -1);\n time = 0;\n\n boolean[] visited = new boolean[n];\n Map edges = new HashMap<>();\n\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n dfs(i, visited, edges);\n }\n }\n\n return edges;\n }\n\n private void dfs(int u, boolean[] visited, Map edges) {\n visited[u] = true;\n discoveryTime[u] = ++time;\n\n for (int v : graph.neighbors(u)) {\n String edge = u + \"->\" + v;\n\n if (!visited[v]) {\n parent[v] = u;\n edges.put(edge, EdgeType.TREE);\n dfs(v, visited, edges);\n } else if (finishTime[v] == 0) {\n // v is ancestor of u (still on stack)\n edges.put(edge, EdgeType.BACK);\n } else if (discoveryTime[u] < discoveryTime[v]) {\n // v is descendant of u (but not via tree edge)\n edges.put(edge, EdgeType.FORWARD);\n } else {\n // v was finished before u started\n edges.put(edge, EdgeType.CROSS);\n }\n }\n\n finishTime[u] = ++time;\n }\n}\n```\n\n### DFS Visualization\n\n```text\nDFS TRAVERSAL ORDER\n━━━━━━━━━━━━━━━━━━━\n\nGraph: DFS from 0:\n 0 0 (start)\n /|\\ │\n 1 2 3 ├─→ 1\n | | │ └─→ 4\n 4 5 │\n ├─→ 2\n │\n └─→ 3\n └─→ 5\n\nOrder: [0, 1, 4, 2, 3, 5]\n\nDiscovery/Finish times:\n Vertex: 0 1 2 3 4 5\n Disc: 1 2 6 8 3 10\n Finish: 12 5 7 11 4 11\n\nBack edge detection:\n If during DFS of u, we find edge u→v where v is on stack\n (discovered but not finished), it's a back edge → cycle!\n```\n\n---\n\n## 🔬 Deep Dive: Breadth-First Search (BFS)\n\n### Basic BFS\n\n```java\npublic class BFS {\n /**\n * BFS traversal from start vertex.\n *\n * Time: O(V + E)\n * Space: O(V)\n */\n public static List bfs(Graph graph, int start) {\n List result = new ArrayList<>();\n boolean[] visited = new boolean[graph.getVertices()];\n Queue queue = new LinkedList<>();\n\n visited[start] = true;\n queue.offer(start);\n\n while (!queue.isEmpty()) {\n int vertex = queue.poll();\n result.add(vertex);\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n visited[neighbor] = true;\n queue.offer(neighbor);\n }\n }\n }\n\n return result;\n }\n\n /**\n * BFS to find shortest path (unweighted graph).\n */\n public static List shortestPath(Graph graph, int start, int end) {\n if (start == end) return List.of(start);\n\n boolean[] visited = new boolean[graph.getVertices()];\n int[] parent = new int[graph.getVertices()];\n Arrays.fill(parent, -1);\n\n Queue queue = new LinkedList<>();\n visited[start] = true;\n queue.offer(start);\n\n while (!queue.isEmpty()) {\n int vertex = queue.poll();\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n visited[neighbor] = true;\n parent[neighbor] = vertex;\n queue.offer(neighbor);\n\n if (neighbor == end) {\n return reconstructPath(parent, start, end);\n }\n }\n }\n }\n\n return Collections.emptyList(); // No path found\n }\n\n private static List reconstructPath(int[] parent, int start, int end) {\n List path = new ArrayList<>();\n int current = end;\n\n while (current != -1) {\n path.add(current);\n current = parent[current];\n }\n\n Collections.reverse(path);\n return path;\n }\n}\n```\n\n### BFS with Levels\n\n```java\npublic class BFS {\n /**\n * BFS returning vertices by level (distance from start).\n */\n public static List> bfsLevels(Graph graph, int start) {\n List> levels = new ArrayList<>();\n boolean[] visited = new boolean[graph.getVertices()];\n Queue queue = new LinkedList<>();\n\n visited[start] = true;\n queue.offer(start);\n\n while (!queue.isEmpty()) {\n int levelSize = queue.size();\n List currentLevel = new ArrayList<>();\n\n for (int i = 0; i < levelSize; i++) {\n int vertex = queue.poll();\n currentLevel.add(vertex);\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n visited[neighbor] = true;\n queue.offer(neighbor);\n }\n }\n }\n\n levels.add(currentLevel);\n }\n\n return levels;\n }\n\n /**\n * Find all vertices at exactly distance k from start.\n */\n public static List verticesAtDistance(Graph graph, int start, int k) {\n List> levels = bfsLevels(graph, start);\n return k < levels.size() ? levels.get(k) : Collections.emptyList();\n }\n}\n```\n\n### BFS vs DFS Comparison\n\n```text\nBFS vs DFS TRAVERSAL\n━━━━━━━━━━━━━━━━━━━━\n\nGraph:\n 0\n /|\\\n 1 2 3\n /| |\\\n 4 5 6 7\n\nBFS from 0: DFS from 0:\nLevel 0: [0] Stack: [0]\nLevel 1: [1, 2, 3] Visit: 0 → 1 → 4 → 5 → 2 → 3 → 6 → 7\nLevel 2: [4, 5, 6, 7]\n\nOrder: [0, 1, 2, 3, 4, 5, 6, 7] Order: [0, 1, 4, 5, 2, 3, 6, 7]\n\nBFS finds shortest path to 7: 0 → 3 → 7 (length 2)\nDFS might find: 0 → 1 → 4 (dead end) → backtrack → ... → 3 → 7\n```\n\n---\n\n## 🔬 Deep Dive: Cycle Detection\n\n### Cycle Detection in Undirected Graph\n\n```java\npublic class CycleDetection {\n /**\n * Detect cycle in undirected graph using DFS.\n *\n * Key insight: In undirected graph, a cycle exists if we\n * visit a vertex that's already visited AND it's not our parent.\n */\n public static boolean hasCycleUndirected(Graph graph) {\n int n = graph.getVertices();\n boolean[] visited = new boolean[n];\n\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n if (dfsCycleUndirected(graph, i, -1, visited)) {\n return true;\n }\n }\n }\n return false;\n }\n\n private static boolean dfsCycleUndirected(Graph graph, int vertex,\n int parent, boolean[] visited) {\n visited[vertex] = true;\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n if (dfsCycleUndirected(graph, neighbor, vertex, visited)) {\n return true;\n }\n } else if (neighbor != parent) {\n // Visited vertex that's not parent = cycle!\n return true;\n }\n }\n return false;\n }\n}\n```\n\n### Cycle Detection in Directed Graph\n\n```java\npublic class CycleDetection {\n /**\n * Detect cycle in directed graph using DFS.\n *\n * Need to track vertices currently on the recursion stack.\n * A back edge (edge to vertex on stack) indicates cycle.\n */\n public static boolean hasCycleDirected(Graph graph) {\n int n = graph.getVertices();\n boolean[] visited = new boolean[n];\n boolean[] onStack = new boolean[n];\n\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n if (dfsCycleDirected(graph, i, visited, onStack)) {\n return true;\n }\n }\n }\n return false;\n }\n\n private static boolean dfsCycleDirected(Graph graph, int vertex,\n boolean[] visited, boolean[] onStack) {\n visited[vertex] = true;\n onStack[vertex] = true;\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n if (dfsCycleDirected(graph, neighbor, visited, onStack)) {\n return true;\n }\n } else if (onStack[neighbor]) {\n // Back edge to vertex currently being processed\n return true;\n }\n }\n\n onStack[vertex] = false; // Remove from stack when done\n return false;\n }\n\n /**\n * Find and return the actual cycle path.\n */\n public static List findCycle(Graph graph) {\n int n = graph.getVertices();\n boolean[] visited = new boolean[n];\n boolean[] onStack = new boolean[n];\n int[] parent = new int[n];\n Arrays.fill(parent, -1);\n\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n int cycleEnd = dfsFindCycle(graph, i, visited, onStack, parent);\n if (cycleEnd != -1) {\n return extractCycle(parent, cycleEnd);\n }\n }\n }\n return null;\n }\n\n private static int dfsFindCycle(Graph graph, int vertex,\n boolean[] visited, boolean[] onStack, int[] parent) {\n visited[vertex] = true;\n onStack[vertex] = true;\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n parent[neighbor] = vertex;\n int result = dfsFindCycle(graph, neighbor, visited, onStack, parent);\n if (result != -1) return result;\n } else if (onStack[neighbor]) {\n parent[neighbor] = vertex;\n return neighbor;\n }\n }\n\n onStack[vertex] = false;\n return -1;\n }\n\n private static List extractCycle(int[] parent, int cycleEnd) {\n List cycle = new ArrayList<>();\n int current = cycleEnd;\n\n do {\n cycle.add(current);\n current = parent[current];\n } while (current != cycleEnd);\n\n cycle.add(cycleEnd);\n Collections.reverse(cycle);\n return cycle;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Topological Sort\n\n### DFS-Based Topological Sort\n\n```java\npublic class TopologicalSort {\n /**\n * Topological sort using DFS (reverse post-order).\n *\n * Time: O(V + E)\n * Space: O(V)\n *\n * @throws IllegalStateException if graph has cycle\n */\n public static List topologicalSortDFS(Graph graph) {\n int n = graph.getVertices();\n boolean[] visited = new boolean[n];\n boolean[] onStack = new boolean[n];\n Deque result = new ArrayDeque<>();\n\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n if (!dfsTopSort(graph, i, visited, onStack, result)) {\n throw new IllegalStateException(\"Graph has cycle - no topological order exists\");\n }\n }\n }\n\n return new ArrayList<>(result);\n }\n\n private static boolean dfsTopSort(Graph graph, int vertex,\n boolean[] visited, boolean[] onStack,\n Deque result) {\n visited[vertex] = true;\n onStack[vertex] = true;\n\n for (int neighbor : graph.neighbors(vertex)) {\n if (!visited[neighbor]) {\n if (!dfsTopSort(graph, neighbor, visited, onStack, result)) {\n return false;\n }\n } else if (onStack[neighbor]) {\n return false; // Cycle detected\n }\n }\n\n onStack[vertex] = false;\n result.addFirst(vertex); // Add to front (reverse post-order)\n return true;\n }\n}\n```\n\n### Kahn's Algorithm (BFS-Based)\n\n```java\npublic class TopologicalSort {\n /**\n * Kahn's algorithm for topological sort.\n *\n * Process vertices with no incoming edges.\n * Also useful for detecting if graph is DAG.\n */\n public static List topologicalSortKahn(Graph graph) {\n int n = graph.getVertices();\n\n // Calculate in-degree of each vertex\n int[] inDegree = new int[n];\n for (int i = 0; i < n; i++) {\n for (int neighbor : graph.neighbors(i)) {\n inDegree[neighbor]++;\n }\n }\n\n // Add all vertices with in-degree 0 to queue\n Queue queue = new LinkedList<>();\n for (int i = 0; i < n; i++) {\n if (inDegree[i] == 0) {\n queue.offer(i);\n }\n }\n\n List result = new ArrayList<>();\n\n while (!queue.isEmpty()) {\n int vertex = queue.poll();\n result.add(vertex);\n\n // \"Remove\" this vertex by decrementing in-degree of neighbors\n for (int neighbor : graph.neighbors(vertex)) {\n inDegree[neighbor]--;\n if (inDegree[neighbor] == 0) {\n queue.offer(neighbor);\n }\n }\n }\n\n // If not all vertices processed, there's a cycle\n if (result.size() != n) {\n throw new IllegalStateException(\"Graph has cycle - no topological order exists\");\n }\n\n return result;\n }\n\n /**\n * Count number of valid topological orderings.\n * (Useful for detecting parallelizable tasks)\n */\n public static long countTopologicalOrders(Graph graph) {\n int n = graph.getVertices();\n int[] inDegree = new int[n];\n\n for (int i = 0; i < n; i++) {\n for (int neighbor : graph.neighbors(i)) {\n inDegree[neighbor]++;\n }\n }\n\n return countOrderings(inDegree, graph, new boolean[n], n);\n }\n\n private static long countOrderings(int[] inDegree, Graph graph,\n boolean[] visited, int remaining) {\n if (remaining == 0) return 1;\n\n long count = 0;\n for (int i = 0; i < inDegree.length; i++) {\n if (!visited[i] && inDegree[i] == 0) {\n visited[i] = true;\n for (int neighbor : graph.neighbors(i)) {\n inDegree[neighbor]--;\n }\n\n count += countOrderings(inDegree, graph, visited, remaining - 1);\n\n visited[i] = false;\n for (int neighbor : graph.neighbors(i)) {\n inDegree[neighbor]++;\n }\n }\n }\n return count;\n }\n}\n```\n\n### Topological Sort Visualization\n\n```text\nTOPOLOGICAL SORT EXAMPLE\n━━━━━━━━━━━━━━━━━━━━━━━━\n\nTask dependencies:\n A → C\n B → C\n B → D\n C → E\n D → E\n\nGraph:\n A ──→ C ──→ E\n ↑ ↑\n B ──→─┘ ┌──┘\n └──→ D─┘\n\nKahn's Algorithm:\n Initial in-degrees: A=0, B=0, C=2, D=1, E=2\n Queue: [A, B]\n\n Step 1: Process A → Queue: [B], Result: [A]\n Update: C's in-degree = 1\n\n Step 2: Process B → Queue: [D], Result: [A, B]\n Update: C's in-degree = 0, D's in-degree = 0\n Add C to queue: [D, C]\n\n Step 3: Process D → Queue: [C], Result: [A, B, D]\n Update: E's in-degree = 1\n\n Step 4: Process C → Queue: [E], Result: [A, B, D, C]\n Update: E's in-degree = 0\n\n Step 5: Process E → Queue: [], Result: [A, B, D, C, E]\n\nValid orderings: [A, B, D, C, E], [A, B, C, D, E], [B, A, D, C, E], ...\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Missing Visited Check\n\n```java\n// ❌ Infinite loop on cyclic graph\nvoid dfs(int vertex) {\n for (int neighbor : graph.neighbors(vertex)) {\n dfs(neighbor); // Will loop forever if there's a cycle!\n }\n}\n\n// ✅ Track visited vertices\nvoid dfs(int vertex, boolean[] visited) {\n if (visited[vertex]) return;\n visited[vertex] = true;\n\n for (int neighbor : graph.neighbors(vertex)) {\n dfs(neighbor, visited);\n }\n}\n```\n\n### Mistake 2: Marking Visited at Wrong Time (BFS)\n\n```java\n// ❌ Marking visited when dequeuing - vertex can be added multiple times\nwhile (!queue.isEmpty()) {\n int v = queue.poll();\n visited[v] = true; // Too late! v might already be in queue multiple times\n\n for (int neighbor : graph.neighbors(v)) {\n if (!visited[neighbor]) {\n queue.offer(neighbor); // Might add same vertex twice\n }\n }\n}\n\n// ✅ Mark visited when enqueueing\nvisited[start] = true;\nqueue.offer(start);\n\nwhile (!queue.isEmpty()) {\n int v = queue.poll();\n\n for (int neighbor : graph.neighbors(v)) {\n if (!visited[neighbor]) {\n visited[neighbor] = true; // Mark before adding to queue\n queue.offer(neighbor);\n }\n }\n}\n```\n\n### Mistake 3: Wrong Parent Check in Undirected Cycle Detection\n\n```java\n// ❌ Using vertex index instead of previous vertex\nvoid dfs(int vertex, int parent, boolean[] visited) {\n for (int neighbor : graph.neighbors(vertex)) {\n if (visited[neighbor] && neighbor != vertex) { // Wrong comparison!\n // This checks if neighbor is not current vertex\n // Should check if neighbor is not the parent\n }\n }\n}\n\n// ✅ Correct parent check\nvoid dfs(int vertex, int parent, boolean[] visited) {\n for (int neighbor : graph.neighbors(vertex)) {\n if (visited[neighbor] && neighbor != parent) { // Correct!\n // This checks if we found a back edge\n }\n }\n}\n```\n\n### Mistake 4: Forgetting Disconnected Components\n\n```java\n// ❌ Only processes vertices reachable from vertex 0\npublic void process(Graph graph) {\n dfs(graph, 0, new boolean[graph.getVertices()]);\n}\n\n// ✅ Process all components\npublic void processAll(Graph graph) {\n boolean[] visited = new boolean[graph.getVertices()];\n for (int i = 0; i < graph.getVertices(); i++) {\n if (!visited[i]) {\n dfs(graph, i, visited);\n }\n }\n}\n```\n\n---\n\n## 🐛 Debug This: The Broken Graph Algorithms\n\nThese implementations have bugs. Find and fix them:\n\n```java\npublic class BrokenGraphAlgorithms {\n\n // Bug 1: BFS shortest path\n public int shortestPath(Graph graph, int start, int end) {\n Queue queue = new LinkedList<>();\n int[] dist = new int[graph.getVertices()];\n Arrays.fill(dist, -1);\n\n queue.offer(start);\n dist[start] = 0;\n\n while (!queue.isEmpty()) {\n int v = queue.poll();\n for (int neighbor : graph.neighbors(v)) {\n if (dist[neighbor] == -1) {\n dist[neighbor] = dist[v]; // Bug\n queue.offer(neighbor);\n }\n }\n }\n return dist[end];\n }\n\n // Bug 2: Topological sort\n public List topSort(Graph graph) {\n List result = new ArrayList<>();\n boolean[] visited = new boolean[graph.getVertices()];\n\n for (int i = 0; i < graph.getVertices(); i++) {\n dfs(graph, i, visited, result);\n }\n return result; // Bug\n }\n\n private void dfs(Graph graph, int v, boolean[] visited, List result) {\n if (visited[v]) return;\n visited[v] = true;\n\n for (int neighbor : graph.neighbors(v)) {\n dfs(graph, neighbor, visited, result);\n }\n result.add(v);\n }\n\n // Bug 3: Cycle detection in directed graph\n public boolean hasCycle(Graph graph) {\n boolean[] visited = new boolean[graph.getVertices()];\n\n for (int i = 0; i < graph.getVertices(); i++) {\n if (detectCycle(graph, i, visited)) {\n return true;\n }\n }\n return false;\n }\n\n private boolean detectCycle(Graph graph, int v, boolean[] visited) {\n if (visited[v]) return true; // Bug\n visited[v] = true;\n\n for (int neighbor : graph.neighbors(v)) {\n if (detectCycle(graph, neighbor, visited)) {\n return true;\n }\n }\n return false;\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. Distance increment in BFS\n2. Order reversal in topological sort\n3. Distinguishing \"visited\" from \"on current path\" in cycle detection\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedGraphAlgorithms {\n\n // ✅ Fix 1: BFS shortest path - increment distance\n public int shortestPath(Graph graph, int start, int end) {\n Queue queue = new LinkedList<>();\n int[] dist = new int[graph.getVertices()];\n Arrays.fill(dist, -1);\n\n queue.offer(start);\n dist[start] = 0;\n\n while (!queue.isEmpty()) {\n int v = queue.poll();\n for (int neighbor : graph.neighbors(v)) {\n if (dist[neighbor] == -1) {\n dist[neighbor] = dist[v] + 1; // ✅ Add 1 to distance\n queue.offer(neighbor);\n }\n }\n }\n return dist[end];\n }\n\n // ✅ Fix 2: Topological sort - reverse result\n public List topSort(Graph graph) {\n Deque result = new ArrayDeque<>(); // ✅ Use Deque\n boolean[] visited = new boolean[graph.getVertices()];\n\n for (int i = 0; i < graph.getVertices(); i++) {\n if (!visited[i]) { // ✅ Check before calling\n dfs(graph, i, visited, result);\n }\n }\n return new ArrayList<>(result); // ✅ Already in correct order\n }\n\n private void dfs(Graph graph, int v, boolean[] visited, Deque result) {\n visited[v] = true;\n\n for (int neighbor : graph.neighbors(v)) {\n if (!visited[neighbor]) {\n dfs(graph, neighbor, visited, result);\n }\n }\n result.addFirst(v); // ✅ Add to front (reverse post-order)\n }\n\n // ✅ Fix 3: Cycle detection - use onStack array\n public boolean hasCycle(Graph graph) {\n int n = graph.getVertices();\n boolean[] visited = new boolean[n];\n boolean[] onStack = new boolean[n]; // ✅ Track current path\n\n for (int i = 0; i < n; i++) {\n if (!visited[i]) {\n if (detectCycle(graph, i, visited, onStack)) {\n return true;\n }\n }\n }\n return false;\n }\n\n private boolean detectCycle(Graph graph, int v,\n boolean[] visited, boolean[] onStack) {\n visited[v] = true;\n onStack[v] = true; // ✅ Mark as on current path\n\n for (int neighbor : graph.neighbors(v)) {\n if (!visited[neighbor]) {\n if (detectCycle(graph, neighbor, visited, onStack)) {\n return true;\n }\n } else if (onStack[neighbor]) { // ✅ Check if on current path\n return true;\n }\n }\n\n onStack[v] = false; // ✅ Remove from path when backtracking\n return false;\n }\n}\n```\n\n**Bugs explained:**\n\n1. **BFS distance**: `dist[neighbor] = dist[v]` doesn't increment distance. Should be `dist[v] + 1`.\n\n2. **Topological sort**: DFS post-order gives reverse topological order. Need to either reverse the result or add to front of a deque.\n\n3. **Cycle detection**: Just checking `visited[v]` returns true for any visited vertex, not just vertices on the current DFS path. Need separate `onStack` array to track vertices currently being explored.\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Count Connected Components ⭐\n\nCount the number of connected components in an undirected graph.\n\n```java\npublic class ConnectedComponents {\n /**\n * Count connected components.\n * Time: O(V + E)\n */\n public int count(Graph graph) {\n // Your implementation\n }\n\n /**\n * Return list of components, each component is list of vertices.\n */\n public List> getComponents(Graph graph) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 2: Bipartite Check ⭐⭐\n\nCheck if an undirected graph is bipartite (can be 2-colored).\n\n```java\npublic class BipartiteCheck {\n /**\n * Check if graph is bipartite using BFS coloring.\n * A graph is bipartite iff it has no odd-length cycles.\n */\n public boolean isBipartite(Graph graph) {\n // Your implementation\n }\n\n /**\n * If bipartite, return the two sets of vertices.\n */\n public List> getPartition(Graph graph) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nUse BFS and try to 2-color the graph. If you find an edge between two vertices of the same color, it's not bipartite.\n\n

\n\n---\n\n### Exercise 3: All Paths Between Two Vertices ⭐⭐⭐\n\nFind all paths from source to destination in a DAG.\n\n```java\npublic class AllPaths {\n /**\n * Find all paths from src to dst in a DAG.\n * Time: O(V! × V) worst case (but typically much better)\n */\n public List> allPaths(Graph graph, int src, int dst) {\n // Your implementation using DFS with backtracking\n }\n}\n```\n\n---\n\n### Exercise 4: Course Schedule II (LeetCode 210) ⭐⭐⭐\n\nGiven n courses and prerequisites, return order to finish all courses.\n\n```java\npublic class CourseSchedule {\n /**\n * @param numCourses Total number of courses\n * @param prerequisites Array of [course, prereq] pairs\n * @return Order to take courses, or empty array if impossible\n */\n public int[] findOrder(int numCourses, int[][] prerequisites) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 5: Clone Graph (LeetCode 133) ⭐⭐⭐⭐\n\nDeep copy a graph where each node has value and list of neighbors.\n\n```java\npublic class CloneGraph {\n static class Node {\n int val;\n List neighbors;\n\n Node(int val) {\n this.val = val;\n this.neighbors = new ArrayList<>();\n }\n }\n\n /**\n * Deep copy the graph.\n * Time: O(V + E)\n * Space: O(V)\n */\n public Node cloneGraph(Node node) {\n // Your implementation using BFS or DFS with HashMap\n }\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: When would you use BFS vs DFS?\n\n**Answer:**\n\n| Use BFS when: | Use DFS when: |\n|---------------|---------------|\n| Finding shortest path (unweighted) | Detecting cycles |\n| Level-order traversal | Topological sort |\n| Finding connected vertices at distance k | Finding any path (not necessarily shortest) |\n| Peer-to-peer networks | Solving puzzles (maze, sudoku) |\n| Social network friend suggestions | Memory constrained (BFS queue can be huge) |\n\n**Key insight:**\n- BFS explores \"outward\" - good for distance-based problems\n- DFS explores \"deep\" - good for existence/connectivity problems\n\n---\n\n### Question 2: How do you detect a cycle in an undirected vs directed graph?\n\n**Answer:**\n\n**Undirected Graph:**\n- During DFS, if we visit an already-visited vertex that's not our parent, there's a cycle\n- Or: Count edges. If edges ≥ vertices, there's a cycle (in connected graph)\n\n```java\n// Undirected: back edge to non-parent = cycle\nif (visited[neighbor] && neighbor != parent) {\n return true; // Cycle!\n}\n```\n\n**Directed Graph:**\n- Need to track vertices on current DFS path (not just visited)\n- Back edge to vertex on current path = cycle\n\n```java\n// Directed: need separate \"onStack\" tracking\nif (onStack[neighbor]) {\n return true; // Cycle!\n}\n```\n\n**Why the difference?** In undirected graphs, edge A-B creates both A→B and B→A. We don't want to falsely detect A→B→A as a cycle.\n\n---\n\n### Question 3: Explain topological sort and its applications\n\n**Answer:**\n\n**Definition:** Linear ordering of vertices such that for every edge u→v, u comes before v.\n\n**Only possible for:** Directed Acyclic Graphs (DAGs)\n\n**Algorithms:**\n1. **DFS-based:** Reverse post-order of DFS gives topological order\n2. **Kahn's (BFS-based):** Repeatedly remove vertices with in-degree 0\n\n**Applications:**\n- Build systems (compile dependencies)\n- Course scheduling\n- Task scheduling\n- Package managers\n- Spreadsheet cell evaluation order\n- Deadlock detection (cycle in wait-for graph)\n\n---\n\n### Question 4: How would you find the shortest path in an unweighted graph?\n\n**Answer:**\n\nUse BFS. BFS explores vertices in order of their distance from the source.\n\n```java\npublic int shortestPath(Graph g, int src, int dst) {\n Queue queue = new LinkedList<>();\n int[] dist = new int[g.getVertices()];\n Arrays.fill(dist, -1);\n\n queue.offer(src);\n dist[src] = 0;\n\n while (!queue.isEmpty()) {\n int v = queue.poll();\n if (v == dst) return dist[dst];\n\n for (int neighbor : g.neighbors(v)) {\n if (dist[neighbor] == -1) {\n dist[neighbor] = dist[v] + 1;\n queue.offer(neighbor);\n }\n }\n }\n return -1; // No path\n}\n```\n\n**Why BFS works:** BFS processes vertices level by level. When we first reach a vertex, it's via the shortest path (fewest edges).\n\n**For weighted graphs:** Use Dijkstra's algorithm (next article).\n\n---\n\n### Question 5: How do you represent a graph in code?\n\n**Answer:**\n\nThree main representations:\n\n1. **Adjacency List** (most common):\n```java\nList> adj = new ArrayList<>();\n// adj.get(i) = list of neighbors of vertex i\n```\nSpace: O(V + E), Good for: sparse graphs, iterating neighbors\n\n2. **Adjacency Matrix:**\n```java\nint[][] matrix = new int[V][V];\n// matrix[i][j] = 1 if edge exists (or weight)\n```\nSpace: O(V²), Good for: dense graphs, checking edge existence in O(1)\n\n3. **Edge List:**\n```java\nList edges = new ArrayList<>();\n// Each element is [from, to] or [from, to, weight]\n```\nSpace: O(E), Good for: algorithms that iterate all edges (Kruskal's)\n\n**Choosing representation:**\n- Sparse graph (E << V²): Adjacency list\n- Dense graph (E ≈ V²): Either works, matrix if need O(1) edge lookup\n- Need to iterate all edges: Edge list or adjacency list\n- Dynamic (add/remove vertices): HashMap-based adjacency list\n\n---\n\n## 📋 Quick Reference\n\n### Graph Terminology\n\n| Term | Definition |\n|------|------------|\n| Vertex (Node) | Point in graph |\n| Edge | Connection between vertices |\n| Directed | Edges have direction (u → v) |\n| Undirected | Edges are bidirectional |\n| Weighted | Edges have values/costs |\n| Path | Sequence of vertices connected by edges |\n| Cycle | Path that starts and ends at same vertex |\n| Connected | Path exists between every pair of vertices |\n| DAG | Directed Acyclic Graph |\n| Degree | Number of edges at a vertex |\n| In-degree | Number of incoming edges (directed) |\n| Out-degree | Number of outgoing edges (directed) |\n\n### Complexity Summary\n\n| Operation | Adjacency List | Adjacency Matrix |\n|-----------|----------------|------------------|\n| Space | O(V + E) | O(V²) |\n| Add vertex | O(1) | O(V²) |\n| Add edge | O(1) | O(1) |\n| Remove edge | O(degree) | O(1) |\n| Check edge | O(degree) | O(1) |\n| Iterate neighbors | O(degree) | O(V) |\n| DFS/BFS | O(V + E) | O(V²) |\n\n### Code Templates\n\n```java\n// DFS Template\nvoid dfs(int v, boolean[] visited) {\n visited[v] = true;\n // Process v\n for (int neighbor : graph.neighbors(v)) {\n if (!visited[neighbor]) {\n dfs(neighbor, visited);\n }\n }\n}\n\n// BFS Template\nvoid bfs(int start) {\n boolean[] visited = new boolean[n];\n Queue queue = new LinkedList<>();\n visited[start] = true;\n queue.offer(start);\n\n while (!queue.isEmpty()) {\n int v = queue.poll();\n // Process v\n for (int neighbor : graph.neighbors(v)) {\n if (!visited[neighbor]) {\n visited[neighbor] = true;\n queue.offer(neighbor);\n }\n }\n }\n}\n\n// Topological Sort (Kahn's)\nList topSort() {\n int[] inDegree = computeInDegrees();\n Queue queue = new LinkedList<>();\n for (int i = 0; i < n; i++) {\n if (inDegree[i] == 0) queue.offer(i);\n }\n\n List result = new ArrayList<>();\n while (!queue.isEmpty()) {\n int v = queue.poll();\n result.add(v);\n for (int neighbor : graph.neighbors(v)) {\n if (--inDegree[neighbor] == 0) {\n queue.offer(neighbor);\n }\n }\n }\n return result;\n}\n```\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read article, implement Graph class | 60 min |\n| Day 3 | Implement DFS and BFS from scratch | 30 min |\n| Day 7 | Implement cycle detection and topological sort | 30 min |\n| Day 14 | Solve 3 LeetCode graph problems | 45 min |\n| Day 30 | Review and implement clone graph | 20 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 12: Shortest Path Algorithms** covers:\n- Dijkstra's algorithm with priority queue\n- Bellman-Ford for negative weights\n- Floyd-Warshall for all pairs\n- A* heuristic search\n- Bidirectional search\n\n**Key insight preview**: BFS finds shortest path by edge count. Dijkstra's finds shortest path by edge weight - a crucial distinction for real-world applications like navigation.\n\n---\n\n*This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.163257Z","createdAt","2026-06-10T07:19:25.164149Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",25,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",11,"author",{"_31":55,"_103":57,"_104":105,"_106":107,"_108":-5,"_109":-5,"_110":-5,"_111":-5,"_112":-5},"category",{"_31":99,"_73":59,"_35":100,"_76":101,"_102":-5},"tags",[79,80,81,82,83],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":96,"_73":97,"_35":98},{"_31":93,"_73":94,"_35":95},{"_31":90,"_73":91,"_35":92},{"_31":87,"_73":88,"_35":89},{"_31":84,"_73":85,"_35":86},163,"Topological Sort","topological-sort",160,"Graph","graph",161,"Dfs","dfs",164,"Cycle Detection","cycle-detection",162,"Bfs","bfs",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]