如何使用堆栈实现将此BFS代码转换为DFS和UCS。？

Question

这是使用队列G1：vertex的BFS代码从集合导入双端队列，我想使用堆栈而不是队列从此BFS代码中实现DFS和UCS代码。请用此代码帮助我。

graph={ 'a': set(['b','c']),
        'b': set(['a','d']),
        'c': set(['a','d','f']),
        'd': set(['b','c','e','s']),
        'e': set(['d','h','s','r']),
        'f': set(['G','c','r']),
        'G': set(['f']),
        'h': set(['e','p','q']),
        'p': set(['s','q','h']),
        'q': set(['p','h']),
        'r': set(['e','f']),
        's': set(['d','e','p'])}

def bfs(graph, start,goal):
    visited= []
    path=[]
    queue=deque([start])

    while queue:
        vertex= queue.popleft()

        if vertex not in path:        
           path.extend(vertex)
           visited.extend(vertex)
           queue.extend(list(set(graph[vertex])))
        if goal in path:
            return (path,visited)
        checker=1
        for a in graph:
            for b in graph[a]:
                if b in path:
                    checker=(checker)*(1)
                else:
                     checker=(checker)*(0)
            if(checker>0):
                if a not in visited:
                    visited.extend(a)
    return (path,visited)
p=[]
p.extend(bfs(graph,'s','G'))
print("path :",p[0])
print("visited nodes:",p[1])

Answer 1

替换

queue=deque([start])

with

queue=[start] # just a list

和

vertex = queue.popleft()

with

vertex= queue.pop(-1) # like a stack, pop the last item from the list

输出变为：

path : ['s', 'd', 'b', 'a', 'c', 'f', 'r', 'e', 'h', 'p', 'q', 'G']
visited nodes: ['s', 'd', 'b', 'a', 'c', 'f', 'r', 'e', 'h', 'p', 'q', 'G']