How to Do a Breadth First Search for a Graph

Introduction

Breadth First Search is a classic graph traversal algorithm that explores the graph layer by layer. Starting from a source node, it visits all its neighbors before moving on to the neighbors’ neighbors. This makes it especially suitable for finding the shortest path in an unweighted graph and for solving problems that require level-wise exploration.

How BFS Works

BFS starts at a selected node, marks it as visited, and then uses a queue to keep track of the nodes to visit next. At each step, the node at the front of the queue is dequeued, its unvisited neighbors are enqueued, and the process continues until the queue is empty. Unlike DFS, which uses recursion or a stack and dives deep into the graph, BFS remains shallow and visits nodes in a breadth-wise manner.

Java Implementation

Below is a Java implementation of BFS for an undirected graph using an adjacency list and a queue.

public class BFSGraphAlg {
    private int verts;
    private List<List<Integer>> adjList;

    public BFSGraphAlg(int verts) {
        this.verts = verts;
        adjList = new ArrayList<>();
        for (int i = 0; i < verts; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addGraphEdge(int source, int destination) {
        adjList.get(source).add(destination);
        adjList.get(destination).add(source); // For undirected graph
    }

    public void bfSearh(int startVertex) {
        boolean[] alreadyVisited = new boolean[verts];
        Queue<Integer> q = new LinkedList<>();

        alreadyVisited[startVertex] = true;
        q.offer(startVertex);

        while (!q.isEmpty()) {
            int currentVertex = q.poll();
            System.out.print(currentVertex + " ");

            for (int neighbor : adjList.get(currentVertex)) {
                if (!alreadyVisited[neighbor]) {
                    alreadyVisited[neighbor] = true;
                    q.offer(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFSGraphAlg graph = new BFSGraphAlg(5);
        graph.addGraphEdge(0, 1);
        graph.addGraphEdge(0, 2);
        graph.addGraphEdge(1, 3);
        graph.addGraphEdge(1, 4);

        System.out.println("BFS traversal of the graph starting from vertex 0:");
        graph.bfSearh(0);
    }
}

Example Explanation

In this example, a graph is created with 5 vertices and edges are added between vertex 0 and its neighbors, and between vertex 1 and its children. When BFS starts from vertex 0, it visits vertices in the order of their proximity: 0 1 2 3 4. The use of a queue ensures that vertices are processed in the correct breadth-wise sequence.

Applications of BFS

BFS is commonly used for shortest path problems in unweighted graphs, peer-to-peer networking, web crawling, social network analysis, and broadcasting in networks. It also plays a crucial role in algorithms such as Ford-Fulkerson for computing maximum flow in a network.

Conclusion

Breadth First Search is a robust and intuitive algorithm for exploring graphs level by level. It complements DFS by offering a breadth-wise perspective, which is often essential in problems where proximity and shortest paths matter. Mastery of BFS is vital for any developer or computer science student dealing with graphs.

You can find the example code on GitHub.