Algoritmo Prim no NetworkX (exemplo de explicação)

Introdução

O algoritmo Prim é semelhante ao algoritmo de caminho mais curto de Dijkstra, ele usa uma estratégia de greed. O algoritmo começa adicionando a aresta de menor peso à árvore T e continuamente adicionando a aresta E (um dos vértices de E está em T, o outro em G-Quando não há arestas E que atendam aos requisitos, o algoritmo termina e T é uma menor floresta geradora de G.

NetworkX é um pacote de software Python para criar, operar redes complexas e aprender a estrutura, dinâmica e função das redes complexas. Este artigo utiliza a classe networkx.Graph para implementar o algoritmo Prim.

Texto

Código do algoritmo Prim

Prim

def prim(G, s):
 dist = {} # dist registra a menor distância até os nós
 parent = {} # parent registra a tabela pais da menor floresta geradora
 Q = lista(G.nodes()) # Q contém todos os nós não cobertos pela floresta geradora
 MAXDIST = 9999.99 # MAXDIST representa o infinito positivo, ou seja, os nós não são vizinhos
 # Inicializa dados
 # Define a menor distância de todos os nós como MAXDIST e os pais como None
 para v in G.nodes():
  dist[v] = MAXDIST
  parent[v] = None
 # Define a distância até o nó inicial s como 0
 dist[s] = 0
 # Continuar removendo o nó 'mais próximo' de Q e adicionando-o à menor floresta geradora
 # Para quando Q estiver vazio, para parar o loop, o algoritmo termina
 enquanto Q:
  # Remove o nó 'mais próximo' u e adiciona-o à menor floresta geradora
  u = Q[0]
  para v in Q:
   se (dist[v] < dist[u]):
    u = v
  Q.remove(u)
  # Atualiza a menor distância dos vizinhos de u
  para v in G.adj[u]:
   se (v in Q) e (G[u][v]['weight'] < dist[v]):
    parent[v] = u
    dist[v] = G[u][v]['weight']
 # A algoritmo termina, retornando o menor floresta geradora na forma de tabela pais
 return parent

Dados de teste

De ~ para	2	3	4	5	6	7	8
1	1.3	2.1	0.9	0.7	1.8	2.0	1.8
2		0.9	1.8	1.2	2.8	2.3	1.1
3			2.6	1.7	2.5	1.9	1.0
4				0.7	1.6	1.5	0.9
5					0.9	1.1	0.8
6						0.6	1.0
7							0.5

Código de teste

import matplotlib.pyplot as plt
import networkx as nx
g_data = [(1, 2, 1.3), (1, 3, 2.1), (1, 4, 0.9), (1, 5, 0.7), (1, 6, 1.8), (1, 7, 2.0), (1, 8, 1.8), (2, 3, 0.9), (2, 4, 1.8), (2, 5, 1.2), (2, 6, 2.8), (2, 7, 2.3), (2, 8, 1.1), (3, 4, 2.6), (3, 5, 1.7), (3, 6, 2.5), (3, 7, 1.9), (3, 8, 1.0), (4, 5, 0.7), (4, 6, 1.6), (4, 7, 1.5), (4, 8, 0.9), (5, 6, 0.9), (5, 7, 1.1), (5, 8, 0.8), (6, 7, 0.6), (6, 8, 1.0), (7, 8, 0.5)
def draw(g):
 pos = nx.spring_layout(g)
 nx.draw(g, pos, \

   arrows=True, \

   with_labels=True, \

   nodelist=g.nodes(), \

   style='dashed', \

   edge_color='b', \

   width=, \
2, \

   node_color='y', \

   alpha=0.5)
 plt.show()
g = nx.Graph()
g.add_weighted_edges_from(g_data)
tree = prim(g, 1)
mtg = nx.Graph()
mtg.add_edges_from(tree.items())
mtg.remove_node(None)
draw(mtg)

Resultados da execução

Este artigo sobre o algoritmo Prim do NetworkX (explicação em exemplos) é tudo o que o editor compartilhou com você, esperando que possa fornecer uma referência e que todos vocês possam apoiar e gritar tutorial.

Declaração: O conteúdo deste artigo é da Internet, pertence ao respectivo proprietário, foi carregado voluntariamente pelos usuários da Internet, este site não possui direitos de propriedade, não foi editado manualmente e não assume responsabilidade por questões legais relacionadas. Se você encontrar conteúdo suspeito de violação de direitos autorais, por favor, envie um e-mail para: notice#w3Declaração: O conteúdo deste artigo foi extraído da Internet, pertence ao respectivo proprietário, foi carregado por usuários da Internet de forma voluntária, este site não possui direitos de propriedade, não foi editado manualmente e não assume responsabilidade por questões legais relacionadas. Se você encontrar conteúdo suspeito de violação de direitos autorais, por favor, envie um e-mail para: notice#w