• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

BFS (Breath First Search)

March 1, 2014 by Dhaval Dave

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.

Algorithm

The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as follows:

1) Enqueue the root node
2) Dequeue a node and examine it

  • If the element sought is found in this node, quit the search and return a result.
  • Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.

3)If the queue is empty, every node on the graph has been examined – quit the search and return “not found”. 4)If the queue is not empty, repeat from Step 2.

C program

#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
 for(i=1;i<=n;i++)
  if(a[v][i] && !visited[i])
   q[++r]=i;
 if(f<=r)
 {
  visited[q[f]]=1;
  bfs(q[f++]);
 }
}
void main()
{
 int v;
 clrscr();
 printf("n Enter the number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  q[i]=0;
  visited[i]=0;
 }
 printf("n Enter graph data in matrix form:n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
 printf("n Enter the starting vertex:");
 scanf("%d",&v);
 bfs(v);
 printf("n The node which are reachable are:n");
 for(i=1;i<=n;i++)
  if(visited[i])
   printf("%dt",i);
  else
   printf("n Bfs is not possible");
 getch();
}

Similar Articles

Filed Under: problem Tagged With: Binary Tree, Graph, tree

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Print vertical sum of all the axis in the given binary tree

Find Pythagorean Triplets in an array in O(N)

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Best Java Book | Top Java Programming Book for Beginners

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

simple sql injection

Hackerearth : Counting Subarrays

Find the element that appears once others appears thrice

Find Percentage of Words matching in Two Strings

Linked List V/S Binary Search Tree

Maximum of all subarrays of size k

Password Predictor

Code Chef PRGIFT Solution

Handle duplicates in Binary Search Tree

Edit Distance ( Dynamic Programming )

Find loop in Singly linked list

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Client Server C program

Memory Efficient LinkedList

Count Possible Decodings of a given Digit Sequence

Coin Collection Dynamic Programming

BlueStone E-commerce Interview Experience

Amazon Interview On-Campus For Internship – 1

Leetcode: Edit Distance

Right view of Binary tree

LeetCode : Word Search

Print all nodes that are at distance k from a leaf node

Reversal of LinkedList

FizzBuzz Solution C C++

The greedy coins game Dynamic Programming

Copyright © 2025 · Genesis Framework · WordPress · Log in