[Solved] The BFS traversal Contest Problem

The BFS traversal: You are given a graph G with edges E. You have to perform BFS on this graph.

Note: Perform BFS in the order the elements appear in the adjacency list (left to right).

The BFS traversal Contest Problem

Input Format:
The first line of input contains T denoting the number of testcases. T testcases follow. Each testcase contains three lines of input. The first line contains E denoting the number of edges. The second line contains E pairs of integers that denote the edge’s starting and ending vertices. The third line contains origin which is the starting vertex for BFS.

Output Format:
For each testcase, in a new line, print the BFS traversal of the graph G.

Your Task:
This is a function problem so you need not worry about taking input and creating graph. You only have to complete the function BFS that takes an integer origin as parameter. This origin is the vertex from which BFS starts.
Also, if a certain vertex can’t be reaches in the traversal then don’t print it.

Constraints:
1 <= T <= 100
1 <= edges <= 100

Examples:
Input:
1
6
0 1 0 2 1 2 2 0 2 3 8 9
2
Output:
2 0 3 1

Explanation:
Testcase1:
The graph is as follows:

As it is evident in the above picture, we start from the vertex 2. So BFS from 2 would give us 2 0 3 1.

Solution

//Back-end complete function Template for C++



void BFS(int origin)
    {
        unordered_map<int,bool>visited;
        
        for(auto it=adj.begin();it!=adj.end();it++)
        {
            visited[it->first]=false;
        }
        
        queue<int>q;
        
        q.push(origin);
        visited[origin]=true;
        
        while(!q.empty())
        {
            int s=q.front();
            q.pop();
            
            cout<<s<<" ";
            
            for(int i=0;i<adj[s].size();i++)
            {
                if(!visited[adj[s][i]])
                {
                    q.push(adj[s][i]);
                    visited[adj[s][i]]=true;
                }
            }
        }
    }

static void BFS(int origin)
    {
        
        boolean visited[] = new boolean[1001];
        for(int i=0;i<1001;i++)
        visited[i]=false;
        
        
        LinkedList<Integer> q = new LinkedList<Integer>();
        visited[origin]=true;
        q.add(origin);
        while (q.size() != 0)
        
        {
            origin = q.poll();
            System.out.print(origin+" ");
            Iterator<Integer> i = obj.adj[origin].iterator();
            while (i.hasNext())
            {
                int n = i.next();
                if (!visited[n])
                {
                    visited[n] = true;
                    q.add(n);
                }
            }
        }
    }

#Back-end complete function Template for Python 3

def bfs(graph,origin):
    visited = {}
    que = queue.Queue()
    for v in graph:
        visited[v] = False
    que.put(origin)
    visited[origin] = True
    while(que.empty() == False):
        s = que.get();
        print(s,end = " ")
        for i in graph[s]:
            if(visited[i] == False):
                que.put(i)
                visited[i] = True

Happy Learning – If you require any further information, feel free to contact me.