Leetcode BFS to traverse a graph level by level

BFS to traverse a graph level by level

Breadth First Search (BFS) is a fundamental graph traversal algorithm. It involves visiting all the connected nodes of a graph in a level-by-level manner. In this article, we will look into the concept of BFS and how it can be applied to graphs effectively.

Breadth First Search (BFS) for a Graph

Breadth First Search (BFS) is a graph traversal algorithm that explores all the vertices in a graph at the current depth before moving on to the vertices at the next depth level. It starts at a specified vertex and visits all its neighbors before moving on to the next level of neighbors. BFS is commonly used in algorithms for pathfinding, connected components, and shortest path problems in graphs.

Relation between BFS for Graph and BFS for Tree

Breadth-First Traversal (BFS) for a graph is similar to the Breadth-First Traversal of a tree. The only catch here is, that, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we divide the vertices into two categories: Visited and Not visited. A Boolean visited array is used to mark the visited vertices. For simplicity, it is assumed that all vertices are reachable from the starting vertex. BFS uses a queue data structure for traversal.

Breadth First Search (BFS) for a Graph Algorithm

Let’s discuss the algorithm for the BFS: Initialization: Enqueue the starting node into a queue and mark it as visited. Exploration: While the queue is not empty: Dequeue a node from the queue and visit it (e.g., print its value). For each unvisited neighbor of the dequeued node: Enqueue the neighbor into the queue. Mark the neighbor as visited. Termination: Repeat step 2 until the queue is empty. This algorithm ensures that all nodes in the graph are visited in a breadth-first manner, starting from the starting node.

Implementation of BFS for Graph using Adjacency List


           
           import java.util.LinkedList;
           import java.util.Queue;
           class Graph {
               int vertices;
               LinkedList[] adjacencies;
           
               Graph(int vertices) {
                   this.vertices = vertices;
                   adjacencies = new LinkedList[vertices];
                   for (int i = 0; i < vertices; ++i)
                       adjacencies[i] = new LinkedList<>();
               }
           
               void addEdge(int u, int v) {
                   adjacencies[u].add(v);
               }
           
               void bfs(int startNode) {
                   Queue queue = new LinkedList<>();
                   boolean[] visited = new boolean[vertices];
           
                   visited[startNode] = true;
                   queue.add(startNode);
           
                   while (!queue.isEmpty()) {
                       int currentNode = queue.poll();
                       System.out.print(currentNode + " ");
           
                       for (int neighbor : adjacencies[currentNode]) {
                           if (!visited[neighbor]) {
                               visited[neighbor] = true;
                               queue.add(neighbor);
                           }
                       }
                   }
               }
           }
           
           public class Hello {
               public static void main(String[] args) {
                   int vertices = 5;
                   Graph graph = new Graph(vertices);
                   graph.addEdge(0, 1);
                   graph.addEdge(0, 2);
                   graph.addEdge(1, 3);
                   graph.addEdge(1, 4);
                   graph.addEdge(2, 4);
           
                   // Perform BFS traversal starting from vertex 0
                   System.out.print("Breadth First Traversal starting from vertex 0: ");
                   graph.bfs(0);
               }
           }

Breadth First Traversal starting from vertex 0: 0 1 2 3 4

Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges.

Auxiliary Space: O(V)

Complexity Analysis of Breadth-First Search (BFS) Algorithm:

Time Complexity of BFS Algorithm: O(V + E)

BFS explores all the vertices and edges in the graph. In the worst case, it visits every vertex and edge once. Therefore, the time complexity of BFS is O(V + E), where V and E are the number of vertices and edges in the given graph.

Space Complexity of BFS Algorithm: O(V)

BFS uses a queue to keep track of the vertices that need to be visited. In the worst case, the queue can contain all the vertices in the graph. Therefore, the space complexity of BFS is O(V), where V and E are the number of vertices and edges in the given graph.

Applications of BFS in Graphs:

BFS has various applications in graph theory and computer science, including:

Shortest Path Finding: BFS can be used to find the shortest path between two nodes in an unweighted graph. By keeping track of the parent of each node during the traversal, the shortest path can be reconstructed.
Cycle Detection: BFS can be used to detect cycles in a graph. If a node is visited twice during the traversal, it indicates the presence of a cycle.
Connected Components: BFS can be used to identify connected components in a graph. Each connected component is a set of nodes that can be reached from each other.
Topological Sorting: BFS can be used to perform topological sorting on a directed acyclic graph (DAG). Topological sorting arranges the nodes in a linear order such that for any edge (u, v), u appears before v in the order.
Level Order Traversal of Binary Trees: BFS can be used to perform a level order traversal of a binary tree. This traversal visits all nodes at the same level before moving to the next level.
Network Routing: BFS can be used to find the shortest path between two nodes in a network, making it useful for routing data packets in network protocols.

Breadth-First Search in graph