BFS (Boy Friend Search)....I am kidding its --Breadth First Search--

BFS is an graph searching algorithm.


Graph????????

• Has nodes (vertices)
• Has Edges (links) -can have a value(weight)

This is an example, Numbers show nodes and links connect

them.

Graphs can be directed or undirected.

picture shows an undirected graph. you can easily identify it... no arrows in links lads......

In directed graph ,,,

you can guess - can be traveled among nodes only in the indicated direction

My sample code for the BFS in python

to_visit = [0]



parent = {}

level4 = []

nodes = [0,1,2,3,4,5]

i = 0

while to_visit != [] and i <= len(to_visit)-1:

    front = to_visit[i]

    #del to_visit[0]



    for j in nodes:

        

        if j not in to_visit and adj[front][j] == 1:

            to_visit.append(j)

            parent[j]=front

    print to_visit,parent

    i+=1

• BFS can be used to get the shortest path in the graph.
• parent nodes of each node indicate the path