Algorithms_in_C++
1.0.0
Set of algorithms implemented in C++.
|
Breadth First Search Algorithm (Breadth First Search) More...
#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <vector>
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 () |
Breadth First Search Algorithm (Breadth First Search)
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
And there are many more...
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.
int main | ( | void | ) |
Main function
void tests | ( | ) |
Test 1 Begin
Test 2 Begin
Test 3 Begins