Python Program: Breadth-First Search (BFS)

This Python program demonstrates the Breadth-First Search (BFS) algorithm in a graph. The BFS algorithm is used to traverse or search tree or graph data structures. It starts at a given node (often called the ‘root’ node) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

Program Explanation

The program includes a Graph class which represents the graph structure and contains methods to add edges and perform BFS traversal.

Key components of the program include:

• The Graph class which uses a dictionary to represent the adjacency list of each vertex.
• The add_edge method to add edges between vertices in the graph.
• The bfs method to perform the BFS traversal starting from a given vertex.
• The main function to create the graph, add edges, and initiate the BFS traversal.

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        """Initialize the graph with a default dictionary to hold the adjacency list."""
        self.graph = defaultdict(list)

    def add_edge(self, src, dest):
        """
        Add an edge to the graph.
        
        :param src: Source vertex
        :param dest: Destination vertex
        """
        self.graph[src].append(dest)
        self.graph[dest].append(src)  # For undirected graph

    def bfs(self, start_vertex):
        """
        Perform BFS traversal starting from a given vertex.
        
        :param start_vertex: The starting vertex for BFS traversal
        """
        visited = set()
        queue = deque([start_vertex])
        visited.add(start_vertex)

        while queue:
            current_vertex = queue.popleft()
            print(current_vertex, end=" ")

            for neighbor in self.graph[current_vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

def main():
    """
    Main function to create a graph and perform BFS traversal.
    """
    g = Graph()
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 4)
    g.add_edge(3, 4)
    g.add_edge(3, 5)

    print("Breadth First Traversal starting from vertex 0:")
    g.bfs(0)

if __name__ == "__main__":
    main()