• 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

BlueStone E-commerce Interview Experience

ADOBE Aptitude C Language Test

Given Set of words or A String find whether chain is possible from these words or not

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

Count number of ways to reach a given score in a game

Maximum of all subarrays of size k

Implement a generic binary search algorithm for Integer Double String etc

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

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

1014 Practice Question of New GRE – Princeton

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Printing each word reverse in string

DFS (Depth First Search)

K’th Largest Element in BST when modification to BST is not allowed

Trie Dictionary

Level order traversal in Spiral form

Leetcode: Merge Intervals

Calculate price of parking from parking start end time prices

The greedy coins game Dynamic Programming

Find if two rectangles overlap

Amazon Interview On-Campus For Internship – 1

Count Possible Decodings of a given Digit Sequence

Regular Expression Matching

Generic Object Oriented Stack with Template

Best Java Book | Top Java Programming Book for Beginners

Cisco Hiring Event 21st – 22nd Feb 2015

Binary Tree in Java

System Design: Designing a LLD for Hotel Booking

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

Reverse a Linked List in groups of given size

Copyright © 2023 · Genesis Framework · WordPress · Log in