Vineeth Chivukula

Understanding Breadth-First Search

Vineeth Chivukula's photo
Vineeth Chivukula
·

2 min read

Breadth-First Search (BFS) is a traversal technique used in graph data structures that explores all the vertices at the present depth level before moving on to vertices at the next depth level. This technique is often implemented using a queue data structure to keep track of the vertices to be processed.

Process

  1. Initialization: Initialize a queue and enqueue the starting vertex. Mark the starting vertex as visited.

  2. Traversal: While the queue is not empty, perform the following steps:

    1. Dequeue the front vertex from the queue.

    2. Process the vertex (e.g., print its value, check a condition, etc.).

    3. Enqueue all the adjacent (unvisited) vertices of the dequeued vertex and mark them as visited.

  3. Termination: The process terminates when the queue becomes empty, indicating that all vertices reachable from the starting vertex have been processed.

When to Use

  1. Shortest Path in Unweighted Graphs: BFS finds the shortest path from the source vertex to any other vertex in an unweighted graph.

  2. Connected Components: To check if a graph is connected or to find all the connected components in an undirected graph.

  3. Level Order Traversal: To traverse or explore the vertices level by level.

  4. Cycle Detection: To detect cycles in an undirected graph.

  5. Bipartite Graph Check: To check if a graph is bipartite.

Time Complexity

The BFS traversal has a time complexity of 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 processed exactly once.

Implementation

// TC: O(V+E)
// SC: O(V)

import java.util.LinkedList;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    @SuppressWarnings({ "unchecked", "rawtypes" })
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList();
        }
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();
        visited[s] = true;
        queue.add(s);
        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            for (int i : adj[s]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
        g.BFS(2);
    }
}

Thank you for reading!

You can support me by buying me a book.

BFSBreadth-Fist-SearchDSA