fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Number of vertices in the graph
  5. #define N 13
  6.  
  7. // data structure to store graph edges
  8. struct Edge {
  9. 	int src, dest;
  10. };
  11.  
  12. // class to represent a graph object
  13. class Graph
  14. {
  15. public:
  16. 	// A array of vectors to represent adjacency list
  17. 	vector<int> adjList[N];
  18.  
  19. 	// Constructor
  20. 	Graph(vector<Edge> edges)
  21. 	{
  22. 		// add edges to the undirected graph
  23. 		for (unsigned i = 0; i < edges.size(); i++)
  24. 		{
  25. 			int src = edges[i].src;
  26. 			int dest = edges[i].dest;
  27.  
  28. 			adjList[src].push_back(dest);
  29. 			adjList[dest].push_back(src);
  30. 		}
  31. 	}
  32. };
  33.  
  34. // Perform BFS recursively on graph
  35. void recursiveBFS(Graph const &graph, queue<int> &q, 
  36. 					vector<bool> &discovered)
  37. {
  38. 	if (q.empty())
  39. 		return;
  40.  
  41. 	// pop front node from queue and print it
  42. 	int v = q.front();
  43. 	q.pop();
  44. 	cout << v << " ";
  45.  
  46. 	// do for every edge (v -> u)
  47. 	for (int u : graph.adjList[v])
  48. 	{
  49. 		if (!discovered[u])
  50. 		{
  51. 			// mark it discovered and push it into queue
  52. 			discovered[u] = true;
  53. 			q.push(u);
  54. 		}
  55. 	}
  56.  
  57. 	recursiveBFS(graph, q, discovered);
  58. }
  59.  
  60. // main function
  61. int main()
  62. {
  63. 	// vector of graph edges as per above diagram
  64. 	vector<Edge> edges = { 
  65. 		{2, 5}, {2, 6}, {5, 9}, 
  66. 		{5, 10}, {4, 7}, {4, 8}, {7, 11}, {7, 12}
  67. 	};
  68.  
  69. 	// create a graph from edges
  70. 	Graph graph(edges);
  71.  
  72. 	// stores vertex is discovered or not
  73. 	vector<bool> discovered(N);
  74.  
  75. 	// create a queue used to do BFS
  76. 	queue<int> q;
  77.  
  78. 	// mark source vertex as discovered
  79. 	discovered[1] = true;
  80. 	// push source vertex into the queue
  81. 	q.push(1);
  82.  
  83. 	// start BFS traversal from vertex i
  84. 	recursiveBFS(graph, q, discovered);
  85.  
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/6i4gd7
Breadth First Search (BFS) | Recursive Implementation
language:
C++14 (gcc 8.3)
created:
6 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!