[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":84,"_73":85,"_35":86},"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",82,"title","Graph Traversal: DFS & BFS","slug","dsa-cheatsheet-part-11-graph-traversal","excerpt","Visual guide to graph traversal: DFS explores deep, BFS explores wide. Watch both algorithms visit nodes.","# Graph Traversal: DFS & BFS\n\n## 📋 Quick Reference\n\n| Property | DFS | BFS |\n|----------|-----|-----|\n| **Data Structure** | Stack (or recursion) | Queue |\n| **Time Complexity** | O(V + E) | O(V + E) |\n| **Space Complexity** | O(V) | O(V) |\n| **Path Found** | Any valid path | Shortest path (unweighted) |\n| **Best For** | Connectivity, cycles, topological sort | Shortest path, level-order |\n\n**One-liner**: *DFS explores deep before wide (uses stack); BFS explores wide before deep (uses queue).*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how DFS and BFS explore graphs differently:\n\n```visualizer-graph\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. Run DFS - see it go deep into one branch first\n2. Run BFS - see it explore level by level\n3. Compare visit order between algorithms\n4. Try on different graph structures (tree, cycle, disconnected)\n\n---\n\n## 🔧 DFS Implementation\n\n### Recursive DFS\n\n```java\npublic void dfs(Map> graph, int start) {\n Set visited = new HashSet<>();\n dfsRecursive(graph, start, visited);\n}\n\nprivate void dfsRecursive(Map> graph,\n int node, Set visited) {\n if (visited.contains(node)) return;\n\n visited.add(node);\n System.out.println(\"Visiting: \" + node);\n\n for (int neighbor : graph.getOrDefault(node, List.of())) {\n dfsRecursive(graph, neighbor, visited);\n }\n}\n```\n\n### Iterative DFS (Stack)\n\n```java\npublic void dfsIterative(Map> graph, int start) {\n Set visited = new HashSet<>();\n Deque stack = new ArrayDeque<>();\n\n stack.push(start);\n\n while (!stack.isEmpty()) {\n int node = stack.pop();\n\n if (visited.contains(node)) continue;\n visited.add(node);\n System.out.println(\"Visiting: \" + node);\n\n // Add neighbors to stack (reverse for consistent order)\n List neighbors = graph.getOrDefault(node, List.of());\n for (int i = neighbors.size() - 1; i >= 0; i--) {\n if (!visited.contains(neighbors.get(i))) {\n stack.push(neighbors.get(i));\n }\n }\n }\n}\n```\n\n---\n\n## 🔧 BFS Implementation\n\n### Standard BFS (Queue)\n\n```java\npublic void bfs(Map> graph, int start) {\n Set visited = new HashSet<>();\n Queue queue = new ArrayDeque<>();\n\n visited.add(start);\n queue.offer(start);\n\n while (!queue.isEmpty()) {\n int node = queue.poll();\n System.out.println(\"Visiting: \" + node);\n\n for (int neighbor : graph.getOrDefault(node, List.of())) {\n if (!visited.contains(neighbor)) {\n visited.add(neighbor);\n queue.offer(neighbor);\n }\n }\n }\n}\n```\n\n### BFS with Distance Tracking\n\n```java\npublic Map bfsDistance(Map> graph,\n int start) {\n Map distance = new HashMap<>();\n Queue queue = new ArrayDeque<>();\n\n distance.put(start, 0);\n queue.offer(start);\n\n while (!queue.isEmpty()) {\n int node = queue.poll();\n\n for (int neighbor : graph.getOrDefault(node, List.of())) {\n if (!distance.containsKey(neighbor)) {\n distance.put(neighbor, distance.get(node) + 1);\n queue.offer(neighbor);\n }\n }\n }\n\n return distance;\n}\n```\n\n---\n\n## 📊 Complexity Analysis\n\n| Algorithm | Time | Space | Notes |\n|-----------|------|-------|-------|\n| DFS | O(V + E) | O(V) | Stack depth = longest path |\n| BFS | O(V + E) | O(V) | Queue size = widest level |\n\nWhere V = vertices (nodes), E = edges\n\n### Memory Comparison\n\n```\nTree with depth D and branching factor B:\n\nDFS space: O(D) - stores path from root\nBFS space: O(B^D) - stores entire level\n\nFor wide, shallow trees: DFS uses less memory\nFor deep, narrow trees: BFS uses less memory\n```\n\n---\n\n## ✅ When to Use Which\n\n### Use DFS When\n\n- **Finding any path** - not necessarily shortest\n- **Detecting cycles** - track path for back edges\n- **Topological sort** - dependency ordering\n- **Connected components** - explore entire component\n- **Maze solving** - exhaustive exploration\n- **Memory constrained** - lower space for deep graphs\n\n### Use BFS When\n\n- **Shortest path (unweighted)** - guaranteed shortest\n- **Level-order traversal** - process by distance\n- **Finding nearest** - closest node matching condition\n- **Social network degrees** - friends of friends\n- **Web crawling to depth N** - limit crawl depth\n\n---\n\n## 🧩 Common Patterns\n\n### Cycle Detection (Directed Graph)\n\n```java\npublic boolean hasCycle(Map> graph) {\n Set visited = new HashSet<>();\n Set inStack = new HashSet<>(); // Currently in recursion stack\n\n for (int node : graph.keySet()) {\n if (hasCycleDFS(graph, node, visited, inStack)) {\n return true;\n }\n }\n return false;\n}\n\nprivate boolean hasCycleDFS(Map> graph, int node,\n Set visited, Set inStack) {\n if (inStack.contains(node)) return true; // Back edge = cycle\n if (visited.contains(node)) return false;\n\n visited.add(node);\n inStack.add(node);\n\n for (int neighbor : graph.getOrDefault(node, List.of())) {\n if (hasCycleDFS(graph, neighbor, visited, inStack)) {\n return true;\n }\n }\n\n inStack.remove(node); // Backtrack\n return false;\n}\n```\n\n### Topological Sort (DFS)\n\n```java\npublic List topologicalSort(Map> graph) {\n Set visited = new HashSet<>();\n Deque result = new ArrayDeque<>();\n\n for (int node : graph.keySet()) {\n if (!visited.contains(node)) {\n topoDFS(graph, node, visited, result);\n }\n }\n\n return new ArrayList<>(result);\n}\n\nprivate void topoDFS(Map> graph, int node,\n Set visited, Deque result) {\n visited.add(node);\n\n for (int neighbor : graph.getOrDefault(node, List.of())) {\n if (!visited.contains(neighbor)) {\n topoDFS(graph, neighbor, visited, result);\n }\n }\n\n result.addFirst(node); // Add after all descendants\n}\n```\n\n### Shortest Path (BFS)\n\n```java\npublic List shortestPath(Map> graph,\n int start, int end) {\n Map parent = new HashMap<>();\n Queue queue = new ArrayDeque<>();\n\n parent.put(start, null);\n queue.offer(start);\n\n while (!queue.isEmpty()) {\n int node = queue.poll();\n\n if (node == end) {\n return reconstructPath(parent, end);\n }\n\n for (int neighbor : graph.getOrDefault(node, List.of())) {\n if (!parent.containsKey(neighbor)) {\n parent.put(neighbor, node);\n queue.offer(neighbor);\n }\n }\n }\n\n return List.of(); // No path found\n}\n\nprivate List reconstructPath(Map parent, int end) {\n List path = new ArrayList<>();\n Integer node = end;\n\n while (node != null) {\n path.add(0, node);\n node = parent.get(node);\n }\n\n return path;\n}\n```\n\n---\n\n## ⚠️ Common Pitfalls\n\n### 1. Forgetting to Mark Visited\n\n```java\n// ❌ Infinite loop on cycles\nvoid dfs(int node) {\n for (int neighbor : graph.get(node)) {\n dfs(neighbor); // Never terminates if cycle exists!\n }\n}\n\n// ✅ Track visited nodes\nvoid dfs(int node, Set visited) {\n if (visited.contains(node)) return;\n visited.add(node);\n for (int neighbor : graph.get(node)) {\n dfs(neighbor, visited);\n }\n}\n```\n\n### 2. BFS Marking Too Late\n\n```java\n// ❌ Mark when polling - causes duplicates\nwhile (!queue.isEmpty()) {\n int node = queue.poll();\n visited.add(node); // Too late! Node may be added multiple times\n for (int neighbor : ...) {\n queue.offer(neighbor);\n }\n}\n\n// ✅ Mark when adding to queue\nvisited.add(start);\nqueue.offer(start);\nwhile (!queue.isEmpty()) {\n int node = queue.poll();\n for (int neighbor : ...) {\n if (!visited.contains(neighbor)) {\n visited.add(neighbor); // Mark immediately\n queue.offer(neighbor);\n }\n }\n}\n```\n\n### 3. Stack Overflow in Recursive DFS\n\n```java\n// ❌ Deep recursion can overflow\nvoid dfs(int node) {\n dfs(graph.get(node).get(0)); // 10,000+ deep = StackOverflow\n}\n\n// ✅ Use iterative with explicit stack\nDeque stack = new ArrayDeque<>();\nwhile (!stack.isEmpty()) {\n int node = stack.pop();\n // ...\n}\n```\n\n### 4. Wrong Data Structure for Traversal\n\n```java\n// ❌ Using List for visited - O(n) contains\nList visited = new ArrayList<>();\nif (visited.contains(node)) ... // O(n) each time!\n\n// ✅ Use HashSet - O(1) contains\nSet visited = new HashSet<>();\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: When would you use DFS over BFS?**\n\n> Use DFS for exhaustive exploration (all paths, cycle detection, topological sort) or when memory is limited. Use BFS when you need the shortest path in unweighted graphs or level-by-level processing.\n\n**Q: How do you detect a cycle in an undirected graph?**\n\n> During DFS, if you encounter a visited node that isn't your parent, there's a cycle. For BFS, it's similar - a visited node that isn't the node you came from indicates a cycle.\n\n**Q: What's the time complexity of graph traversal?**\n\n> O(V + E) for both DFS and BFS when using adjacency list. Each vertex is visited once (O(V)) and each edge is examined once (O(E)).\n\n**Q: How do you find the shortest path?**\n\n> For unweighted graphs, use BFS - it finds shortest path in O(V + E). For weighted graphs, use Dijkstra (non-negative weights) or Bellman-Ford (with negative weights).\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 10: Sorting Algorithms](dsa-cheatsheet-part-10-sorting)\n\n**Next**: [Part 12: Dijkstra's Algorithm](dsa-cheatsheet-part-12-dijkstra)\n\n---\n\n**Visualizer**: `Graph` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.691797Z","createdAt","2026-06-10T07:19:25.692080Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",5,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",4,"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","Interactive Data Structures & Algorithms","dsa-visualized-cheatsheet","description","A concise, visual reference for essential data structures and algorithms. Each article features an interactive visualizer showing how the structure/algorithm works step-by-step, along with complexity analysis, use cases, and quick reference code. Perfect for interview prep, quick review, or learning by visualization.","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},280,"Traversal","traversal",160,"Graph","graph",161,"Dfs","dfs",162,"Bfs","bfs",278,"Algorithm","algorithm",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]