BFS
Breadth-first search is a graph traversal algorithm that travels the graph from a root location and scans all the neighboring nodes. Then, select a nearby location and scan all unchecked nodes. When using BFS, any node in the graph can be considered as the root node.
There are many ways to traverse a graph, but among them, BFS is the most widely used method. It is a recursive algorithm to search all the vertices of a tree or structure of graph data. BFS puts the whole vertex of the graph into two categories - visited and unvisited. It selects one node in the graph and, after that, visits all nodes near the selected location.
Complexity of BFS algorithm
The complexity of BFS depends on the data structure used to represent the graph. The time complexity of the BFS algorithm is O(V + E), as in the worst case scenario, the BFS algorithm scans the entire node and edge. In the graph, the number of vertices is O(V), while the number of edges is O(E).
The BFS space complexity is O(V), where V is the number of vertices.
Applications of BFS algorithm
The applications of breadth-first-algorithm:-
Breadth-first-algorithm applications are provided as follows:
- BFS can be used to locate neighborhoods in a specific source.
- In a peer-to-peer network, the BFS algorithm can be used as a shortcut to locate all the neighboring nodes. Many torrent customers, such as BitTorrent, Torrent, etc. use this process to find "seeds" and "peers" in the network.
- BFS can be used by web searchers to create web page references. It is one of the main algorithms that can be used to target web pages. It starts cutting from the source page and then follows the links related to the page. Here, all web pages are considered as nodes in the graph.
- BFS is used to determine the shortest path and the minimum spanning tree.
- BFS is also used in Cheney's techniques to replicate garbage collection.
- It can be used in the ford-Fulkerson method to calculate the maximum flow in a flow network.
Implementation of BFS using C++
<![CDATA[ #include<bits/stdc++>
using namespace std;
// a directed graph class
class DiGraph
{
int V; // No. of vertices
// Pointer to an array containing adjacency lists
list<int> *adjList;
public:
DiGraph(int V); // Constructor
// add an edge from vertex v to w
void addEdge(int v, int w);
// BFS traversal sequence starting with s ->starting node
void BFS(int s);
};
DiGraph::DiGraph(int V)
{
this->V = V;
adjList = new list<int>[V];
}
void DiGraph::addEdge(int v, int w)
{
adjList[v].push_back(w); // Add w to v’s list.
}
void DiGraph::BFS(int s)
{
// initially none of the vertices is visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// queue to hold BFS traversal sequence
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// iterator 'i' to get all adjacent vertices
list<int>::iterator i;
while(!queue.empty())
{
// dequeue the vertex
s = queue.front();
cout << s << " ";
queue.pop_front();
// get all adjacent vertices of popped vertex and process each if not already visited
for (i = adjList[s].begin(); i != adjList[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
int main()
{
// create a graph
DiGraph dg(5);
dg.addEdge(0, 1);
dg.addEdge(0, 2);
dg.addEdge(0, 3);
dg.addEdge(1, 2);
dg.addEdge(2, 4);
dg.addEdge(3, 3);
dg.addEdge(4, 4);
cout << "Breadth First Traversal for given graph (with 0 as starting node): "<<endl;
dg.BFS(0);
return 0;
}
]]>
output:
<![CDATA[
Breadth-First Traversal for the given graph (with 0 as starting node):
0 1 2 3 4
]]>
