Depth-First Search (DFS) is a fundamental algorithm used in graph theory to explore nodes and edges of a graph. It is one of the most commonly used graph traversal methods, which explores as far as possible along each branch before backtracking. The DFS algorithm can be applied to both directed and undirected graphs and is useful for tasks like pathfinding, connectivity checking, and topological sorting.
Depth-First Search (DFS) is an algorithm used for traversing or searching tree or graph data structures. Starting from a source node, DFS explores as far as possible along each branch before backtracking. This ensures that the algorithm visits all nodes in a graph while following the deepest path first, hence the name.
DFS can be implemented using either recursion or an explicit stack. The core idea behind DFS is to visit a node, explore its adjacent unvisited nodes, and then backtrack once all of a node's neighbors are visited.
Here’s how the DFS algorithm works, step by step:
DFS can be used in both connected and disconnected graphs. If the graph is disconnected, DFS needs to be initiated from every unvisited node.
DFS(graph, node):
if node is not visited:
mark node as visited
process node (e.g., print it)
for each neighbor of node:
if neighbor is not visited:
DFS(graph, neighbor)
Here’s a simple Python implementation of DFS using recursion:
class Graph:
def __init__(self, vertices):
self.V = vertices # Number of vertices
self.graph = {i: [] for i in range(vertices)} # Dictionary to store the adjacency list
def add_edge(self, u, v):
self.graph[u].append(v) # For directed graph; for undirected, add reverse edge too.
def dfs(self, node, visited):
# Mark the current node as visited and process it
visited[node] = True
print(node, end=" ")
# Recur for all the vertices adjacent to this vertex
for neighbor in self.graph[node]:
if not visited[neighbor]:
self.dfs(neighbor, visited)
# Example usage:
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
visited = [False] * 5 # List to keep track of visited nodes
print("DFS Traversal (starting from vertex 0):")
g.dfs(0, visited)
Output:
DFS Traversal (starting from vertex 0):
0 1 3 4 2
While the recursive implementation is easy to understand and implement, it may hit recursion limits in some cases (especially with large graphs). An iterative version of DFS uses an explicit stack to simulate the recursion process.
DFS(graph):
create an empty stack and push the starting node onto it
create a visited list to track visited nodes
while stack is not empty:
pop a node from the stack
if the node has not been visited:
mark it as visited
process the node
push all unvisited neighbors of the node onto the stack
class Graph:
def __init__(self, vertices):
self.V = vertices # Number of vertices
self.graph = {i: [] for i in range(vertices)} # Dictionary to store the adjacency list
def add_edge(self, u, v):
self.graph[u].append(v) # For directed graph; for undirected, add reverse edge too.
def dfs_iterative(self, start):
visited = [False] * self.V # List to track visited nodes
stack = [start] # Stack to simulate recursion
while stack:
node = stack.pop() # Pop the top node from the stack
if not visited[node]:
print(node, end=" ") # Process the node
visited[node] = True # Mark it as visited
# Push all unvisited neighbors to the stack
for neighbor in self.graph[node]:
if not visited[neighbor]:
stack.append(neighbor)
# Example usage:
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
print("DFS Traversal (starting from vertex 0) - Iterative:")
g.dfs_iterative(0)
Output:
DFS Traversal (starting from vertex 0) - Iterative:
0 2 1 4 3
Time Complexity: , where:
This is because the DFS algorithm visits every vertex and edge exactly once.
Space Complexity: for the visited array and the recursion stack (or explicit stack in the iterative version).