Write Breadth first search technique and its use.

Breadth-first search (BFS) is a graph traversal algorithm that explores vertices in a graph layer by layer. It starts at a given source node and explores all of the neighboring nodes at the present depth before moving on to nodes at the next depth level. BFS is particularly useful for finding the shortest path on unweighted graphs.

Step-by-Step Approach to Breadth-First Search

1. Start by selecting a source node (starting point).
2. Create a queue and mark the source node as visited and enqueue it.

3. While the queue is not empty:

   • Dequeue a vertex from the queue. Let's call this vertex current.
   • Visit the current vertex and process it if necessary (e.g., print out the vertex).
   • For each adjacent vertex v of current that has not been visited:
     • Mark v as visited.
     • Enqueue v.

4. Continue this process until the queue is empty.

5. Once the queue is empty, the BFS traversal is complete.

Pseudocode

BFS(graph, startVertex):
    create a queue Q
    mark startVertex as visited and enqueue it into Q

    while Q is not empty:
        current = Q.dequeue()
        process current

        for each vertex v adjacent to current:
            if v is not visited:
                mark v as visited
                Q.enqueue(v)

Example

Consider the following graph:

1 -- 2
|    |
4 -- 3

Let's perform BFS starting from vertex 1:

1. Start with vertex 1: Mark it as visited and enqueue it.
2. Queue: [1]
3. Dequeue 1 and visit its neighbors (2 and 4): Mark them as visited and enqueue them.
4. Queue: [2, 4]
5. Dequeue 2 and visit its neighbor (3): Mark it as visited and enqueue it.
6. Queue: [4, 3]
7. Dequeue 4: Since all its neighbors are visited, do nothing.
8. Queue: [3]
9. Dequeue 3: Since all its neighbors are visited, do nothing.
10. Queue: []
11. The queue is empty, so BFS is complete.

The BFS traversal of the graph starting from vertex 1 is: 1, 2, 4, 3.

Uses of Breadth-First Search

Use Case	Description
Shortest Path	BFS is used to find the shortest path between two nodes in an unweighted graph.
Connectivity	It can determine if the graph is connected by checking if all nodes are visited during the traversal.
Level Order Traversal	In trees, BFS is used for level order traversal, where nodes are visited level by level.
Cycle Detection	BFS can be used to detect cycles in an undirected graph.
Serialization/Deserialization	BFS can be used to serialize and deserialize a binary tree or graph structure.
Finding All Nodes Within One Connected Component	BFS can explore all nodes within one connected component of a graph.
Web Crawling	BFS is used in web crawling to visit pages and their immediate neighbors.
Social Networking	BFS can be used to find people within a certain distance from a person in a social network.

Complexity

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. The space complexity is O(V), as it needs to store the visited vertices and the queue.

Conclusion

Breadth-first search is a fundamental graph traversal algorithm with a wide range of applications, from finding the shortest path to web crawling. Its level-by-level approach makes it particularly useful for problems related to the shortest path on unweighted graphs or level-wise processing.