• 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

Python String and numbers

Walmart Labs Interview Experience

Max Sum in circularly situated Values

Hackerearth : Counting Subarrays

Sequence Finder Dynamic Programming

Maximum of all subarrays of size k

Diagonal Traversal of Binary Tree

Daughter’s Age VeryGood Puzzle

Find next greater number with same set of digits

Password Predictor

Maximum path sum between two leaves

Adobe Interview Questions 8 month Exp

Maximum difference between two elements s.t larger element appears after the smaller number

CodeChef’ RRCOPY

Maximum occurred Smallest integer in n ranges

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

Connect n ropes with minimum cost

Stock Buy Sell to Maximize Profit

Knight Tour Problem (Graph – Breadth First Search)

LeetCode : Word Search

simple sql injection

strtok()

The Magic HackerEarth Nirvana solutions Hiring Challenge

Find Nearest Minimum number in left side in O(n)

Get K Max and Delete K Max in stream of incoming integers

Difference between a LinkedList and a Binary Search Tree BST

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

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

Doubly linked list

Code Chef PRGIFT Solution

Copyright © 2025 · Genesis Framework · WordPress · Log in