• 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

Given a string, find the first character which is non-repetitive

TicTacToe Game As Asked in Flipkart

Find the smallest window in a string containing all characters of another string

The Magic HackerEarth Nirvana solutions Hiring Challenge

Common Ancestor in a Binary Tree or Binary Search Tree

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

Possible sizes of bus to carry n groups of friends

Edit Distance ( Dynamic Programming )

Amazon Interview Experience – SDE Chennai

Add Sub Multiply very large number stored as string

Reverse a Linked List in groups of given size

Difference between a LinkedList and a Binary Search Tree BST

Number of Islands BFS/DFS

Password Predictor

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

LeetCode: Binary Tree Maximum Path Sum

Check if an array has duplicate numbers in O(n) time and O(1) space

BlueStone E-commerce Interview Experience

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Serialise Deserialise N-ary Tree

Generate largest number arranging a no. of given non negative integer numbers

Closed Parentheses checker

Knight Tour Problem (Graph – Breadth First Search)

Coin Collection Dynamic Programming

LeetCode: Container With Most Water

FizzBuzz Solution C C++

Hackerearth : Counting Subarrays

Spanning Tree

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

Introduction To Number Theory ( Part 1 )

Copyright © 2026 · Genesis Framework · WordPress · Log in