Graph Traversal — Breadth First Search Algorithm

Deep dive into Breadth First Search graph traversal algorithm.

Breath First Search (BFS) is a graph traversal algorithm that explores a graph by systematically visiting all the vertices in breadth-first order, starting from a given source vertex. The algorithm explores vertices level by level, visiting all the neighbors of a vertex before moving on to the next level.

BFS guarantees that all vertices are visited in increasing order of their distance from the source vertex. It is particularly useful when we want to find the shortest path between two vertices or when we want to visit all vertices in a connected component.

Here’s the pseudocode for the Breadth First Search (BFS) algorithm:

BFS(graph, startVertex):
    // Create a queue for BFS traversal
    queue = new Queue()

    // Mark the start vertex as visited and enqueue it
    mark startVertex as visited
    enqueue startVertex into queue

    // Loop until the queue becomes empty
    while queue is not empty:
        // Dequeue a vertex from the front of the queue
        currentVertex = dequeue from queue

        // Process the current vertex (e.g., print it or perform some operation on it)

        // Explore all the unvisited neighbors of the current vertex
        for each neighbor in neighbors of currentVertex:
            if neighbor is not visited:
                // Mark the neighbor as visited and enqueue it
                mark neighbor as visited
                enqueue neighbor into queue

In the above pseudocode, graph represents the graph object or data structure containing the vertices and their connections. startVertex is the vertex from which the BFS traversal begins.

The algorithm starts by marking the startVertex as visited and enqueuing it into a queue data structure. Then, while the queue is not empty, it dequeues a vertex from the front of the queue, processes it, and explores its unvisited neighbors. For each unvisited neighbor, it marks it as visited and enqueues it into the queue.

This process continues until the queue becomes empty, ensuring that all vertices reachable from the startVertex are visited.

Breadth First Search Implementation in Java

    // BFS implementation
    public void bfs(T startVertex) {
        Map<T, Boolean> visited = new HashMap<>();
        Queue<T> queue = new LinkedList<>();

        visited.put(startVertex, true);
        queue.offer(startVertex);

        while (!queue.isEmpty()) {
            T vertex = queue.poll();
            System.out.print(vertex + " ");

            List<T> neighbors = adjacencyList.get(vertex);
            if (neighbors != null) {
                for (T neighbor : neighbors) {
                    if (!visited.containsKey(neighbor)) {
                        visited.put(neighbor, true);
                        queue.offer(neighbor);
                    }
                }
            }
        }
    }