{"id":83364,"date":"2021-08-04T09:00:38","date_gmt":"2021-08-04T03:30:38","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=83364"},"modified":"2021-08-04T09:00:38","modified_gmt":"2021-08-04T03:30:38","slug":"breadth-first-search","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/","title":{"rendered":"Breadth First Search in Data Structure"},"content":{"rendered":"

Traversal means to visit each node of a graph. For graphs, there are two types of traversals: Depth First traversal and Breadth-First traversal. In this article, we are going to study Breadth-first traversal or BFS in detail.<\/p>\n

What is Breadth First Search?<\/h3>\n

Breadth First Search is a traversal technique in which we traverse all the nodes of the graph in a breadth-wise motion. In BFS, we traverse one level at a time and then jump to the next level.<\/p>\n

In a graph, the traversal can start from any node and cover all the nodes level-wise. The BFS algorithm makes use of the queue data structure for implementation. In BFS, we always reach the final goal state (which was not always the case for DFS).<\/p>\n

Algorithm for BFS:<\/h3>\n

Step 1: Choose any one node randomly, to start traversing.
\nStep 2: Visit its adjacent unvisited node.
\nStep 3: Mark it as visited in the boolean array and display it.
\nStep 4: Insert the visited node into the queue.
\nStep 5: If there is no adjacent node, remove the first node from the queue.
\nStep 6: Repeat the above steps until the queue is empty.<\/p>\n

Working of Breadth First Search:<\/h3>\n

Consider the following graph having 8 nodes named as A, B, C, D, E, F, G and H as shown:<\/p>\n

\"Graph<\/a><\/p>\n

Initially, the queue will be empty.
\nLet us start traversing the graph from node A. Once we visit node A, we mark it as visited and also place it inside the queue as shown:<\/p>\n

\"BFS<\/a><\/p>\n

The next step is to traverse its adjacent nodes i.e. B and C and place them inside the queue. When we place the adjacent node of A in the queue, we will remove A from the queue and display it in the output array as shown:<\/p>\n

\"Breadth<\/a><\/p>\n

Next, we don\u2019t have any more adjacent nodes for A. therefore, we will remove node B from the queue and place its adjacent nodes into the queue. Similarly, we will traverse the nodes of C and put them into the queue.<\/p>\n

\"BFS<\/a><\/p>\n

The next adjacent node is node H. thus, we will traverse that as well and place it in the queue. Once all the nodes have entered the queue, we will start removing them from the queue and putting them into the output array.<\/p>\n

\"Breadth<\/a><\/p>\n

Thus, slowly the queue starts decreasing in size and the output array will be full as shown:<\/p>\n

\"Working<\/a><\/p>\n

\"Working<\/a><\/p>\n

In this way, we will get the output of BFS to be A\u2192B\u2192C\u2192D\u2192E\u2192F\u2192G\u2192H.<\/p>\n

Pseudo-code for BFS:<\/h3>\n
procedure BFS(Graph, root) is\n    Let root = explored\n    Queue.enqueue(root)\n    while(Queue is not empty):\n        v := Queue.dequeue()\n        if v == goal:\n           return v\n        for all edges from v to w in Graph.adjacentEdges(v):\n            if w is not labeled as explored:\n                label w as explored\n            Queue.enqueue(w)\n        END for\n    END while\nEND BFS\n<\/pre>\n
Implementation of BFS in C:<\/h3>\n
#include <stdio.h>\n#include <stdio.h>\n#include <stdlib.h>\n#include <stdbool.h>\n#define MAX 5\n\nstruct Node{\n   char label;\n   bool visited;\n};\n\nint Queue[MAX];\nint Rear = -1;\nint Front = 0;\nint queue_item_count = 0;\nstruct Node* lst_Nodes[MAX];\nint adj_matrix[MAX][MAX];\nint node_count = 0;\n\nvoid insert(int data) {\n   Queue[++Rear] = data;\n   queue_item_count++;\n}\n\nint remove_data() {\n   queue_item_count--;\n   return Queue[Front++]; \n}\n\nbool isQueueEmpty() {\n   return queue_item_count == 0;\n}\n\nvoid addNode(char label) {\n   struct Node* node = (struct Node*) malloc(sizeof(struct Node));\n   node->label = label;  \n   node->visited = false;     \n   lst_Nodes[node_count++] = node;\n}\n\nvoid addEdge(int start,int end) {\n   adj_matrix[start][end] = 1;\n   adj_matrix[end][start] = 1;\n}\n\nvoid display_node(int node_index) {\n   printf(\"%c \",lst_Nodes[node_index] -> label);\n}       \n\nint get_adj_unvisited_node(int node_index) {\n   int i;\n   for(i = 0; i<node_count; i++) {\n      if(adj_matrix[node_index][i] == 1 && lst_Nodes[i]->visited == false)\n         return i;\n   }\n   return -1;\n}\n\nvoid BFS() {\n   int i;\n   lst_Nodes[0]->visited = true;\n   display_node(0);   \n   insert(0);\n   int unvisited_node;\n   while(!isQueueEmpty()) {\n      int temp_node = remove_data();   \n      while((unvisited_node = get_adj_unvisited_node(temp_node)) != -1) {    \n         lst_Nodes[unvisited_node]->visited = true;\n         display_node(unvisited_node);\n         insert(unvisited_node);               \n        }\n   }   \n        \n    for(i = 0; i<node_count; i++) {\n      lst_Nodes[i]->visited = false;\n   }    \n}\n\nint main() {\n    int i, j;\n    for(i = 0; i<MAX; i++) {\n      for(j = 0; j<MAX; j++) \n         adj_matrix[i][j] = 0;\n   }\n\n   addVertex('A');   \n   addVertex('B');   \n   addVertex('C');   \n   addVertex('D');   \n   addVertex('E');   \n \n   addEdge(0, 1);    \n   addEdge(0, 2);    \n   addEdge(0, 3);    \n   addEdge(1, 4);    \n   addEdge(2, 4);    \n   addEdge(3, 4);    \n  \n   printf(\"\\nBreadth First Search: \");\n   BFS();\n   return 0;\n}\n<\/pre>\n
BFS Implementation in C++<\/h3>\n
#include<bits\/stdc++.h>\nusing namespace std;\nclass Graph\n{\n  int V; \n  list<int> *adj;\npublic:\n  Graph(int V); \n  void addEdge(int v, int w);\n  void BFS(int s);\n};\n\nGraph::Graph(int V)\n{\n  this->V = V;\n  adjacent = new list<int>[V];\n}\n\nvoid Graph::addEdge(int v, int w)\n{\n  adjacent[v].push_back(w); \n}\n\nvoid Graph::BFS(int s)\n{\n  bool *visited = new bool[V];\n  for(int i = 0; i < V; i++)\n    visited[i] = false;\n  list<int> queue;\n  visited[s] = true;\n  queue.push_back(s);\n  list<int>::iterator i;\n\n  while(!queue.empty())\n  {\n    s = queue.front();\n    cout << s << \" \";\n    queue.pop_front();\n    for (i = adjacent[s].begin(); i != adjacent[s].end(); ++i)\n    {\n      if (!visited[*i])\n      {\n        visited[*i] = true;\n        queue.push_back(*i);\n      }\n    }\n  }\n}\n\nint main()\n{\n  Graph g(4);\n  g.addEdge(0, 2);\n  g.addEdge(0, 1);\n  g.addEdge(1, 3);\n  g.addEdge(2, 1);\n  g.addEdge(2, 3);\n  g.addEdge(3, 3);\n  cout << \"The Breadth First Traversal is: \\n\";\n  g.BFS(1);\n  return 0;\n}\n\n<\/pre>\n
Implementation of Breadth First Search in Java:<\/h3>\n
import java.io.*;\nimport java.util.*;\nclass Graph\n{\n  private int V; \n  private LinkedList<Integer> adjacent[]; \n  Graph(int v)\n  {\n    V = v;\n    adjacent = new LinkedList[v];\n    for (int i=0; i<v; ++i)\n      adjacent[i] = new LinkedList();\n  }\n  void addEdge(int v,int w)\n  {\n    adjacent[v].add(w);\n  }\n\n  void BFS(int s)\n  {\n    boolean visited[] = new boolean[V];\n    LinkedList<Integer> queue = new LinkedList<Integer>();\n    visited[s]=true;\n    queue.add(s);\n\n    while (queue.size() != 0)\n    {\n      s = queue.poll();\n      System.out.print(s+\" \");\n      Iterator<Integer> i = adj[s].listIterator();\n      while (i.hasNext())\n      {\n        int n = i.next();\n        if (!visited[n])\n        {\n          visited[n] = true;\n          queue.add(n);\n        }\n      }\n    }\n  }\n\n  public static void main(String args[])\n  {\n    Graph g = new Graph(4);\n    g.addEdge(0, 2);\n    g.addEdge(0, 1);\n    g.addEdge(1, 3);\n    g.addEdge(2, 1);\n    g.addEdge(2, 3);\n    g.addEdge(3, 3);\n    System.out.println(\"The Breadth First Traversal is: \");\n    g.BFS(1);\n  }\n}\n<\/pre>\n
Implementation of BFS in Python<\/h3>\n
class Graph:\n  def __init__(self):\n    self.graph = defaultdict(list)\n\n  def addEdge(self,u,v):\n    self.graph[u].append(v)\n\n  def BFS(self, s):\n    visited = [False] * (max(self.graph) + 1)\n    queue = []\n    queue.append(s)\n    visited[s] = True\n\n    while queue:\n      s = queue.pop(0)\n      print (s, end = \" \")\n      for i in self.graph[s]:\n        if visited[i] == False:\n          queue.append(i)\n          visited[i] = True\n\ng = Graph()\ng.addEdge(0, 2)\ng.addEdge(0, 1)\ng.addEdge(1, 3)\ng.addEdge(2, 1)\ng.addEdge(2, 3)\ng.addEdge(3, 3)\n\nprint (\"The Breadth First Traversal is: \")\ng.BFS(1)\n<\/pre>\n
Complexity of BFS<\/h3>\n
Time complexity:<\/strong> Since we are visiting all the nodes exactly once, therefore, the time complexity is O(V+E).<\/strong> Here, O(E) may vary between O(1) and O(V2). Thus, in the worst case, the time complexity of BFS is O(V2).<\/strong><\/p>\n
Space complexity:<\/strong> The space complexity of the BFS algorithm is O(V)<\/strong> where V denotes vertices\/nodes of the graph.<\/p>\n
Applications of Breadth First Search<\/h3>\n
    \n
  • To find the shortest path between two edges when the path length is equivalent to the number of edges.<\/li>\n
  • To check whether a graph is bipartite or not<\/li>\n
  • To copy garbage collection by Cheney\u2019s algorithm<\/li>\n
  • Used in unweighted graphs to find the minimum cost spanning tree<\/li>\n
  • To form peer-to-peer network connections<\/li>\n
  • To find neighboring locations in the GPS navigation system<\/li>\n
  • To detect cycle in an undirected graph<\/li>\n
  • To broadcast packets in a network<\/li>\n
  • To find all the nodes within one connected component in an otherwise disconnected graph<\/li>\n<\/ul>\n
    Conclusion<\/h3>\n
    In this article, we have gone through a graph traversal technique known as BFS. we have seen the working of BFS and its implementation in different programming languages like C, C++, Java and Python.<\/p>\n
    We have also seen some of the real-life applications of BFS which clearly shows that BFS is one of the most important algorithms of data structures.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Traversal means to visit each node of a graph. For graphs, there are two types of traversals: Depth First traversal and Breadth-First traversal. In this article, we are going to study Breadth-first traversal or...<\/p>\n","protected":false},"author":1,"featured_media":83397,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[3944,3945,3946,3947,3948,3949,3950],"class_list":["post-83364","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-bfs","tag-bfs-algorithm","tag-breadth-first-search","tag-breadth-first-search-pseudocode","tag-breadth-first-search-working","tag-complexity-of-bfs","tag-implementation-of-bfs"],"yoast_head":"\nBreadth First Search in Data Structure - TechVidvan<\/title>\n<meta name=\"description\" content=\"Learn the graph traversal technique known as Breadth First Search (BFS). Learn its working, algorithm, pseudocode and implementation.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Breadth First Search in Data Structure - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Learn the graph traversal technique known as Breadth First Search (BFS). Learn its working, algorithm, pseudocode and implementation.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-08-04T03:30:38+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Breadth-First-Search-in-DS.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"7 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Breadth First Search in Data Structure - TechVidvan","description":"Learn the graph traversal technique known as Breadth First Search (BFS). Learn its working, algorithm, pseudocode and implementation.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/","og_locale":"en_US","og_type":"article","og_title":"Breadth First Search in Data Structure - TechVidvan","og_description":"Learn the graph traversal technique known as Breadth First Search (BFS). Learn its working, algorithm, pseudocode and implementation.","og_url":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-08-04T03:30:38+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Breadth-First-Search-in-DS.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"7 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Breadth First Search in Data Structure","datePublished":"2021-08-04T03:30:38+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/"},"wordCount":662,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Breadth-First-Search-in-DS.jpg","keywords":["BFS","BFS Algorithm","Breadth First Search","Breadth First Search Pseudocode","Breadth First Search working","Complexity of BFS","Implementation of BFS"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/","url":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/","name":"Breadth First Search in Data Structure - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Breadth-First-Search-in-DS.jpg","datePublished":"2021-08-04T03:30:38+00:00","description":"Learn the graph traversal technique known as Breadth First Search (BFS). Learn its working, algorithm, pseudocode and implementation.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Breadth-First-Search-in-DS.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Breadth-First-Search-in-DS.jpg","width":1200,"height":628,"caption":"Breadth First Search"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/breadth-first-search\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Breadth First Search in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83364","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=83364"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83364\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/83397"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=83364"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=83364"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=83364"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}