Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
breadth_first_search.cpp File Reference

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

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

Namespaces

 graph
 Graph algorithms.
 

Functions

void graph::add_directed_edge (std::vector< std::vector< int >> *graph, int u, int v)
 Adds a directed edge from vertex u to vertex v. More...
 
void graph::add_undirected_edge (std::vector< std::vector< int >> *graph, int u, int v)
 Adds an undirected edge from vertex u to vertex v. Essentially adds too directed edges to the adjacency list reprsentation of the graph. More...
 
std::vector< bool > graph::breadth_first_search (const std::vector< std::vector< int >> &graph, int start)
 Function performs the breadth first search algorithm over the graph. More...
 
void tests ()
 
int main ()
 

Detailed Description

Breadth First Search Algorithm (Breadth First Search)

Author
Ayaan Khan

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

Function Documentation

◆ main()

int main ( void  )

Main function

162  {
163  tests();
164 
165  size_t vertices = 0, edges = 0;
166  std::cout << "Enter the number of vertices: ";
167  std::cin >> vertices;
168  std::cout << "Enter the number of edges: ";
169  std::cin >> edges;
170 
172 
173  std::cout << "Enter space-separated pairs of vertices that form edges: "
174  << std::endl;
175  while (edges--) {
176  int u = 0, v = 0;
177  std::cin >> u >> v;
178  // Decrement the vertex index so that we can read more convenint
179  // 1-based indexing from the user input.
180  graph::add_directed_edge(&graph, u - 1, v - 1);
181  }
182 
184  return 0;
185 }
Here is the call graph for this function:

◆ tests()

void tests ( )

Test 1 Begin

Test 2 Begin

Test 3 Begins

122  {
123  /// Test 1 Begin
128 
130  std::vector<bool> correct_result = {true, true, true, true};
131 
132  assert(std::equal(correct_result.begin(), correct_result.end(),
133  returned_result.begin()));
134  std::cout << "Test 1 Passed..." << std::endl;
135 
136  /// Test 2 Begin
137  returned_result = graph::breadth_first_search(graph, 0);
138 
139  assert(std::equal(correct_result.begin(), correct_result.end(),
140  returned_result.begin()));
141  std::cout << "Test 2 Passed..." << std::endl;
142 
143  /// Test 3 Begins
144  graph.clear();
145  graph.resize(6);
152 
153  returned_result = graph::breadth_first_search(graph, 2);
154  correct_result = {false, false, true, true, false, true};
155 
156  assert(std::equal(correct_result.begin(), correct_result.end(),
157  returned_result.begin()));
158  std::cout << "Test 3 Passed..." << std::endl;
159 }
Here is the call graph for this function:
graph::breadth_first_search
std::vector< bool > breadth_first_search(const std::vector< std::vector< int >> &graph, int start)
Function performs the breadth first search algorithm over the graph.
Definition: breadth_first_search.cpp:96
std::equal
T equal(T... args)
std::vector
STL class.
graph::add_directed_edge
void add_directed_edge(std::vector< std::vector< int >> *graph, int u, int v)
Adds a directed edge from vertex u to vertex v.
Definition: breadth_first_search.cpp:66
std::cout
graph::add_undirected_edge
void add_undirected_edge(std::vector< std::vector< int >> *graph, int u, int v)
Adds an undirected edge from vertex u to vertex v. Essentially adds too directed edges to the adjacen...
Definition: breadth_first_search.cpp:81
tests
void tests()
Definition: breadth_first_search.cpp:122
std::endl
T endl(T... args)
std::vector::begin
T begin(T... args)
graph
Graph algorithms.
std::vector::end
T end(T... args)
std::cin