Breath First Search

Apr 28 • General • 2185 Views • 1 Comment on Breath First Search

Breath First Search

Tree Traversal

Traveling from the start node to find the target node, by visiting all the nodes only once with the available path(edge).

Before we gonna know about DFS we need to know the basics of a tree stucture

A tree is a hierarchical order of nodes that that contains

• ROOT (top node of the tree)
• NODE (all elements in the tree will be considered as NODE)
• PARENT (any node that contain child / children) a ROOT also PARENT if it contains children but we cant consider every PARENT is a ROOT
• CHILD (any node that does not contain child) all the leaf nodes are CHILD
• EDGES (like branches will connect 2 nodes

this is a tipi cal example of a tree

picture of a tree that explains traversal

Breadth-first search(BFS)

Breadth-first search is a way to find all the nodes reachable from the a given source node, s. Like depth first search, BFS traverse a connected component(nodes) 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 A. The wave hits all nodes 1 edge from A. From there, the wave hits all node 2 edges from A. 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.

A simple Breath first search example

Algorithm for BFS

BFS(V, E, s)

for each u in V − {s}
do color[u] ← WHITE
d[u] ← infinity
π[u] ← NIL
color[s] ← GRAY
d[s] ← 0
π[s] ← NIL
Q ← {}
ENQUEUE(Q, s)
while Q is non-empty
do u ← DEQUEUE(Q)
for each v adjacent to u
do if color[v] ← WHITE
then color[v] ← GRAY
d[v] ← d[u] + 1
π[v] ← u
ENQUEUE(Q, v)
DEQUEUE(Q)
color[u] ← BLACK

Now we can see the step by step working principle with pictorial representation

STEP 1:

Now our task is to reach the node F (TARGET) by using Breath First Search

Initially no node is visited except the ROOT node

Path Traveled: A

STEP 1

STEP 2

Now there is no node present to the right of A so we need to go down

we have to select the node from left, so now we have to visit the node B

Path Traveled: A,B

step 2

STEP 3

Now we have node on the right side so we have to travel to the right node
i.e from B to C

Path Traveled: A,B,C

step 3

STEP 4

There is no node present right to the node C, so we have to come down
Again we have to go down
i.e: from C to D

Path Traveled : A,B,C,D

step 4

Step 5

now we have nodes right to node D so we have to visit the node E

Path Traveled: A,B,C,D,E

step 5

STEP 6

Still we have nodes right to E, even though it’s belong to other branch we can visit those nodes level wise

so our next node is node F

it’s not only the next node it’s our TARGET so we can stop the search from here

Path Traveled: A,B,C,D,E,F

step 6

we have achieved the task

« SBI CLERK GRADE SAMPLE PAPER Depth First Search »