Breadth First Search

Write a program to implement a breadth-first search.

Example 1:

Input: n=6,edges={{1,2},{1,3},{2,4},{4,5},{4,6}}
Output: 1 2 3 4 5 6

Approach:

Java

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

public class BreadthFirstSearch {
    // visited list
    public static ArrayList<Integer> visited = new ArrayList<>();
    // traversal list
    public static ArrayList<Integer> ans = new ArrayList<>();

    public static void main(String[] args) {
        // Adjacency Lists
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        int v = 7;
        for (int i = 0; i < v; i++)
            adj.add(new ArrayList<>());

        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 4);
        addEdge(adj, 4, 5);
        addEdge(adj, 4, 6);
        int source = 1;
        // bfs calling
        BFSTraversal(adj, source);
        // print traversal list
        ans.forEach(i -> System.out.print(i + " "));
    }

    /**
     * @Desc: Method used for BFS
     * @param graph
     */
    private static void BFSTraversal(ArrayList<ArrayList<Integer>> g, int source) {
        // create queue
        Queue<Integer> queue = new LinkedList<>();
        // add node into queue
        queue.add(source);
        // make visited node
        visited.add(source);
        // Iterate till queue is not empty
        while (!queue.isEmpty()) {
            // get front value from queue and pop front
            int v = queue.poll();
            // print the front element of the queue
            ans.add(v);
            // iterate through the adjacency list
            // of the popped element
            for (Integer child : g.get(v)) {
                // If not visited
                if (visited.indexOf(child) == -1) {
                    // add element into queue
                    queue.add(child);
                    // make visited
                    visited.add(child);
                }
            }
        }

    }

    /**
     * @Desc : Method used for add edges
     * @param u
     * @param v
     */

    private static void addEdge(ArrayList<ArrayList<Integer>> g, int u, int v) {
        // undirected graph
        g.get(u).add(v);
        g.get(v).add(u);
    }
}

//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges

C++

#include <bits/stdc++.h>
using namespace std;
//adjacency list
vector<int> adj[1001];
//visited array to hold
//which node is visit and which
//is not
bool visited[100001];
//function to add the edge
//into the adjacency list
void addEdge(int u,int v)
{
    //undirected graph
    adj[u].push_back(v);
    adj[v].push_back(u);
}
void bfsTraversal(int node)
{
    //queue to hold the nodes
    queue<int> q;
    q.push(node);
    //make visited the current node
    visited[node]=1;
    //iterate till queue is not empty
    while(!q.empty())
      {
          //store the front element from queue
          node=q.front();
          //print the front element of the queue
          cout<<node<<" ";
          //pop out the first element of the queue
          q.pop();
          //iterate through the adjacency list
          //of the popped element
          for(int child:adj[node])
            {
                //if not visited then push into
                //queue and make it as visited
                if(visited[child]==0)
                 {
                     q.push(child);
                     visited[child]=1;
                     
                 }
            }
      }
}
int main()
{
    int n=6;
    int edges=5;
    addEdge(1,2);
    addEdge(1,3);
    addEdge(2,4);
    addEdge(4,5);
    addEdge(4,6);
    int source=1;
    cout<<"BFS Traversal is ";
    //call the bfsTraversal function 
    //on source node
    bfsTraversal(source);
    return 0;
}
//Time Complexity: O(n+m)
//where n=no of nodes,m=no of edges