Example 1: python breadth first search
def breadthFirstSearch(root):
q = [root]
while q:
current = q.pop(0)
print(current)
if current.left is not None: q.append(current.left)
if current.right is not None: q.append(current.right)
Example 2: breadth first search
procedure BFS(G, start_v) is
2 let Q be a queue
3 label start_v as discovered
4 Q.enqueue(start_v)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as discovered then
11 label w as discovered
12 w.parent := v
13 Q.enqueue(w)
Example 3: depth first search
class Graph:
def __init__(self,lst=None):
self.lst=dict()
if lst is None:
pass
else:
self.lst=lst
def find_path(self,start,end):
self.checklist={}
for i in self.lst.keys():
self.checklist[i]=False
self.checklist[start]=True
store,extra=(self.explore(start,end))
if store==False:
print('No Path Found')
else:
print(extra)
def explore(self,start,end):
while True:
q=[]
q.append(start)
flag=False
for i in self.lst[start]:
if i==end:
q.append(i)
return True,q
if self.checklist[i]:
pass
else:
flag=True
self.checklist[i]=True
q.append(i)
break
if flag:
store,extra=self.explore(q[-1],end)
if store==False:
q.pop()
if len(q)==0:return False
return self.explore(q[-1],end)
elif store==None:
pass
elif store==True:
q.pop()
q.extend(extra)
return True,q
else:
return False,None
def __str__(self):return str(self.lst)
if __name__=='__main__':
store={1: [2, 3, 4], 2: [3, 1], 3: [2, 1], 4: [5, 8, 1], 5: [4, 6, 7], 6: [5, 7, 9, 8], 7: [5, 6], 8: [4, 6, 9], 9: [6, 8, 10], 10: [9],11:[12,13]}
a=Graph(store)
a.find_path(1,11)
a.find_path(1,6)
a.find_path(3,10)
a.find_path(4,10)
print(a)
Example 4: depth first search stack
DFS-iterative (G, s): //Where G is graph and s is source vertex
let S be stack
S.push( s ) //Inserting s in stack
mark s as visited.
while ( S is not empty):
//Pop a vertex from stack to visit next
v = S.top( )
S.pop( )
//Push all the neighbours of v in stack that are not visited
for all neighbours w of v in Graph G:
if w is not visited :
S.push( w )
mark w as visited
DFS-recursive(G, s):
mark s as visited
for all neighbours w of s in Graph G:
if w is not visited:
DFS-recursive(G, w)
Example 5: bfs
function breadthFirstSearch (Start, Goal)
{
enqueue(Queue,Start)
setVisited(start)
while notEmpty(Queue)
{
Node := dequeue(Queue)
if Node = Goal
{
return Node
}
for each Child in Expand(Node)
{
if notVisited(Child)
{
setVisited(Child)
enqueue(Queue, Child)
}
}
}
}
Example 6: bfs algorithm
function breadthFirstSearch (Start, Goal)
{
enqueue(Queue,Start)
setVisited(start)
while notEmpty(Queue)
{
Node := dequeue(Queue)
if Node = Goal
{
return Node
}
for each Child in Expand(Node)
{
if notVisited(Child)
{
setVisited(Child)
enqueue(Queue, Child)
}
}
}
}