Breadth-First Traversal

Breadth-First Traversal (BFS)

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. BFS is particularly useful for finding the shortest path on unweighted graphs.

Key Characteristics

1. Level Order Traversal: BFS visits all nodes at the present "level" before moving to the next level.
2. Queue Data Structure: BFS uses a queue to keep track of the nodes that need to be explored next. This ensures that nodes are explored in the order they were discovered.
3. Shortest Path: In unweighted graphs, BFS can be used to find the shortest path between two nodes.

Algorithm Steps

1. Initialize:

   • Start from a selected node (usually the root for trees).
   • Create a queue and enqueue the starting node.
   • Maintain a list (or array) to keep track of visited nodes.

2. Process the Queue:

   • While the queue is not empty:
     • Dequeue the front node.
     • Process (or visit) the node (e.g., print its value).
     • Enqueue all unvisited adjacent nodes, marking them as visited.

3. Repeat until all nodes are visited.

BFS Implementation

Here’s an implementation of BFS using an adjacency list representation of a graph in C++:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
private:
    int V; // Number of vertices
    vector<vector<int>> adj; // Adjacency list

public:
    Graph(int v) : V(v), adj(v) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v); // Add edge from u to v
        adj[v].push_back(u); // If undirected graph, also add edge from v to u
    }

    void BFS(int start) {
        vector<bool> visited(V, false); // Track visited vertices
        queue<int> q; // Queue for BFS

        visited[start] = true; // Mark the start node as visited
        q.push(start); // Enqueue the start node

        while (!q.empty()) {
            int node = q.front(); // Get the front node
            cout << node << " "; // Process the node
            q.pop(); // Dequeue the front node

            // Visit all the adjacent nodes
            for (int i : adj[node]) {
                if (!visited[i]) { // If not visited
                    visited[i] = true; // Mark as visited
                    q.push(i); // Enqueue the adjacent node
                }
            }
        }
        cout << endl; // New line after traversal
    }
};

int main() {
    Graph g(5); // Create a graph with 5 vertices
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    cout << "BFS Traversal starting from vertex 0: ";
    g.BFS(0); // Start BFS from vertex 0

    return 0;
}

Explanation of the Code

1. Graph Class:

   • Vertices and Adjacency List: Contains the number of vertices and an adjacency list to represent edges.
   • addEdge Function: Adds edges to the graph. If the graph is undirected, it adds edges in both directions.

2. BFS Function:

   • Initializes a visited vector and a queue.
   • Marks the starting vertex as visited and enqueues it.
   • Processes nodes in the queue, marking and enqueuing their unvisited neighbors.

3. Main Function:

   • Creates a graph, adds edges, and calls the BFS function to traverse from a starting vertex.

Complexity Analysis

• Time Complexity: $O(V + E)$

  • $V$ is the number of vertices, and $E$ is the number of edges. Each vertex and edge is processed once.

• Space Complexity: $O(V)$

  • For the visited list and the queue.

Applications of BFS

1. Shortest Path: Finding the shortest path in unweighted graphs.
2. Web Crawlers: Exploring the structure of the web, where nodes are web pages and edges are links.
3. Social Networks: Finding the shortest connection path between users.
4. Network Broadcasting: Spreading information in networks efficiently.

Conclusion

Breadth-First Search is a powerful traversal algorithm that systematically explores all vertices at the current depth level before moving deeper. Its use of a queue allows for efficient exploration of nodes, making it suitable for various applications, particularly in networking and pathfinding. Understanding BFS is essential for solving problems related to graph traversal and analysis.