Learnitweb

Breadth First Search Algorithm

—

by

Editorial Team
in

1. Introduction

Breadth First Search (BFS) is a graph traversal algorithm. Breadth First Search starts at the root vertex and explores all nodes at a particular level before moving on to the nodes at the next level. Breadth First Search requires extra data structure, usually the queue, to keep track of the child nodes that were encountered. Breadth-first search can be generalized to be used for both undirected graphs and directed graphs with a given root node.

The time complexity of Breadth First Search can be expressed as O(V+E), since every vertex and edge will be explored in the worst case. V is the number of vertices and E is the number of edges in the graph.

2. Breadth First Search with an example

Let is see the traversal of nodes of a graph with the help of an example.

Following are the steps of Breadth First Search:

  • Define the graph and root node.
  • Mark the root visited and add to the queue.
  • Dequeue the vertex A. Mark the neighbors of A(B and E) visited and add the neighbors to the queue.
  • Dequeue the vertex B. Mark the neighbors of B (C and D) visited and add to the queue.
  • Dequeue the vertex E, mark the neighbors of E (F and G) visited and add to the queue.
  • Dequeue the nodes C, D, F and G. Since there are no neighbors, no other steps required.

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

3. Pseudocode

Following is the pseudocode for Breadth First Search

// Breadth-First Search Algorithm
BFS(graph, root):
    // Initialize an empty queue
    queue = new Queue()
	//mark root as visited
    queue.enqueue(root)

    // Create a set to keep track of visited vertices
    visited = new Set()
    visited.add(root)

    // Loop until the queue is empty
    while queue is not empty do:
        // Dequeue a vertex from the queue
        current_vertex = queue.dequeue()

        // Process the current vertex (e.g., print it or perform some action)
        process(current_vertex)

        // Get all adjacent vertices (neighbors) of the current vertex
        neighbors = graph.getNeighbors(current_vertex)

        // For each neighbor of the current vertex
        for neighbor in neighbors:
            // If the neighbor has not been visited
            if neighbor not in visited:
                // Mark it as visited
                visited.add(neighbor)
				// Mark parent of visited node
				neighbor.parent = current_vertex
                // Enqueue the neighbor
                queue.enqueue(neighbor)

4. Implementation

In this implementation, there are 3 main files:

  • Vertex: Represents a vertex or node, has methods to declare the adjacent nodes.
  • BreadthFirstSearch: Contains the traversal logic of graph
  • BreadthFirstSearchExample: The class with creates nodes, define adjacent nodes and imitates the traversal of graph.

Vertex.java

import java.util.ArrayList;
import java.util.List;

public class Vertex {
	private String name;
	private boolean visited;
	private List<Vertex> adjacencyList;
	
	public Vertex(String name) {
		this.name = name;
		this.adjacencyList = new ArrayList();
	}
	
	public void addNeighbor(Vertex vertex) {
		this.adjacencyList.add(vertex);
	}
	
	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}

	public List<Vertex> getAdjacencyList() {
		return adjacencyList;
	}

	public void setAdjacencyList(List<Vertex> adjacencyList) {
		this.adjacencyList = adjacencyList;
	}
	
	public String toString() {
		return this.name;
	}
}

BreadthFirstSearch.java

import java.util.LinkedList;
import java.util.Queue;

public class BreadthFirstSearch {
	public void traverse(Vertex root) {
		Queue<Vertex> queue = new LinkedList();
		
		root.setVisited(true);
		queue.add(root);
		
		while(!queue.isEmpty()) {
			Vertex currentVertex = queue.remove();
			System.out.println("Visited vertex: " + currentVertex);
			
			for(Vertex v: currentVertex.getAdjacencyList()) {
				if(!v.isVisited()) {
					v.setVisited(true);
					queue.add(v);
				}
			}
		}
	}
}

BreadthFirstSearchExample.java

public class BreadthFirstSearchExample {
	public static void main(String[] args) {
		BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch();
		
		Vertex a = new Vertex("A");
		Vertex b = new Vertex("B");
		Vertex c = new Vertex("C");
		Vertex d = new Vertex("D");
		Vertex e = new Vertex("E");
		Vertex f = new Vertex("F");
		Vertex g = new Vertex("G");
		
		a.addNeighbor(b);
		a.addNeighbor(e);
		
		b.addNeighbor(c);
		b.addNeighbor(d);
		
		e.addNeighbor(f);
		e.addNeighbor(g);
		
		breadthFirstSearch.traverse(a);
	}

}

5. Application of Breadth First Search

Following are some applications of Breadth First Search:

  • Shortest Path in Unweighted Graphs: BFS helps find the shortest path from a starting node to a target node in an unweighted graph. By exploring nodes level by level, it guarantees the shortest path in terms of the number of edges.
  • Web Crawlers: Web crawlers use BFS to systematically traverse the web. Starting from a seed page, they visit linked pages, ensuring that pages closer to the seed page are explored first.
  • Social Network Analysis: BFS measures the degrees of separation in social networks. By finding the shortest path between two users, we can determine how many “hops” it takes to connect them.
  • Peer-to-Peer Networks: In peer-to-peer networks, BFS efficiently searches for resources. It helps locate nodes holding the desired resource.
  • Broadcasting in Networks: BFS is used for network routing. It ensures efficient information broadcasting from one node to all others, minimizing the time taken to reach all nodes.
  • GPS Navigation Systems: GPS systems employ BFS to find the shortest path between two locations. This minimizes the number of road segments traveled.
  • Solving Puzzles and Games: Many puzzles and games, such as Rubik’s Cubes or mazes, can be tackled using BFS. It explores all possible states or moves level by level until a solution is found.
  • Cycle Detection in Graphs: BFS detects cycles in undirected graphs. By tracking visited nodes, it identifies revisited nodes before completing the current traversal depth, indicating a cycle.
  • Connectivity in Graphs: BFS determines whether a graph is connected. Starting from a node, it checks if all other nodes can be reached.
  • Finding Nodes within a Certain Distance: BFS locates all nodes within a specified distance from a starting node. This is valuable in network analysis.
  • Level Order Traversal in Trees: For trees, BFS traverses level by level. It’s useful for printing tree structures or implementing binary tree serialization/deserialization.

6. Conclusion

Breadth-First Search (BFS) is a fundamental graph traversal algorithm that systematically explores nodes level by level. It has various applications across different domains, including finding shortest paths, web crawling, social network analysis, and solving puzzles. By efficiently exploring all nodes at the current depth before moving to the next level, BFS ensures reliable and efficient traversal in graphs and trees.