Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- /*
- * This program reads a simple undireced graph from stdin and preforms
- * a BFS on the given graph. The format is as follows:
- * n m
- * e1 e2
- * ...
- *
- * The first line contains the number of vertices and edges of
- * the graph. The following m lines contain one edge each.
- * An edge is represented by two distinct integers between 0 and n-1,
- * being the two respective endpoints of the edge.
- *
- * */
- void bfs(vector<vector<int> > & g, vector<int> & order){
- int n = (int)g.size();
- vector<bool> seen(n,false);
- queue<int> q;
- seen[0] = true;
- q.push(0);
- while(!q.empty()){
- int x = q.front();
- order.push_back(x);
- q.pop();
- for(auto y : g[x]){
- if(!seen[y]){
- q.push(y);
- seen[y] = true;
- }
- }
- }
- }
- int main(){
- //setting up the graph
- int n,m;
- cin >> n >> m;
- vector<vector<int> > g(n,vector<int> ());
- vector<int> order;
- while(m--){
- int a,b;
- cin >> a >> b;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- //bfs call
- bfs(g,order);
- //printing the order
- cout << "One BFS order of the graph is:" << endl;
- for(auto x: order){
- cout << x << " ";
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement