Breadth First Search (BFS)


Breadth First Search is one of the most simple graph algorithms. It traverses the graph by first checking the current node and then expanding it by adding its successors to the next level. The process is repeated for all nodes in the current level before moving to the next level. If the solution is found the search stops.

Visualisation

Evaluation

Space Complexity: O(n)

Worse Case Time Complexity: O(n)

Breadth First Search is complete on a finite set of nodes and optimal if the cost of moving from one node to another is constant.

Application

  1. To find all connected components in a given graph
  2. To find the shortest path between two nodes of any weighted or unweighted graph
  3. To find all nodes within an individual connected components

C++ code for BFS implementation

// Program to print BFS traversal from a given // source vertex. BFS(int s) traverses vertices // reachable from s. #include<iostream> #include <list> using namespace std; // This class represents a directed graph using // adjacency list representation class Graph { int V; // No. of vertices // Pointer to an array containing adjacency // lists list<int> *adj; public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int v, int w); // prints BFS traversal from a given source s void BFS(int s); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } void Graph::BFS(int s) { // Mark all the vertices as not visited bool *visited = new bool[V]; for(int i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS list<int> queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // 'i' will be used to get all adjacent // vertices of a vertex list<int>::iterator i; while(!queue.empty()) { // Dequeue a vertex from queue and print it s = queue.front(); cout << s << " "; queue.pop_front(); // Get all adjacent vertices of the dequeued // vertex s. If a adjacent has not been visited, // then mark it visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "Following is Breadth First Traversal " << "(starting from vertex 2) n"; g.BFS(2); return 0; }

Implementation of BFS in Java

import java.util.*; public class BFS { /* The method takes an adjacency matrix where 1 denotes an edge between i and j. * n - number of nodes in the graph. * m - number of edges in the graph. */ void Map<Integer, List<Integer>> createAdjList(int[][] edges, int n, int m) { Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>>(); for (int i = 1; i <= n; i++) { adjList.put(i, new LinkedList<Integer>()); } for (int i = 0; i < m; i++) { List<Integer> ls = adjList.get(edges[i][0]); ls.add(edges[i][1]); ls = adjList.get(edges[i][1]); ls.add(edges[i][0]); } return adjList; } /* s - starting node for bfs. * edges - edge array which stores the edges. * n - number of nodes in the graph. * m - number of edges in the graph. */ void bfs(int n, int m, int[][] edges, int s) { // Create an adjacency list from the adjacency matrix edges. Map<Integer, List<Integer>> adjList = createAdjList(edges, n, m); boolean visited[] = new boolean[n+1]; Queue<Integer> q = new LinkedList<Integer>(); q.add(s); visited[s] = true; System.out.println("BFS traversal of the graph"); while (!q.isEmpty()) { int currNode = q.remove(); Iterator<Integer> it = adjList.get(currNode).iterator(); System.out.println(currNode + "->"); while (it.hasNext()) { int neighbor = (Integer)it.next(); if (visited[neighbor] == false) { visited[neighbor] = true; q.add(neighbor); } } } } }

More Information:

Graphs

Depth First Search (DFS)

This article needs improvement. You can help improve this article. You can also write similar articles and help the community.