广度优先搜索Python代码到深度优先搜索

Question

我写了一些代码，在定义图时执行BFS。我现在需要编辑代码来做DFS，有人知道我需要更改什么才能完成吗？

这是我现在拥有的BFS代码：

class MyQUEUE: # Just an implementation of a queue.
def __init__(self): # Initialises the queue to an empty queue.
self.holder = []
def enqueue(self,val):
# Appends item val onto the end of the queue.
self.holder.append(val)
def dequeue(self):
# Pops the head off the queue and returns it value.
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):
# Returns True if the queue is empty.
result = False
if len(self.holder) == 0:
result = True
return result

def BFS(graph,start,end):
# Traverses the graph using a Breadth First Search starting
# from the start node with end being the goal node. Uses a
# queue to store the nodes that are current leaves at the
# fringe of the search.
q = MyQUEUE() # make an empty queue first
q.enqueue([start]) # add the start node onto the queue
while q.IsEmpty() == False:
path = q.dequeue()
last_node = path[len(path)-1]
print (path)
if last_node == end:
print ("VALID_PATH : ", path)
for link_node in graph[last_node]:
if link_node not in path:
new_path = []
new_path = path + [link_node]
q.enqueue(new_path)

Answer 1

不是在开头追加-插入：

修改：

self.holder.append(val)

至：

self.holder.insert(0, val)

解释

当BFS"一层一层"地"药丸"邻居时，DFS会"一直到底部"并返回。通过改变我们迭代邻居的顺序(递归(，我们实际上是在将BFS修改为DFS。

更新

正如Kaya在下面评论的那样，如果我们关心性能，我们应该使用append/pop而不是insert，因为insert取O(n(，而append/pop是O(1(