Depth-First Search (DFS)
Depth-First Search (DFS) is one of the fundamental search algorithms used for exploring graphs. It traverses or explores a graph by starting at a given node and visiting all its neighbors before backtracking.
DFS can be implemented using recursion or a stack.
Recursive Approach
In the recursive approach, we start at a given node and recursively visit its neighbors.
Here's an example of a recursive DFS implementation in Python:
PYTHON
1# Recursive DFS function
2
3def dfs_recursive(graph, node, visited):
4 if node not in visited:
5 visited.add(node)
6 print(node)
7 neighbors = graph[node]
8 for neighbor in neighbors:
9 dfs_recursive(graph, neighbor, visited)
10
11# Example graph
12graph = {
13 'A': ['B', 'C'],
14 'B': ['D', 'E'],
15 'C': ['F'],
16 'D': [],
17 'E': ['F'],
18 'F': []
19}
20
21# Perform recursive DFS
22visited = set()
23dfs_recursive(graph, 'A', visited)xxxxxxxxxx25
def dfs(graph, start_node): visited = set() stack = [start_node] while stack: node = stack.pop() if node not in visited: visited.add(node) print(node) neighbors = graph[node] stack.extend(neighbors)# Example graphgraph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}# Perform DFSdfs(graph, 'A')OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
