Breadth-first search is a way to find all the vertices
reachable from the a given source vertex,
s. Like depth first search,
BFS traverse a connected component of a given graph and defines a spanning tree. Intuitively, the basic idea of the
breath-first search is this: send a wave out from source
s. The wave hits all
vertices 1 edge from
s. From there, the wave hits all vertices 2 edges from
s.
Etc. We use FIFO queue Q to maintain the wavefront:
v is in Q if and only if
wave has hit
v but has not come out of
v yet.
Overall Strategy of BFS Algorithm
Breadth-first search starts at a given vertex s, which is at level 0.
In the first stage, we visit all the vertices that are at the distance of one edge away.When we visit there, we paint as "visited," the vertices adjacent
to the start vertex s - these vertices are placed into level 1. In the
second stage, we visit all the new vertices we can reach at the distance of two
edges away from the source vertex s.These new vertices, which are adjacent to
level 1 vertices and not previously assigned to a level, are placed into level
2, and so on. The BFS traversal terminates when every vertex has been visited.
To keep track of progress, breadth-first-search colors each
vertex. Each vertex of the graph is in one of three states:
1. Undiscovered;
2. Discovered but not fully explored; and
3. Fully explored.
The state of a vertex, u, is stored in a color variable as
follows:
1. color[u] = White - for the "undiscovered" state,
2. color [u] = Gray - for the "discovered but not fully explored"
state, and
3. color [u] = Black - for the "fully explored" state.
The BFS(G, s) algorithm develops a breadth-first search tree
with the source vertex, s, as its root
The parent or predecessor of any other
vertex in the tree is the vertex from which it was first discovered. For each
vertex, v, the parent of v is placed in the variable π[v]. Another
variable, d[v], computed by BFS contains the number of tree edges on the path
from s to v. The breadth-first search uses a FIFO queue, Q, to store gray vertices.
Algorithm: Breadth-First Search Traversal
BFS(V, E, s)
1. for each
u
in V − {s} ▷ for each vertex u in V[G] except s.
2.
do
color[u] ← WHITE
3.
d[u] ← infinity
4.
π[u] ← NIL
5. color[s] ← GRAY
▷ Source
vertex discovered
6. d[s] ← 0
▷ initialize
7. π[s] ← NIL
▷ initialize
8. Q ← {}
▷ Clear
queue Q
9. ENQUEUE(Q, s)
10 while Q is
non-empty
11.
do u ← DEQUEUE(Q)
▷ That is, u = head[Q]
12.
for each v adjacent to u
▷ for loop for every node along with edge.
13.
do if color[v] ← WHITE
▷ if color is white you've never seen it before
14.
then color[v] ← GRAY
15. d[v]
← d[u] + 1
16. π[v]
←
u
17. ENQUEUE(Q,
v)
18.
DEQUEUE(Q)
19. color[u] ← BLACK
