forked from reachanihere/Data-Structures-and-Algorithms
/
BFS.cpp
82 lines (64 loc) · 1.47 KB
/
BFS.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
Given an undirected and connected graph G(V, E), print its BFS traversal.
Here you need to consider that you need to print BFS path starting from vertex 0 only.
V is the number of vertices present in graph G and vertices are numbered from 0 to V-1.
E is the number of edges present in graph G.
Input Format :
Line 1: Two Integers V and E (separated by space)
Next 'E' lines, each have two space-separated integers, 'a' and 'b', denoting that there exists an edge between Vertex 'a' and Vertex 'b'.
Output Format :
BFS Traversal (separated by space)
Constraints :
2 <= V <= 1000
1 <= E <= 1000
Sample Input 1:
4 4
0 1
0 3
1 2
2 3
Sample Output 1:
0 1 3 2
*/
#include <iostream>
#include <queue>
using namespace std;
void bfs(int **edges,int n,int start,bool *visited){
queue<int> q;
q.push(start);
visited[start]=true;
while(!q.empty()){
int node=q.front();
q.pop();
cout<<node<<" ";
for(int i=0;i<n;i++){
if(edges[node][i] && !visited[i]){
q.push(i);
visited[i]=true;
}
}
}
cout<<endl;
}
int main() {
int V, E;
cin >> V >> E;
int **edges=new int*[V];
//intialization
for(int i=0;i<V;i++){
edges[i]=new int[V];
for(int j=0;j<V;j++)
edges[i][j]=0;
}
for(int i=0;i<E;i++){
int a,b;
cin>>a>>b;
edges[a][b]=1;
edges[b][a]=1;
}
bool* visited=new bool[V];
for(int i=0;i<V;i++)
visited[i]=false;
bfs(edges,V,0,visited);
return 0;
}