**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’) and explores the neighbor nodes first, before moving to the next level neighbors.

**Pseudocode**

**Input:**A graph G and a starting vertex v of G

**Output:**All vertices reachable from v labeled as explored.

A
non-recursive implementation of breadth-first search:

Breadth-First-Search(G, v):

for each
node n in G:

n.distance = INFINITY

n.parent = NIL

create
empty queue Q

v.distance = 0

Q.enqueue(v)

while Q
is not empty:

u =
Q.dequeue()

for
each node n that is adjacent to u:

if n.distance == INFINITY:

n.distance = u.distance + 1

n.parent = u

Q.enqueue(n)

https://en.wikipedia.org/wiki/Breadth-first_search

ReplyDelete