Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order, i.e., exploring all the vertices at the same level before moving to the next level.

BFS is often used to find the shortest path between two vertices in an unweighted graph. By exploring the graph level by level, BFS ensures that the first path found between two vertices is the shortest path.

The algorithm starts at a specified vertex, visits all its neighbors, then visits the neighbors' neighbors, and so on. This process continues until all the vertices have been visited.

To implement BFS, we can use a queue data structure to keep track of the vertices to be visited. We start by enqueueing the initial vertex and mark it as visited. Then, while the queue is not empty, we dequeue a vertex, visit it, and enqueue its unvisited neighbors. By doing so, we ensure that the vertices are visited in the order they were discovered, i.e., in breadth-first order.

Here is an example of how BFS can be implemented in Java:

1{{code}}

In this example, we have a Graph class that represents a graph using an adjacency map. The Graph class has a addEdge method to add edges between vertices, a getNeighbors method to get the neighbors of a vertex, and a bfs method that implements the breadth-first search algorithm. The bfs method takes a Graph object and a start vertex as input and performs the breadth-first search traversal, printing the visited vertices.

BFS can be used to solve various graph-related problems, such as finding the shortest path between two vertices, finding connected components, and checking bipartiteness. Its time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

BFS is a fundamental algorithm in graph theory and has applications in various domains, such as social network analysis, web crawling, and shortest path routing.

xxxxxxxxxx

}

class Main {

  public static void main(String[] args) {

    // Replace with your Java logic here

    // Create a graph

    Graph graph = new Graph();

    graph.addEdge(1, 2);

    graph.addEdge(1, 3);

    graph.addEdge(2, 4);

    graph.addEdge(3, 4);

    graph.addEdge(4, 5);

    // Perform breadth-first search

    BFS.bfs(graph, 1);

  }

}

​

class Graph {

  private final Map<Integer, List<Integer>> adjacencyMap;

  public Graph() {

    adjacencyMap = new HashMap<>();

  }

  public void addEdge(int source, int destination) {

    adjacencyMap.computeIfAbsent(source, ArrayList::new).add(destination);

    adjacencyMap.computeIfAbsent(destination, ArrayList::new).add(source);

  }

  public List<Integer> getNeighbors(int vertex) {