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 🧗.
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>