Breadth First Search - Graph In Python

Breadth-first search (BFS) is a method of visiting all the nodes of a tree or a graph in a breadth-first manner, i.e., visiting all the nodes at a given level before moving to the next level.

Here is a basic implementation of breadth-first search on a graph in Python 3.10:

from collections import deque

class Graph:
    def __init__(self, num_of_vertices):
        self.num_of_vertices = num_of_vertices
        self.adj_list = {i: [] for i in range(num_of_vertices)}

    def add_edge(self, v, w):
        self.adj_list[v].append(w)

    def breadth_first_search(self, start_vertex):
        result = []
        visited = [False for _ in range(self.num_of_vertices)]
        queue = deque([start_vertex])

        while queue:
            vertex = queue.popleft()
            result.append(vertex)
            visited[vertex] = Truefor neighbor in self.adj_list[vertex]:
                if not visited[neighbor]:
                    queue.append(neighbor)
                    visited[neighbor] = Truereturn result

The above implementation of breadth-first search on a graph uses a deque (double-ended queue) data structure to traverse the graph in a breadth-first manner. The breadth_first_search method starts at the given start_vertex, visits all the nodes at a given level before moving to the next level, and returns a list of the nodes in the order they were visited.

Time complexity of breadth-first search in a graph:

• The time complexity of breadth-first search is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because each vertex and each edge is visited exactly once.

Space complexity of breadth-first search in a graph:

• The space complexity of breadth-first search is O(V), where V is the number of vertices in the graph. This is because in the worst case, all the vertices of the graph may be stored in the queue.