fork download
copy 
  1. # encoding: utf-8
  2. # A linha anterior permite usar acentos no nosso programa.
  3.  
  4. def gerar_caminhos(grafo, caminho, final):
  5.     """Enumera todos os caminhos no grafo `grafo` iniciados por `caminho` e que terminam no vértice `final`."""
  6.  
  7.     # Se o caminho de fato atingiu o vértice final, não há o que fazer.
  8.     if caminho[-1] == final:
  9.         yield caminho
  10.         return
  11.  
  12.     # Procuramos todos os vértices para os quais podemos avançar…
  13.     for vizinho in G[caminho[-1]]:
  14.         # …mas não podemos visitar um vértice que já está no caminho.
  15.         if vizinho in caminho:
  16.             continue
  17.         # Se você estiver usando python3, você pode substituir o for
  18.         # pela linha "yield from gerar_caminhos(grafo, caminho + [vizinho], final)"
  19.         for caminho_maior in gerar_caminhos(grafo, caminho + [vizinho], final):
  20.             yield caminho_maior
  21.  
  22. # Exemplo de uso
  23. G = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D'], 'D': ['B', 'C']}
  24. for caminho in gerar_caminhos(G, ['A'], 'D'):
  25.     # "print(caminho)" em python3
  26.     print caminho
Success #stdin #stdout 0.01s 7736KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
['A', 'B', 'C', 'D']
['A', 'B', 'D']
['A', 'C', 'B', 'D']
['A', 'C', 'D']
https://ideone.com/FOHGSZ
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!