#include<bits/stdc++.h>
#define MX 1000000
#define ll long long
#define ull unsigned long long
using namespace std;
bool visited[10000]; //1. For monitoring already visited or not
vector<int>adj[1000]; //2. Define a 2D matrix to store the graph
void bfs(int startNode)
{
queue<int>q; //3. Defining a queue
q.push(startNode); //4. push the starting node to the queue
visited[startNode] = 1; //5. make visited or starting node
cout<< "Output: "<< startNode <<" ";
while(!q.empty()){ // 6. do loop while queue is not empty
// 7. Take the first element of the queue and remove it from queue
// then do loop for all child or front element
int u = q.front();
q.pop();
for(int i=0; i<adj[u].size(); i++){
int v = adj[u][i];
if(!visited[v]){ // if the element is not visited
visited[v] = 1; // 8. set the status as visited
q.push(v); // 9. also push the element(child) into the queue
cout<< v <<" ";
}
}
}
cout<<endl;
}
int main()
{
int node, edge, vertex1, vertex2;
cin>>node>>edge; // Input node and vertex
for(int i = 0; i < edge; i++){
cin>> vertex1 >> vertex2;
// take input as Bidirectional graph
adj[vertex1].push_back(vertex2);
adj[vertex2].push_back(vertex1);
}
bfs(0);
return 0;
}
// Test case:
/*
5 6
1 2
1 3
0 2
0 3
0 4
3 4
Output: 0 2 3 4 1
*/
No comments