Breadth First Search

Introduction:

This is one of the graph traversal algorithms.

Problem Statement:

Print all nodes of a graph in such a away that the nodes which are nearer to start are printed first and then the later.

Algorithm

1. A graph \(G(V, E)\) and start vertex \(s\) are given.

2. We push the start node into a queue and go through a loop till queue is empty

3. In the loop, we first pop() the front node ( save it in an array or print it ) in the queue and push all its unvisited adjacent nodes in to the queue.

4. Exit when qeueue is empty. (By the end some nodes may be left out.i.e., not all nodes will be visited..guess why ?? )

Pseudo code

Pseudo code :

bfs(adjacency_list, start_vertex):
    queue q
    q.push(start_vertex)
    while !q.empty():
        u = q.front()
        q.pop()
        for v in adjacency_list[u]:
            if !visited[v]:
                q.push(v)
                visited[v] = true

Code :

        #include <bits/stdc++.h>
        using namespace std;
        
        bool visited[100] = {false};
        
        void bfs(map<int, vector<int>> &adj, int s)
        {
            vector<int>::iterator itr;
            queue<int> q;
            q.push(s);
            visited[s] = true;
            while (!q.empty())
            {
                int u = q.front();
                cout << u << " ";
                q.pop();
                for (auto u:adj[u])
                {
                    if (!visited[u])
                    {
                        q.push(u);
                        visited[u] = true;
                    }
                }
            }
        }
        
        int main()
        {
            int n;
            cin >> n;
        
            map<int, vector<int>> adj; // u - {v1, v2, .... vk}
        
            int u, v;
            for (int i = 0; i < n; i++)
            {
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
            int s;
            cout << "Enter start vertext for bfs : ";
            cin >> s;
        
            bfs(adj, s);
            cout << "\n";
        }

Complexity Analysis :

Time complexity is : \(O(|V|+|E|)\) where \(|V|\) is number of vertices and \(|E|\) is number of edges .