fork download
copy 
  1. /*
  2.  *  Author  : Adrian Statescu <http://t...content-available-to-author-only...p.ro> , <mergesortv@gmail.com>
  3.  *  License : MIT
  4.  */
  5. #include <iostream>
  6. #include <fstream>
  7. #include <vector>
  8. #include <list>
  9. #define FIN "bfs.in"
  10. #define FOUT "bfs.out"
  11.  
  12. using namespace std;
  13.  
  14. typedef unsigned long ulong;
  15.  
  16. #define NDEBUG
  17.  
  18. class Breadth_First_Search {
  19.  
  20.       //constructor of the class
  21. 	  public:
  22.  
  23. 	  	    Breadth_First_Search(vector<vector<ulong>* >& adjcencyList, ulong nVertices, ulong source) :
  24. 	  	                         adjList(adjcencyList), nodes(nVertices), source(source)
  25.  
  26. 	  	         {
  27.  
  28.                                  costs.resize(nodes + 1, -1);
  29. 	  	         }
  30.  
  31. 	  public: 
  32. 	  	   void execute() {
  33.  
  34.                 costs[ source ] = 0;
  35.  
  36. 	  	   	    bfs(source);  
  37.  
  38. 	       }	
  39.  
  40. 	       void bfs(ulong node) {
  41.  
  42.  
  43.                 list<ulong> queue;
  44.  
  45.                 queue.push_back(node);
  46.  
  47.                 while( !queue.empty() ) {
  48.  
  49.                 	  ulong curr = queue.front();
  50.  
  51.                 	  queue.pop_front();
  52.  
  53.                 	  vector<ulong> *neighbours = adjList[curr];
  54.  
  55.                 	  if(!neighbours) continue;
  56.  
  57.                 	  for(int i = 0; i < neighbours->size(); ++i) {
  58.  
  59.                 	  	      ulong vertex = (*neighbours)[i];
  60.  
  61.                 	  	      if(costs[vertex] == -1) {
  62.  
  63.                 	  	      	costs[vertex] = costs[curr] + 1;
  64.  
  65.                 	  	      	queue.push_back(vertex);
  66.                 	  	      }
  67.  
  68.                 	  }       
  69.  
  70.                 }              
  71. 	       }
  72.  
  73. 	       const vector<long>& getCosts() {
  74.  
  75.                  return costs; 
  76. 	       }
  77.  
  78.       private:
  79.             vector<vector<ulong>* >& adjList;
  80.             ulong nodes;
  81.             ulong source;
  82.             vector<long> costs;
  83.  
  84. };
  85.  
  86. int main(int argc, char const *argv[])
  87. {
  88.  
  89. 	const char *inFile = "bfs.in";
  90. 	const char *outFile = "bfs.out";
  91.  
  92. 	ulong nodes, edges, source;
  93.  
  94. 	ifstream fin(inFile);
  95. 	ofstream fout(outFile);
  96.  
  97.  
  98.     #ifndef NDEBUG 
  99.  
  100. 	if(!fin || !fout) {
  101.  
  102. 		cerr<<"Error opening one of \""<<inFile<<"\" or \""<<outFile<<"\""<<endl;;
  103. 	}
  104.  
  105. 	#endif
  106.  
  107. 	cin>>nodes>>edges>>source;
  108.  
  109. 	vector<vector<ulong>* > adjList;
  110.  
  111. 	adjList.resize(nodes+1, NULL);
  112.  
  113. 	ulong x, y;
  114.  
  115. 	for(ulong i = 0; i < edges; ++i) {
  116.  
  117.         cin>>x>>y;
  118.  
  119.         if(adjList[x] == NULL) {
  120.  
  121.         	adjList[x] = new vector<ulong>;
  122.  
  123.         }
  124.  
  125.         adjList[x]->push_back(y);
  126. 	}
  127.  
  128.  
  129.     Breadth_First_Search bfs(adjList, nodes, source);
  130.  
  131.                          bfs.execute();  
  132.  
  133.     const vector<long>& costs = bfs.getCosts();                          
  134.  
  135.     for(vector<long>::const_iterator it = costs.begin()  + 1; it != costs.end(); ++it) 
  136.  
  137.     cout<<*it<<" ";      
  138.  
  139.     //clean up
  140.  
  141.     for(ulong i = 0; i < adjList.size(); ++i) {
  142.  
  143.     	if(adjList[i] != NULL) delete adjList[i];	
  144.     }      
  145.  
  146. 	return 0;
  147. }
  148.  
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
8 12 7
2 2
5 5
6 6
8 3
5 4
2 5
4 2
7 2
1 6
5 3
6 7
3 3
stdout
copy 
-1 1 3 3 2 -1 0 -1
https://ideone.com/53Famm
Breadth First Search Traversal with given Adj List using class stl vector and list
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!