Implement algorithms on a graph as an adjacency list matrix Python Program

Graph Traversal: Implement algorithms like breadth-first search (BFS) or depth-first search (DFS) on a graph represented as an adjacency list or matrix Python Program?

Below are Python implementations for Breadth-First Search (BFS) and Depth-First Search (DFS) on a graph represented using an adjacency list. I'll also briefly explain the graph representation and traversal algorithms.

Graph Representation

Adjacency List: This is a common way to represent a graph. Each vertex has a list of its adjacent vertices.

Adjacency Matrix: This is another representation where a 2D matrix is used to indicate the presence of edges between vertices.

BFS (Breadth-First Search)

BFS explores all neighbors of a vertex before moving on to their neighbors. It's useful for finding the shortest path in an unweighted graph.

from collections import deque

def bfs(graph, start):

    visited = set()

    queue = deque([start])

    result = []

    while queue:

        vertex = queue.popleft()

        if vertex not in visited:

            visited.add(vertex)

            result.append(vertex)

            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

    

    return result

# Example usage:

graph_adj_list = {

    0: [1, 2],

    1: [0, 3, 4],

    2: [0, 4],

    3: [1],

    4: [1, 2]

}

print(bfs(graph_adj_list, 0))  # Output: [0, 1, 2, 3, 4]

DFS (Depth-First Search)

DFS explores as far as possible along a branch before backing up. It can be implemented using recursion or an explicit stack.

Recursive DFS

def dfs_recursive(graph, vertex, visited=None):

    if visited is None:

        visited = set()

    visited.add(vertex)

    result = [vertex]

    

    for neighbor in graph[vertex]:

        if neighbor not in visited:

            result.extend(dfs_recursive(graph, neighbor, visited))

    

    return result

# Example usage:

graph_adj_list = {

    0: [1, 2],

    1: [0, 3, 4],

    2: [0, 4],

    3: [1],

    4: [1, 2]

}

print(dfs_recursive(graph_adj_list, 0))  # Output: [0, 1, 3, 4, 2]

Iterative DFS

def dfs_iterative(graph, start):

    visited = set()

    stack = [start]

    result = []

    while stack:

        vertex = stack.pop()

        if vertex not in visited:

            visited.add(vertex)

            result.append(vertex)

            stack.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

    

    return result

# Example usage:

graph_adj_list = {

    0: [1, 2],

    1: [0, 3, 4],

    2: [0, 4],

    3: [1],

    4: [1, 2]

}

print(dfs_iterative(graph_adj_list, 0))  # Output: [0, 2, 4, 1, 3]

Explanation

1. BFS (Breadth-First Search):

   • Uses a queue to explore vertices level by level.
   • Mark vertices as visited and add their neighbors to the queue.
   • Ensures all vertices at the current level are processed before moving to the next level.

2. DFS (Depth-First Search):

   • Uses recursion or an explicit stack to explore vertices deeply before backtracking.
   • In recursive DFS, the function calls itself for each unvisited neighbor.
   • In iterative DFS, a stack is used to manage the vertices to be explored.

Complexity

• Time Complexity for both BFS and DFS: $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges.
• Space Complexity: For BFS, the space complexity is $O(V)$ due to the queue and visited set. For DFS, the space complexity is $O(V)$ due to the recursion stack or explicit stack.

These implementations will help you understand how to traverse graphs and perform various operations on them.