• 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

Stickler thief

Calculate price of parking from parking start end time prices

Wrong Directions given find minimum moves so that he can reach to the destination

System Design: Designing a LLD for Hotel Booking

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

Python String and numbers

Find Pythagorean Triplets in an array in O(N)

Implement LRU Cache

Generate next palindrome number

How strtok() Works

Leetcode: Merge Intervals

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Edit Distance ( Dynamic Programming )

Practo Hiring Experience

Memory Efficient LinkedList

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

Connect n ropes with minimum cost

SAP Hiring Off-Campus General Aptitude

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Find loop in Singly linked list

Regular Expression Matching

Find position of the only set bit

Naurki.com Security Breach

Interfaces in C++ (Abstract Classes in C++)

Find and print longest consecutive number sequence in a given sequence in O(n)

Trapping Rain Water

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

C++ OOPs Part2

Find the element that appears once others appears thrice

Printing intermediate Integers between one element & next element of array

Copyright © 2025 · Genesis Framework · WordPress · Log in