Write a Python program to implement breadth-first search.

from collections import deque class Graph: def init(self): self.adjacency_list = {} def add_edge(self, u, v): # Add an edge from u to v (assuming a directed graph) if u not in self.adjacency_list: self.adjacency_list[u] = [] self.adjacency_list[u].append(v) def bfs(self, start_vertex): visited = set() queue = deque() visited.add(start_vertex) queue.append(start_vertex) while queue: current_vertex = queue.popleft() print(current_vertex, end=' ') for neighbor in self.adjacency_list.get(current_vertex, []): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) # Example usage if name == "main": g = Graph() g.add_edge(1, 2) g.add_edge(1, 3) g.add_edge(2, 4) g.add_edge(2, 5) g.add_edge(3, 6) g.add_edge(5, 6) print("Breadth First Traversal starting from vertex 1:") g.bfs(1)

Apr 29, 2025 - 08:39

Write a Python program to implement breadth-first search.

from collections import deque

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    def add_edge(self, u, v):
        # Add an edge from u to v (assuming a directed graph)
        if u not in self.adjacency_list:
            self.adjacency_list[u] = []
        self.adjacency_list[u].append(v)

    def bfs(self, start_vertex):
        visited = set()
        queue = deque()

        visited.add(start_vertex)
        queue.append(start_vertex)

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

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

# Example usage
if __name__ == "__main__":
    g = Graph()
    g.add_edge(1, 2)
    g.add_edge(1, 3)
    g.add_edge(2, 4)
    g.add_edge(2, 5)
    g.add_edge(3, 6)
    g.add_edge(5, 6)

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