BFS

BFS

0
63
views
bfs
bfs

BFS Stands for Breadth first search.It is one of the graph traversal technique

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’[1]), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

Actually many graph problems can be solved using search methods.

Here the search method can be like:

  • Path from one vertex to another i.e; searching from one vertex to another.
  • Is the graph connected to another.
  • or by finding a spanning tree etc.

Commonly used search methods are BFS and DFS.

BFS: Breadth first search, In this algorithm, we take a graph first we visit start vertex and put it into a queue. After that repeatedly remove a vertex from queue(i.e; if it visits all the vertices) .visit it unvisited adjacent vertex and put newly visited vertex in a queue.

The main differences are the Breadth first search uses the queue and the Depth first search uses Stack.

Psuedo code:

Input: Graph G

Queue Q

Integers S X

while G has an unvisited node then do , s= an unvisited node

And visit that node(s)