2 Replies - 400 Views - Last Post: 17 February 2014 - 06:18 PM Rate Topic: -----

#1 lloyd4076  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 40
  • Joined: 16-February 14

Depth First Search Stack

Posted 16 February 2014 - 11:46 AM

I need to modify the MyQUEUE class, so that It can do Depth First Search. Currently this will so a Breadth First Search.

What I'm trying to achieve is cgainging the MyQueue to a stack. So when im using the enqueue procedure the values will be placed at the beginning of the queue rather than the end of the queue.

How would i go abouts on doing this. By still using the MyQUEUE class. I need to prepend the value in enqueue rather than append. From this all rather than a breadth search i need to achieve a depth first search.


graph = {'A': ['F', 'D','C'],
         'B': ['A','C', 'D'],
         'C': ['D','A','F'],
         'D': ['C'],
         'E': ['F','D'],
         'F': ['C']}

class MyQUEUE: # just an implementation of a queue
	
	def __init__(self):
		self.holder = []
		
	def enqueue(self,val):
		self.holder.push(val)
		
	def dequeue(self):
		val = None
		try:
			val = self.holder[0]
			if len(self.holder) == 1:
				self.holder = []
			else:
				self.holder = self.holder[1:]	
		except:
			pass
			
		return val
		
	def IsEmpty(self):
		result = False
		if len(self.holder) == 0:
			result = True
		return result


path_queue = MyQUEUE() # now we make a queue


def BFS(graph,start,end,q):
	
	temp_path = [start]
	
	q.enqueue(temp_path)
	
	while q.IsEmpty() == False:
		tmp_path = q.dequeue()
		last_node = tmp_path[len(tmp_path)-1]
		print tmp_path
		if last_node == end:
			print "VALID_PATH : ",tmp_path
		for link_node in graph[last_node]:
			if link_node not in tmp_path:
				new_path = []
				new_path = tmp_path + [link_node]
				q.enqueue(new_path)



BFS(graph,"A","D",path_queue)


Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: Depth First Search Stack

#2 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Depth First Search Stack

Posted 17 February 2014 - 07:01 AM

Input removed my DK3250

This post has been edited by DK3250: 17 February 2014 - 07:05 AM

Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7744
  • View blog
  • Posts: 13,099
  • Joined: 19-March 11

Re: Depth First Search Stack

Posted 17 February 2014 - 06:18 PM

The only difference between a queue and a stack is that a stack removes from the same end that you add to.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1