Graph Breadth First Search (BFS)

1. Pick the starting node and visit it.
2. Visit all the unvisited neighbors of the current node (in order).
3. Move to the next node in the queue.
4. Repeat steps 2 and 3 until there are no more nodes in the queue.

Visualization

BFS in tree

BFS in maze

BFS in graph

DFS vs BFS

Algorithm

There is one primary approach to implement a breadth first search for graphs, that is, using a queue.

1. Prepare variables
   • to_visit: Stack to store verteces that needs to be visited. Initial value is the start vertex.
   • visited: Hash set to store verteces that has already been visited.
   • path: List to store all verteces traversed by to_visit.
2. Keep dequeueing to_visit queue while it’s not empty. For each vertex.
3. If the current vertex is already in visited, we skip it.
4. If not, we add the vertex to visited and path.
5. For each adjacent vertex of the current vertex:
6. Add the adjacent vertex into the queue.

Implementation

To see the complete code, go to Graph

    def bfs(self, start: _Vertex) -> list[_Vertex]:
        to_visit: Deque[_Vertex] = deque([start])
        visited: set[_Vertex] = set()
        path: list[_Vertex] = []
 
        while len(to_visit) != 0:
            curr = to_visit.popleft()
 
            if curr not in visited:
                visited.add(curr)
                path.append(curr)
 
                for neigh in self._get_neighs(curr):
                    to_visit.append(neigh)
 
        return path
 
    @abstractmethod
    def _get_neighs(self, vertex: _Vertex) -> list[_Vertex]: ...