Graph algorithms can seem intimidating at first but once you understand the fundamental traversal algorithms, patterns and practice few problems, they get much easier.
In this article, we’ll cover the 10 most common Graph algorithms and patterns that appear in coding interviews, explaining how they work, when to use them, how to implement them and LeetCode problems you can practice to get better at them.
DFS is a fundamental graph traversal algorithm used to explore nodes and edges of a graph systematically.
It starts at a designated root node and explores as far as possible along each branch before backtracking.
DFS is particularly useful in scenarios like:
Find a path between two nodes.
Checking if a graph contains any cycles.
Identifying isolated subgraphs within a larger graph.
Topological Sorting: Scheduling tasks without violating dependencies.
Start at the Root Node: Mark the starting node as visited.
Explore Adjacent Nodes: For each neighbor of the current node, do the following:
If the neighbor hasn't been visited, recursively perform DFS on it.
Backtrack: Once all paths from a node have been explored, backtrack to the previous node and continue the process.
Termination: The algorithm ends when all nodes reachable from the starting node have been visited.
Recursive DFS: Uses system recursion (function call stack) to backtrack.
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(f"Visiting {node}")
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visitedExplanation:
Base Case: If visited is not provided, initialize it.
Visit the Node: Add the current node to the visited set.
Recursive Call: For each unvisited neighbor, recursively call dfs_recursive.
Iterative DFS: Uses an explicit stack to mimic the function call behavior.
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(f"Visiting {node}")
# Add neighbors to stack
stack.extend([neighbor for neighbor in graph[node] if neighbor not in visited])
return visitedExplanation:
Initialize:
A visited set to keep track of visited nodes.
A stack with the starting node.
Process Nodes:
Pop a node from the stack.
If unvisited, mark as visited and add its neighbors to the stack.
Time Complexity: O(V + E), where
Vis the number of vertices andEis the number of edges. This is because the algorithm visits each vertex and edge once.Space Complexity: O(V), due to stack used for recursion (in recursive implementation) or an explicit stack (in iterative implementation).
BFS is a fundamental graph traversal algorithm that systematically explores the vertices of a graph level by level.
Starting from a selected node, BFS visits all of its immediate neighbors first before moving on to the neighbors of those neighbors. This ensures that nodes are explored in order of their distance from the starting node.
BFS is particularly useful in scenarios such as:
Finding the minimal number of edges between two nodes.
Processing nodes in a hierarchical order, like in tree data structures.
Finding people within a certain degree of connection in a social network.
Initialization: Create a queue and enqueue the starting node.
Mark the starting node as visited.
Traversal Loop: While the queue is not empty:
Dequeue a node from the front of the queue.
Visit all unvisited neighbors:
Mark each neighbor as visited.
Enqueue the neighbor.
Termination: The algorithm terminates when the queue is empty, meaning all reachable nodes have been visited.
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
vertex = queue.popleft()
print(f"Visiting {vertex}")
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Time Complexity: O(V + E), where
Vis the number of vertices andEis the number of edges. This is because BFS visits each vertex and edge exactly once.Space Complexity: O(V) for the queue and visited set used for traversal.
Topological Sort algorithm is used to order the vertices of a Directed Acyclic Graph (DAG) in a linear sequence, such that for every directed edge u → v, vertex u comes before vertex v in the ordering.
Essentially, it arranges the nodes in a sequence where all prerequisites come before the tasks that depend on them.
Topological Sort is particularly useful in scenarios like:
Determining the order of tasks while respecting dependencies (e.g., course prerequisites, build systems).
Figuring out the order to install software packages that depend on each other.
Ordering files or modules so that they can be compiled without errors due to missing dependencies.
There are two common methods to perform a Topological Sort:
def topological_sort_dfs(graph):
visited = set()
stack = []
def dfs(vertex):
visited.add(vertex)
for neighbor in graph.get(vertex, []):
if neighbor not in visited:
dfs(neighbor)
stack.append(vertex)
for vertex in graph:
if vertex not in visited:
dfs(vertex)
return stack[::-1] # Reverse the stack to get the correct orderExplanation:
DFS Traversal: Visit each node and recursively explore its neighbors.
Post-Order Insertion: After visiting all descendants of a node, add it to the stack.
Result: Reverse the stack to obtain the topological ordering.
from collections import deque
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] = in_degree.get(v, 0) + 1
queue = deque([u for u in in_degree if in_degree[u] == 0])
topo_order = []
while queue:
u = queue.popleft()
topo_order.append(u)
for v in graph.get(u, []):
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(topo_order) == len(in_degree):
return topo_order
else:
raise Exception("Graph has at least one cycle")Explanation:
Compute In-Degrees: Calculate the number of incoming edges for each node.
Initialize Queue: Start with nodes that have zero in-degree.
Process Nodes:
Dequeue a node, add it to the topological order.
Reduce the in-degree of its neighbors.
Enqueue neighbors whose in-degree becomes zero.
Cycle Detection: If the topological order doesn't include all nodes, the graph contains a cycle.
Time Complexity: O(V + E) since each node and edge is processed exactly once.
Space Complexity: O(V) for storing the topological order and auxiliary data structures like the visited set or in-degree array.