Python Patterns – Implementing Graphs | Python.org

Change notes: 2/22/98, 3/2/98, 12/4/00: Esta versão deste ensaio corrige vários bugs no código. 6/10/19: Retracção defind_shortest_pathcomo “quase óptimo”. 8/11/19: Correção do uso acidental defind_graph()ao invés defind_path()

Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.

Os gráficos são redes constituídas por nós conectados por arestas ou arcos. Nos gráficos indiretos, as conexões entre nós têm uma direção, e são chamadas de arcos; nos gráficos não direcionados, as conexões não têm direção e são chamadas de arestas. Nós discutimos principalmente os gráficos dirigidos. Algoritmos nos gráficos incluem encontrar um caminho entre dois nós, encontrar o caminho mais curto entre dois nós, determinar ciclos no gráfico (um ciclo é um caminho não vazio de um nó para si mesmo), encontrar um caminho que chega a todos os nós (o famoso “problema do vendedor ambulante”), e assim por diante. Às vezes os nós ou arcos do agraph têm pesos ou custos associados a eles, e estamos interessados em encontrar o caminho mais barato.

Há uma literatura considerável sobre algoritmos gráficos, que são uma parte importante da matemática discreta. Os gráficos também têm muito uso prático de algoritmos de incomputador. Exemplos óbvios podem ser encontrados no gerenciamento de redes, mas exemplos abundam em muitas outras áreas. Por exemplo, relações caller-callee em um programa de computador podem ser vistas como um gráfico (onde ciclos indicam recursividade, e nós inalcançáveis representam deadcode).

Poucas linguagens de programação fornecem suporte direto para gráficos como um tipo de dado, e Python não é exceção. Entretanto, os gráficos são facilmente construídos a partir de listas e dicionários. Por exemplo, aqui está um gráfico simples (não posso usar desenhos nestas colunas, então eu escrevo os arcos do gráfico):

 A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C

Este gráfico tem seis nós (A-F) e oito arcos. Ele pode ser representado pela seguinte estrutura de dados Python:

 graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }

Este é um dicionário cujas chaves são os nós do gráfico. Para cada chave, o valor correspondente é uma lista contendo os nós que estão conectados por um arco direto deste nó. Isto é tão simples quanto possível (evensimpler, os nós poderiam ser representados por números ao invés de nomes, mas nomes são mais convenientes e podem ser facilmente feitos para carregar mais informações, como nomes de cidades).

Vamos escrever uma função simples para determinar um caminho entre dois nós. O gráfico e os nós de início e fim são argumentos. Ele retornará a lista de nós (incluindo os nós inicial e final) que compõem o caminho. Quando nenhum caminho pode ser encontrado, ele retorna Nenhum. O mesmo nó não ocorrerá mais de uma vez na trajetória retornada (ou seja, não conterá ciclos). O agloritmo usa uma técnica importante chamada backtracking: ele trieseach possibilidade por sua vez até encontrar uma solução.

 def find_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None for node in graph: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None

A sample run (usando o gráfico acima):

 >>> find_path(graph, 'A', 'D') >>>

A segunda declaração ‘se’ é necessária apenas no caso de haver nós que estão listados como pontos finais para arcos, mas que não têm arcos de saída, e não estão listados no gráfico de forma alguma. Tais nós também poderiam estar contidos no gráfico, com uma lista vazia de arcos de saída, mas algumas vezes é mais conveniente não requerer isto.

Note que enquanto o usuário chama find_path() com três argumentos, ele se chama com um quarto argumento: o caminho que já foi percorrido. O valor padrão para este argumento é a lista vazia, ”, significando que os nós ainda não foram percorridos. Este argumento é usado para evitar ciclos (o primeiro ‘se’ dentro do laço ‘para’). O argumento ‘path’ não é modificado:a atribuição “path = path + ” cria uma nova lista. Se tivéssemos escrito “path.append(start)” em vez disso, teríamos modificado a variável ‘path’ no autor da chamada, com resultados desastrosos. (Usando tuples, poderíamos ter a certeza que isso não aconteceria, ao custo de ter que escrever “path = path + (start,)” uma vez que “(start)” não é um tuple de um único botão — é apenas uma expressão entre parênteses.)

É simples mudar esta função para retornar uma lista de todos os caminhos (sem ciclos) em vez do primeiro caminho que encontra:

 def find_all_paths(graph, start, end, path=): path = path + if start == end: return if not graph.has_key(start): return paths = for node in graph: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths

Uma execução de amostra:

 >>> find_all_paths(graph, 'A', 'D') , , ] >>>

Outra variante encontra o caminho mais curto:

 def find_shortest_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest

Execução de amostra:

 >>> find_shortest_path(graph, 'A', 'D') >>>

Estas funções são tão simples quanto elas. Ainda assim, elas são quase ideais (para código escrito em Python). Em outra coluna Python Patternscolumn, tentarei analisar sua velocidade de execução e melhorar seu desempenho, ao custo de mais código.

UPDATE: Eryk Kopczyński apontou que estas funções não são ótimas. Pelo contrário, “este programa roda em tempo exponencial, enquanto find_shortest_path pode ser feito em tempo linear usando BFS . Além disso, um BFS linear é mais simples:”

 # Code by Eryk Kopczyński def find_shortest_path(graph, start, end): dist = {start: } q = deque(start) while len(q): at = q.popleft() for next in graph: if next not in dist: dist = , next] q.append(next) return dist.get(end)

Note que isto retorna o caminho em um formato estranho, por exemplo,, 'B'], 'D']. Em particular,len(find_shortest_path(graph, 'A', 'D'))dará a resposta incorreta (2, porque a lista externa é de comprimento 2). Isto é porque o apêndice é feito como, next]em vez dedist+. O segundo método usaria quadratictime e memória, mas ainda assim deve ser bom para gráficos relativamente pequenos; caso contrário, é fácil transformar a lista no formato correto.

Outra variação seria adicionar mais abstração de dados: criar uma classe de gráficos rasgados, cujos métodos implementam os vários algoritmos. Enquanto isto apela ao desejo de programação estruturada, não torna o código mais eficiente (ao contrário). Ele facilita a inserção de etiquetas variáveis nos nós ou arcos e a adição de algoritmos que levam esses rótulos em conta (por exemplo, para encontrar a rota mais curta entre duas cidades no mapa). Este também será o assunto de outra coluna.