Untitled

 avatar
unknown
plain_text
a year ago
1.0 kB
5
Indexable
from collections import deque
class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        self.graph[u].append(v)

    def bfs(self, start):
        visited = set()
        queue = deque([start])
        traversal = []

        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                traversal.append(vertex)
                visited.add(vertex)
                neighbors = self.graph.get(vertex, [])
                for neighbor in neighbors:
                    if neighbor not in visited:
                        queue.append(neighbor)
        return traversal

if __name__ == "__main__":
    graph = Graph()
    graph.add_edge(0, 1)
    graph.add_edge(0, 2)
    graph.add_edge(1, 2)
    graph.add_edge(2, 0)
    graph.add_edge(2, 3)
    graph.add_edge(3, 3)

    start_vertex = 2
    print("BFS traversal from vertex", start_vertex, ":", graph.bfs(start_vertex))

Editor is loading...
Leave a Comment