TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
breadth_first_search.cpp File Reference

Breadth First Search Algorithm (Breadth First Search) More...

#include <algorithm>
#include <cassert>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <string>
Include dependency graph for breadth_first_search.cpp:

Go to the source code of this file.

Classes

class  graph::Graph< T >
 

Namespaces

namespace  graph
 Graph Algorithms.
 

Functions

static void tests ()
 
int main ()
 

Detailed Description

Breadth First Search Algorithm (Breadth First Search)

Author
Ayaan Khan
Aman Kumar Pandey

Breadth First Search also quoted as BFS is a Graph Traversal Algorithm. Time Complexity O(|V| + |E|) where V are the number of vertices and E are the number of edges in the graph.

Applications of Breadth First Search are

  1. Finding shortest path between two vertices say u and v, with path length measured by number of edges (an advantage over depth first search algorithm)
  2. Ford-Fulkerson Method for computing the maximum flow in a flow network.
  3. Testing bipartiteness of a graph.
  4. Cheney's Algorithm, Copying garbage collection.

And there are many more...

working

In the implementation below we first created a graph using the adjacency list representation of graph. Breadth First Search Works as follows it requires a vertex as a start vertex, Start vertex is that vertex from where you want to start traversing the graph. We maintain a bool array or a vector to keep track of the vertices which we have visited so that we do not traverse the visited vertices again and again and eventually fall into an infinite loop. Along with this boolen array we use a Queue.

  1. First we mark the start vertex as visited.
  2. Push this visited vertex in the Queue.
  3. while the queue is not empty we repeat the following steps
    1. Take out an element from the front of queue
    2. Explore the adjacency list of this vertex if element in the adjacency list is not visited then we push that element into the queue and mark this as visited

Definition in file breadth_first_search.cpp.

Function Documentation

◆ main()

int main ( void )

Main function

Definition at line 185 of file breadth_first_search.cpp.

185 {
186 tests();
187 size_t edges = 0;
188 std::cout << "Enter the number of edges: ";
189 std::cin >> edges;
190
192
193 std::cout << "Enter space-separated pairs of vertices that form edges: "
194 << std::endl;
195 while (edges--) {
196 int u = 0, v = 0;
197 std::cin >> u >> v;
198 g.add_edge(u, v);
199 }
200
201 g.breadth_first_search(0);
202 return 0;
203}
static void tests()
double g(double x)
Another test function.

◆ tests()

static void tests ( )
static

Test function

Test 1 Begin

Test 2 Begin

Test 3 Begins

Definition at line 138 of file breadth_first_search.cpp.

138 {
141 std::map<int, bool> correct_result;
142 g.add_edge(0, 1);
143 g.add_edge(1, 2);
144 g.add_edge(2, 3);
145 correct_result[0] = true;
146 correct_result[1] = true;
147 correct_result[2] = true;
148 correct_result[3] = true;
149
150 std::map<int, bool> returned_result = g.breadth_first_search(2);
151
152 assert(returned_result == correct_result);
153 std::cout << "Test 1 Passed..." << std::endl;
154
156 returned_result = g.breadth_first_search(0);
157
158 assert(returned_result == correct_result);
159 std::cout << "Test 2 Passed..." << std::endl;
160
163
164 g2.add_edge("Gorakhpur", "Lucknow", false);
165 g2.add_edge("Gorakhpur", "Kanpur", false);
166 g2.add_edge("Lucknow", "Agra", false);
167 g2.add_edge("Kanpur", "Agra", false);
168 g2.add_edge("Lucknow", "Prayagraj", false);
169 g2.add_edge("Agra", "Noida", false);
170
171 std::map<std::string, bool> correct_res;
172 std::map<std::string, bool> returned_res =
173 g2.breadth_first_search("Kanpur");
174 correct_res["Gorakhpur"] = false;
175 correct_res["Lucknow"] = false;
176 correct_res["Kanpur"] = true;
177 correct_res["Agra"] = true;
178 correct_res["Prayagraj"] = false;
179 correct_res["Noida"] = true;
180 assert(correct_res == returned_res);
181 std::cout << "Test 3 Passed..." << std::endl;
182}
std::map< T, bool > breadth_first_search(T src)
void add_edge(T u, T v, bool bidir=true)