Depth-First Search (DFS)
Algorithms
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Algorithm
DFS can be implemented using either recursion or an explicit stack:
- Start from a given vertex
- Mark the vertex as visited
- For each unvisited neighbor, recursively perform DFS
- Backtrack when no more unvisited neighbors exist
Time Complexity
The time complexity is , where is the number of vertices and is the number of edges.
Implementation
class Graph:
def __init__(self):
self.graph = {{}}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append(v)
self.graph[v].append(u)
def dfs_recursive(self, node, visited):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in self.graph[node]:
self.dfs_recursive(neighbor, visited)
def dfs_stack(self, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=' ')
visited.add(node)
stack.extend(neighbor for neighbor in self.graph[node] if neighbor not in visited)
def print_graph(self):
for node in self.graph:
print("{}: {}".format(node, ', '.join(map(str, self.graph[node]))))
# Example usage
if __name__ == "__main__":
g = Graph()
# Add edges to the graph
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('B', 'E')
g.add_edge('C', 'F')
g.add_edge('C', 'G')
# Print the graph
print("Graph Representation:")
g.print_graph()
# Perform DFS using recursion
print("\nDFS Recursive Traversal:")
visited_recursive = set()
g.dfs_recursive('A', visited_recursive)
# Perform DFS using a stack
print("\n\nDFS Stack Traversal:")
g.dfs_stack('A')Exercises
A full exercise set is available for this topic, structured as one worked example + 7 practice problems (across 7 surface contexts) + 2 pattern-resistant check problems.
Open the Depth-First Search exercise set