fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void BFS(vector<vector<int>>& graph,int start,vector<bool>& visited,queue<int>&q,vector<int>& distance ){
  5.     visited[start]=true;
  6.     q.push(start);
  7.     distance[start]=0;
  8.     cout<<q.front()<<"--"<<distance[start]<<endl;
  9.     int curr=start;
  10.  
  11.     while(!q.empty()){
  12.  
  13.         for(int i=0;i<graph.size();i++){
  14.             if(graph[curr][i]==1 &&visited[i]==false){
  15.                 q.push(i);
  16.                 distance[i]=distance[curr]+1;
  17.                 visited[i]=true;
  18.                 cout<<q.back()<<"--"<<distance[i]<<endl;
  19.                 }
  20.         }
  21.         q.pop();
  22.         curr=q.front();
  23.     }
  24. }
  25.  
  26. int main(){
  27.  
  28.     int n;
  29. 	cout << "Enter the number of nodes: " << endl;
  30. 	cin >> n;
  31. 	// defining the adjacency matrix
  32.  
  33. 	vector<vector<int>> graph (n,vector<int>(n,0));
  34.  
  35. 	// creating the adjacency matrix
  36. 	for(int i=0; i<n; i++){
  37. 		for(int j=0; j<n; j++)
  38. 			cin >> graph[i][j];
  39. 	}
  40.  
  41. 	vector<bool> visited(n,false);
  42. 	vector<int> distance(n);
  43. 	queue<int> q;
  44. 	cout<<"BFS traversal with distance: "<<endl;
  45. 	BFS(graph,0,visited,q,distance);
  46.  
  47.  
  48. return 0;
  49. }
  50.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
8
0 0 0 1 0 0 0 1
0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 1 0 0 0 1 0 1
0 0 0 0 1 1 0 0
stdout
copy 
Enter the number of nodes: 
BFS traversal with distance: 
0--0
3--1
7--1
4--2
5--2
https://ideone.com/1IEIAs
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!