Back
+20 XP
Concept

Depth-First Search (DFS) & Cycle Detection

Depth-First Search plunges deep along each branch before backtracking. Implemented via recursion or an explicit stack, DFS is the champion for topological sorting, maze solving, and cycle detection 🧗.

python
graph = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []}

def dfs(node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited)
    return visited

print(dfs("A"))  # ['A', 'B', 'D', 'C'] 🧗

# 11. Depth-First Search (DFS) & Cycle Detection Depth-First Search plunges deep along each branch before backtracking. Implemented via recursion or an explicit stack, DFS is the champion for topological sorting, maze solving, and cycle detection 🧗. ```python graph = {"A": ["B", "C"], "B": ["D"], "C": [], "D": []} def dfs(node, visited=None): if visited is None: visited = [] visited.append(node) for neighbor in graph[node]: if neighbor not in visited: dfs(neighbor, visited) return visited print(dfs("A")) # ['A', 'B', 'D', 'C'] 🧗 ``` If a DFS search encounters a node currently in the active recursion call stack, it has proven the existence of a circular cycle! 🧗 --- ### Question What underlying data structure drives Depth-First Search during recursion? 🧠 - [ ] a. The function Call Stack (LIFO) 🧗 - [ ] b. A First-In First-Out Queue - [ ] c. A B-Tree Index - [ ] d. A Ring Buffer --- ### Challenge Given `g = {'A': ['B'], 'B': ['C'], 'C': []}`, implement a recursive `dfs(node, path)` appending visited nodes to `path`. Print `dfs('A', [])`. 🎯 <details> <summary>Solution</summary> ```python g = {"A": ["B"], "B": ["C"], "C": []} def dfs(node, path): path.append(node) for neighbor in g[node]: if neighbor not in path: dfs(neighbor, path) return path print(dfs("A", [])) ``` </details>

Checkpoint

What underlying data structure drives Depth-First Search during recursion? 🧠

Practice

Given `g = {'A': ['B'], 'B': ['C'], 'C': []}`, implement a recursive `dfs(node, path)` appending visited nodes to `path`. Print `dfs('A', [])`. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks