Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It is widely used in computer science for tasks such as solving puzzles, finding connected components, topological sorting, and detecting cycles in graphs. DFS operates on both directed and undirected graphs and works for graph representations like adjacency lists and matrices.
Key Features of DFS
1. Exploration Depth:
DFS dives deep into a graph by following one branch until it reaches the end before backtracking.
2. Stack-Based Approach:
DFS can be implemented using either recursion (implicit stack) or an explicit stack data structure.
3. Graph Representation:
Works efficiently on adjacency lists and matrices.
4. Time Complexity:
The time complexity is , where is the number of vertices and is the number of edges.
5. Space Complexity:
Space complexity depends on the recursion stack or explicit stack used, making it in the worst case.
DFS Algorithm
1. Start at a source node (vertex).
2. Mark the current node as visited.
3. Explore all unvisited neighbors recursively.
4. Backtrack when no unvisited neighbors are left.
Code Boilerplate: DFS in Python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
# Mark the current node as visited
visited.add(start)
print(start, end=” “) # Process the node
# Explore neighbors
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Example graph (Adjacency List)
graph = {
‘A’: [‘B’, ‘C’],
‘B’: [‘D’, ‘E’],
‘C’: [‘F’],
‘D’: [],
‘E’: [‘F’],
‘F’: []
}
# Perform DFS starting at vertex ‘A’
print(“DFS Traversal:”)
dfs(graph, ‘A’)
Schematic Representation
Consider a graph:
A
/ \
B C
/ \ \
D E — F
DFS starting from A would visit nodes in this order: A → B → D → E → F → C.
Applications of DFS
1. Pathfinding:
Determines if a path exists between nodes in a graph.
2. Cycle Detection:
Identifies cycles in directed or undirected graphs.
3. Topological Sorting:
Used in Directed Acyclic Graphs (DAGs) for scheduling tasks.
4. Connected Components:
Finds all connected components in a graph.
DFS is a versatile algorithm that forms the backbone of many graph-related tasks. Its recursive and iterative implementations make it highly adaptable to diverse problems in computational scenarios.
The article above is rendered by integrating outputs of 1 HUMAN AGENT & 3 AI AGENTS, an amalgamation of HGI and AI to serve technology education globally.