Graph Algorithms

Graph Algorithms

In this blog, I will cover 2 popular algorithms - DFS and BFS.

DFS

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores nodes and edges to visit all vertices of a graph or tree. It starts from a selected node (often referred to as the “root” in the case of trees or an arbitrary starting point in graphs) and explores as far as possible along each branch before backtracking.

Key Concepts in DFS:

1. Stack-Based Approach (Recursive or Iterative):

   • DFS can be implemented using a stack (either explicitly through recursion or using an explicit stack data structure).
   • The basic idea is to push nodes onto the stack and explore each node deeper and deeper until the deepest node (or a dead end) is reached, then backtrack.

2. Visited Nodes:

   • To avoid processing a node more than once, DFS keeps track of visited nodes using a set or array.
   • Nodes are marked as visited when they are pushed onto the stack (or at the start of the recursive call) and are processed when popped off the stack.

3. Traversal Order:

   • DFS does not necessarily visit nodes in the order they are stored in the graph data structure.
   • The order depends on the structure of the graph and the choice of traversal (e.g., pre-order, in-order, post-order for trees).

Recursive DFS Algorithm (Pre-order traversal for Trees):

Here’s a simplified version of the recursive DFS algorithm for a tree:

def dfs(node, visited):
    if node is None:
        return
    
    visited.add(node)
    print(node.val)  # Process node
    
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs(neighbor, visited)

Iterative DFS Algorithm using Stack:

Here’s a simplified version of the iterative DFS algorithm using an explicit stack for a graph represented as an adjacency list:

def dfs_iterative(graph, start):
    stack = [start]
    visited = set()
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)  # Process node
            
            # Push neighbors onto stack
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

Example Explanation:

Consider a graph represented as an adjacency list:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

Starting from node 'A', DFS would explore the graph in the order A -> B -> D -> E -> F -> C. It explores each branch as far as possible before backtracking to unexplored nodes.

Applications:

• Pathfinding: Finding paths between two nodes.
• Cycle Detection: Detecting cycles in a graph.
• Topological Sorting: Ordering nodes in a directed acyclic graph (DAG).
• Connected Components: Finding connected components in an undirected graph.

DFS is versatile and widely used due to its simplicity and effectiveness in many graph-related problems. However, it may not be suitable for finding shortest paths in weighted graphs without modifications.

BFS

Breadth-First Search (BFS) is another fundamental graph traversal algorithm that explores nodes and edges level by level. It starts from a selected node (often referred to as the “root” in the case of trees or an arbitrary starting point in graphs) and explores all neighbors at the present depth level before moving on to nodes at the next depth level.

Key Concepts in BFS:

1. Queue-Based Approach:

   • BFS uses a queue data structure to facilitate exploration. Nodes are added to the back of the queue when discovered and removed from the front when visited.
   • This ensures that nodes are visited in the order they were discovered, maintaining the level-order traversal property.

2. Visited Nodes:

   • To prevent processing a node more than once (which could lead to infinite loops in cyclic graphs), BFS keeps track of visited nodes using a set or array.
   • Nodes are marked as visited when they are dequeued for processing.

3. Traversal Order:

   • BFS explores nodes level by level. It first visits all nodes at the current depth level before moving on to nodes at the next depth level.
   • This leads to a breadth-first or level-order traversal of the graph.

Iterative BFS Algorithm using Queue:

Here’s a simplified version of the iterative BFS algorithm using a queue for a graph represented as an adjacency list:

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    visited = set([start])
    
    while queue:
        node = queue.popleft()
        print(node)  # Process node
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Example Explanation:

Consider a graph represented as an adjacency list:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

Starting from node 'A', BFS would explore the graph in the order A -> B -> C -> D -> E -> F. It explores all neighbors at the current depth level (starting with 'A'), before moving on to nodes at the next depth level (neighbors of 'A'), ensuring all nodes at the current level are visited before any nodes at the next level.

Applications:

• Shortest Path: BFS can be used to find the shortest path between two nodes in an unweighted graph.
• Level Order Traversal: Useful for traversing hierarchical structures like trees or finding all nodes at a specific distance from the start node.
• Connected Components: Identifying connected components in an undirected graph.
• Bipartiteness Testing: Determining if a graph can be colored using two colors without any two adjacent vertices having the same color.

BFS is efficient for searching and exploring in graphs where the shortest path is needed or when nodes are at varying depths, making it a versatile and widely used algorithm in graph theory and computer science.