4

Eu tenho um dicionário, em que a chave é um vértice e o valor é uma lista de vértices adjacentes ao vértice (chave).

dic = {'A':['B,'C'],'B':['A','C','D'],'C':['A','B','D'],'D':['B','C']}

O que eu quero é uma matriz de todos os caminhos possíveis (de um vértice a outro, por exemplo de 'A' a 'D').

Já tentei tanta coisa, que não sei já mais o que tentar. Eu pensei em percorrer cada lista de vértices adjacentes, começando pela chave 'A' (por causa do exemplo) e depois para cada vértice adjacente percorrer a sua lista de vértices adjacentes. Tentei fazer isso, mas deu-me um erro, pelo que percebi não parava de percorrer.

def percorrer(v,vAux,dic):
  for e in dic.get(v):
    while e!=vAux:
        percorrer(e,vAux,dic)

def todosCaminhos(g,v1,v2):
   dicVertices = g.getVertices()
   for v in dicVertices:
       if v != v1:
           if v1 in dicVertices.get(v):
               dicVertices.get(v).remove(v1)
    matriz=[]
    lista=[]
    for v in dicVertices.get(v1):
        while v != v2:
            percorrer(v,v2,dicVertices)
            lista.append(v)
        matriz.append(lista)
    return matriz
4
  • Suponho que você quer gerar caminhos sem vértices repetidos (e.g. ['A', 'B', 'C', 'D'] seria legal mas ['A', 'B', 'C', 'B', 'D'] seria proibido)? Qual o número máximo de vértices desse grafo?
    – user25930
    Commented 5/06/2015 às 0:00
  • @ctgPi Sim, não é suposto haver vértices repetidos. Estou a criar esta função para ajudar noutra, e não faz sentido haver vértices repetidos. Este grafo pode ter n vértices, mas no exemplo que dei tem somente 4. Commented 5/06/2015 às 0:01
  • Tem como editar a pergunta e postar o código que você fez até agora (mesmo com esse problema de percorrer o grafo infinitamente)?
    – user25930
    Commented 5/06/2015 às 0:17
  • @ctgPi Editei, já pôs o código! Commented 5/06/2015 às 0:22

2 Respostas 2

2

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

5
  • Acho que percebi, por acaso já conhecia o yield, não costumo é usar, por não o conhecer bem.no python 3. Muito obrigada, deu-me uma grande ajuda! Commented 5/06/2015 às 0:53
  • uma curiosidade, basta fazermos: #encoding utf-8 no início do código e podemos utilizar acentos no código todo? Commented 5/06/2015 às 0:55
  • Dado que essa pergunta ainda não está no pt.StackOverflow (que quase não tem Python), eu preferia que você a fizesse como uma pergunta top-level, pra ela não ficar perdida aqui nos comentários.
    – user25930
    Commented 5/06/2015 às 0:57
  • Não sei bem o que pergunta top-level significa, mas perguntei no "Faça uma pergunta", lá em cima. Commented 5/06/2015 às 1:02
  • Era isso mesmo. :)
    – user25930
    Commented 5/06/2015 às 1:04
0

Use o algorítmo de busca Depth Dirst Search:

dic = {'A':['B','C'],'B':['A','C','D'],'C':['A','B','D'],'D':['B','C']}

def dfs_caminhos(grafo, inicio, fim):
    pilha = [(inicio, [inicio])]
    while pilha:
        vertice, caminho = pilha.pop()
        for proximo in set(grafo[vertice]) - set(caminho):
            if proximo == fim:
                yield caminho + [proximo]
            else:
                pilha.append((proximo, caminho + [proximo]))

caminhos = list(dfs_caminhos(dic, 'A', 'D'))
print(caminhos)
>>> [['A', 'B', 'D'], ['A', 'B', 'C', 'D'], ['A', 'C', 'D'], ['A', 'C', 'B', 'D']]

Primeiro caminho mais curto:

min(caminhos, key = len)
>>> ['A', 'B', 'D']

Você também poderia utlizar Breadth-first search.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .