Graph Traversal (DFS, BFS)

Graph traversal involves visiting all the nodes of a graph systematically. There are two primary methods for this: Depth-First Search (DFS) and Breadth-First Search (BFS).

Depth-First Search (DFS)

Concept: Explores as far as possible along each branch before backtracking.

Data Structure: Stack (implicitly used through recursion)

Algorithm:

1. Visit the current node.
2. Mark the current node as visited.
3. Recursively visit all adjacent unvisited nodes.

Code Implementation:

def dfs_util(graph, visited, node):
    visited[node] = True
    print(node, end=' ')
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs_util(graph, visited, neighbor)

def dfs(graph, start):
    visited = [False] * len(graph)
    dfs_util(graph, visited, start)

Breadth-First Search (BFS)

Concept: Explores all neighbors at the present depth before moving on to the next depth level.

Data Structure: Queue

Algorithm:

1. Enqueue the starting node.
2. While the queue is not empty:
3. Dequeue a node.
4. Visit the dequeued node.
5. Enqueue all unvisited neighbors of the dequeued node.

Code Implementation:

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)
    queue = deque([start])
    visited[start] = True
    while queue:   
        node = queue.popleft()
        print(node, end=' ')

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)   

Choosing the Right Approach

• DFS: Suitable for problems involving exploration, backtracking, and finding paths.
• BFS: Ideal for finding shortest paths in unweighted graphs, exploring all neighbors at a given level, and algorithms like Dijkstra’s.

Graph Traversal (DFS, BFS) using a Class-Based Approach

Class-Based Graph Representation

class Graph:
    def __init__(self, num_vertices, directed=False):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
        self.directed = directed

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        if not self.directed:
            self.adj_list[v].append(u)

Depth-First Search (DFS)

class Graph(Graph):
    def dfs_util(self, visited, v):
        visited[v] = True
        print(v, end=' ')
        for neighbor in self.adj_list[v]:
            if not visited[neighbor]:
                self.dfs_util(visited, neighbor)
    
    def dfs(self, start):
        visited = [False] * self.num_vertices
        self.dfs_util(visited, start)

Breadth-First Search (BFS)

from collections import deque

class Graph(Graph):
    def bfs(self, start):
        visited = [False] * self.num_vertices
        queue = deque([start])
        visited[start] = True
        
        while queue:
            v = queue.popleft()
            print(v, end=' ')
            for neighbor in self.adj_list[v]:
                if not visited[neighbor]:   
                    visited[neighbor] = True
                    queue.append(neighbor)

Explanation

• Graph class: Defines the basic structure of a graph with adjacency list representation.
• DFS and BFS methods: Inherited from the Graph class, providing implementations for the respective traversal algorithms.
• dfs_util: Helper function for DFS to recursively explore neighbors.

Example Usage

g = Graph(4)

g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)

print("DFS traversal:")
g.dfs(0)
print("\nBFS traversal:")
g.bfs(0)

Key Points

• This class-based approach encapsulates graph properties and traversal methods within a single class.
• It provides a clear separation of concerns and improves code organization.
• You can extend the Graph class to include additional functionalities like finding shortest paths, detecting cycles, etc.