Как преобразовать этот код BFS в DFS и UCS с использованием реализации стека ..?

Question

Это код BFS с использованием очереди G1: вершина из коллекции импорта deque, и я хочу реализовать код DFS и UCS из этого кода BFS, используя стек вместо очереди. Пожалуйста, помогите мне с этим кодом.

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])

с участием

queue=[start] # just a list

А также

vertex = queue.popleft()

с участием

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']