Breadth First Search (BFS)

Posted By on November 5, 2014


Download PDF
Graphs Traversal/Searching
Depth First Search (DFS)

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

Example: The following figure (from CLRS) illustrates the progress of breadth-first search on the undirected sample graph.

a. After initialization (paint every vertex white, set d[u] to infinity for each vertex u,  and set the parent of every vertex to be NIL), the source vertex is discovered in line 5. Lines 8-9 initialize Q to contain just the source vertex s.

b. The algorithm discovers all vertices 1 edge from s i.e., discovered all vertices (w and r) at level 1.

c.

d. The algorithm discovers all vertices 2 edges from s i.e., discovered all vertices (t, x, and v) at level 2.

e.

f.

g. The algorithm discovers all vertices 3 edges from s i.e., discovered all vertices (u and y) at level 3.

h.

i. The algorithm terminates when every vertex has been fully explored.

Analysis

  • The while-loop in breadth-first search is executed at most |V| times. The reason is that every vertex enqueued at most once. So, we have O(V).

  • The for-loop inside the while-loop is executed at most |E| times if G is a directed graph or 2|E| times if G is undirected. The reason is that every vertex dequeued at most once and we examine (u, v) only when u is dequeued. Therefore, every edge examined at most once if directed, at most twice if undirected. So, we have O(E).

Therefore, the total running time for breadth-first search traversal is O(V + E).

Graphs Traversal/Searching
Depth First Search (DFS)

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com