Wednesday, June 25, 2014

My Future Diary: Breadth-first search coding in Python

 My future diary for revision:
#Breadh First search
import Queue
initial = 9925065 
GRAPH = { 1:[(2,initial) ,(3,initial)] , 3:[(4,initial) ,(5,initial),(8,initial)] , 2: [(5,initial),(52,initial)] , 5:[(9,initial)] , 8:[(126,initial)]   }

key = GRAPH.keys() # Here 1,2,3,,5,6,8 excet the root*/
   
for i in range(len(key)):
    vertice = GRAPH[key[i]]
    print "Parent : "+ str(key[i])
    for j in (vertice):
      print  " " + str(j[0])


queue = Queue.Queue()

root = (1,0)
search   = input('Enter which vertices You want to search: ')
found = 0

print "Root : " + str(root)
print "Need to find   : " + str(search)
queue.put(root)

visit = []
while not queue.empty():

     current_node = queue.get()

     print  "Current node : "+ str(current_node)
    
     if current_node[0] == search :
         found = current_node[1] #value/cost/complexity
         print "Found"
         print "Complexity = " + str(found)
         found  = 1
         break
      
   
     if GRAPH.has_key(current_node[0]) and (visit.count(current_node[0]) == 0 ):
       
         child_node = GRAPH[current_node[0]]
         previous_cost = current_node[1]
         new_cost = previous_cost + 1
         print "child node  of  "+ str(current_node)+" are " + str(child_node)
         visit.append(current_node)      
         for i in child_node:
             child_previous_cost = i[1]
             if(child_previous_cost > new_cost):
                 new_node_status = (i[0] , new_cost)
                 queue.put(new_node_status)
          
   
       
   
if found == 0:
    print "The desired node doesn't exist in the tree"




Courtesy: Kowsar Hossain Auvi Sir
                Robin halder
Post a Comment

Add Choice