# Breadth First Search in C++ – Algorithm and Source Code

**Basic Theory**

Breadth-first searches are performed by exploring all nodes at a given depth before proceeding to the next level. This means that all immediate children of nodes are explored before any of the children’s children are considered. It has obvious advantage of always finding a minimal path length solution when one exists. However, a great many nodes may need to be explored before a solution is found, especially if the tree is very full.

**Algorithm**

BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search. The BFS algorithm proceeds as follows.

- Place the starting node
*s*on the queue. - If the queue is empty, return failure and stop.
- If the first element on the queue is a goal node
*g*, return success and stop Otherwise, - Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
- Return to step 2.

**Example**

Consider a graph

Applying above algorithm, the BFS of the graph starting from node 1 is : 1, 2, 3, 4, 6, 7, 5

**Source Code**

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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 | /**************************************************************** BFS.cpp Written by Bibek Subedi ****************************************************************/ #include <iostream> #include <ctime> using namespace std; /**************************************************************** Performs the Breadth-First Graph search for both directed and undirected graphs. This algorithm explores all the findable nodes in "layers". @author Bibek Subedi *****************************************************************/ /**************************************************************** Class Queue represent a Queue data structure which is First In First Out [FIFO] structured. It has operations like Enqueue which adds an element at the rear side and Dequeue which removes the element from front. *****************************************************************/ struct node { int info; node *next; }; class Queue { private: node *front; node *rear; public: Queue(); ~Queue(); bool isEmpty(); void enqueue(int); int dequeue(); void display(); }; void Queue::display(){ node *p = new node; p = front; if(front == NULL){ cout<<"\nNothing to Display\n"; }else{ while(p!=NULL){ cout<<endl<<p->info; p = p->next; } } } Queue::Queue() { front = NULL; rear = NULL; } Queue::~Queue() { delete front; } void Queue::enqueue(int data) { node *temp = new node(); temp->info = data; temp->next = NULL; if(front == NULL){ front = temp; }else{ rear->next = temp; } rear = temp; } int Queue::dequeue() { node *temp = new node(); int value; if(front == NULL){ cout<<"\nQueue is Emtpty\n"; }else{ temp = front; value = temp->info; front = front->next; delete temp; } return value; } bool Queue::isEmpty() { return (front == NULL); } /************************************************************ Class Graph represents a Graph [V,E] having vertices V and edges E. ************************************************************/ class Graph { private: int n; /// n is the number of vertices in the graph int **A; /// A stores the edges between two vertices public: Graph(int size = 2); ~Graph(); bool isConnected(int, int); void addEdge(int u, int v); void BFS(int ); }; Graph::Graph(int size) { int i, j; if (size < 2) n = 2; else n = size; A = new int*[n]; for (i = 0; i < n; ++i) A[i] = new int[n]; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) A[i][j] = 0; } Graph::~Graph() { for (int i = 0; i < n; ++i) delete [] A[i]; delete [] A; } /****************************************************** Checks if two given vertices are connected by an edge @param u vertex @param v vertex @return true if connected false if not connected ******************************************************/ bool Graph::isConnected(int u, int v) { return (A[u-1][v-1] == 1); } /***************************************************** adds an edge E to the graph G. @param u vertex @param v vertex *****************************************************/ void Graph::addEdge(int u, int v) { A[u-1][v-1] = A[v-1][u-1] = 1; } /***************************************************** performs Breadth First Search @param s initial vertex *****************************************************/ void Graph::BFS(int s) { Queue Q; /** Keeps track of explored vertices */ bool *explored = new bool[n+1]; /** Initailized all vertices as unexplored */ for (int i = 1; i <= n; ++i) explored[i] = false; /** Push initial vertex to the queue */ Q.enqueue(s); explored[s] = true; /** mark it as explored */ cout << "Breadth first Search starting from vertex "; cout << s << " : " << endl; /** Unless the queue is empty */ while (!Q.isEmpty()) { /** Pop the vertex from the queue */ int v = Q.dequeue(); /** display the explored vertices */ cout << v << " "; /** From the explored vertex v try to explore all the connected vertices */ for (int w = 1; w <= n; ++w) /** Explores the vertex w if it is connected to v and and if it is unexplored */ if (isConnected(v, w) && !explored[w]) { /** adds the vertex w to the queue */ Q.enqueue(w); /** marks the vertex w as visited */ explored[w] = true; } } cout << endl; delete [] explored; } int main() { /** Creates a graph with 12 vertices */ Graph g(12); /** Adds edges to the graph */ g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(3, 4); g.addEdge(3, 6); g.addEdge(4 ,7); g.addEdge(5, 6); g.addEdge(5, 7); clock_t t1; t1 = clock(); /** Explores all vertices findable from vertex 1 */ g.BFS(1); float diff = (double)(clock() - t1)/CLOCKS_PER_SEC ; cout <<endl<< "The time taken for Breadth first search: "<< diff << endl; } |

**Complexity**

The time complexity of the breadth-first search is O(

*b*). This can be seen by noting that all nodes up to the goal depth d are generated. Therefore, the number generated is^{d}*b + b*which is O(^{2}+ . . . + b^{d}*b*). The space complexity is also O(^{d}*b*) since all nodes at a given depth must be stored in order to generate the nodes at the next depth, that is,^{d}*b*nodes must be stored at depth^{d-1}*d – 1*to generate nodes at depth*d*, which gives space complexity of O(*b*).^{d}
This post seem very yummy!!! I love chocolate!

Technology, Free Software and Best Tutorial

your blog is good! I'll visit again 🙂

God Bless You

In your BFS function, I think you have to remove the 'continue' in the if-statement. Otherwise it's not doing the right thing. Just use for example g.BFS(1, 3); and you will see that the output after the 3rd value is different.

In your bfs program remove that time thing from the void main part..

main function should return an integer value … 🙂

Of course, but my compiler does it for me 🙂 … any way thank you for pointing.

what does this algorithm do exactly?

Got a small memory leak in dequeue. You are leaking temp when you assign front to it.

according to the c++ standard, it is not necessary have a return statement in main()

I think there are memory leak in the queue destructor

Why did you implement your own queue anyway, when there's std::queue?

use of std:queue is recommended.

I sense a memory leak .. no need to allocate memory for the temp variables.

When does the display() function ever get called?

post Output of the program i.e screenshot of ouput

line 156 is added because of the graph is undirected, sure?

Thank a lot.

The style you code is neat and perspicuous.

It helps me.

Yes, also it Depend on – if u r using diff Ide such as Code::Blocks

node *p = new node;

no need of making new node , we just need pointer;

just write :node *p

And thank u for code