O problema da sua solução é que a função percorrer
não tem acesso a lista
, que é onde você guarda a informação sobre quais vértices você já visitou. Você tem que passar essa informação de alguma forma para a função que vai fazer a recursão. Eu juntei as funções, coloquei uns comentários e fiz um código mais idiomático:
# encoding: utf-8
# A linha anterior permite usar acentos no nosso programa.
def gerar_caminhos(grafo, caminho, final):
"""Enumera todos os caminhos no grafo `grafo` iniciados por `caminho` e que terminam no vértice `final`."""
# Se o caminho de fato atingiu o vértice final, não há o que fazer.
if caminho[-1] == final:
yield caminho
return
# Procuramos todos os vértices para os quais podemos avançar…
for vizinho in G[caminho[-1]]:
# …mas não podemos visitar um vértice que já está no caminho.
if vizinho in caminho:
continue
# Se você estiver usando python3, você pode substituir o for
# pela linha "yield from gerar_caminhos(grafo, caminho + [vizinho], final)"
for caminho_maior in gerar_caminhos(grafo, caminho + [vizinho], final):
yield caminho_maior
# Exemplo de uso
G = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D'], 'D': ['B', 'C']}
for caminho in gerar_caminhos(G, ['A'], 'D'):
# "print(caminho)" em python3
print caminho
(IDEOne)
Pra evitar a repetição, eu uso o operador in
do Python, que verifica se um objeto pertence a uma lista (ou um conjunto, ou às chaves de um dicionário) — isso quer dizer que eu ignoro os vizinhos do vértice atual pelos quais eu já passei.
A outra coisa que eu faço é usar o yield
na minha função — é mais fácil ilustrar o que ele faz com um exemplo mais simples:
def LOST():
yield 4
yield 8
yield 15
yield 16
yield 23
yield 42
for n in LOST():
print n
O yield
funciona como se fosse um return
, mas pensado para ser usado em um for
. O yield
, ao contrário do return
, não interrompe a execução da função: ele devolve o valor para o for
, deixa o for
fazer o serviço dele, e depois volta a executar a função de onde ele parou.
A ideia da chamada recursiva a gerar_caminhos(grafo, caminho + [vizinho], final)
é que é permitido ir a vizinho
partindo de caminho[-1]
(o último elemento de caminho
); eu procuro todos os caminhos que fazem isso, devolvo eles para a função-mãe (i.e. a função que me chamou), e repito isso para todos os vizinhos que já não estão no caminho (assim evitando a repetição).