Existem várias maneiras de implementar um gráfico direcionado no Python, cada um com suas próprias vantagens e desvantagens, dependendo dos requisitos específicos de aplicação e desempenho. Aqui estão três abordagens comuns:
1. Lista de adjacência (usando um dicionário) *
Conceito: Cada nó no gráfico é uma chave em um dicionário. O valor associado a cada chave (nó) é uma lista de seus vizinhos (os nós para os quais o nó chave tem uma borda direcionada). Este geralmente é o método mais eficiente e comumente usado, especialmente para gráficos esparsos (gráficos com relativamente poucas bordas).
*
Implementação: `` `Python
Classe DirectedGraph:
def __init __ (self):
self.graph ={} # dicionário para armazenar a lista de adjacência
DEFT add_node (self, nó):
Se o nó não estiver em self.graph:
self.graph [nó] =[]
DEFT add_edge (self, from_node, to_node):
Se de_node não estiver em self.graph:
self.add_node (de_node)
Se to_node não estiver em self.graph:
self.add_node (to_node) # ou levante um erro se você precisar de nós para ser explicitamente adicionado primeiro
self.graph [from_node] .append (to_node)
def get_neighbors (self, nó):
se nó em self.graph:
retornar self.graph [nó]
outro:
retornar [] # ou levantar um erro, dependendo do comportamento desejado
def remover_node (self, nó):
se nó em self.graph:
del self.graph [nó]
# Remova as bordas apontando * para * o nó excluído
para n em self.graph:
Se o nó em self.graph [n]:
self.graph [n] .remove (nó)
def remover_edge (self, from_node, to_node):
se de_node em self.graph e to_node em self.graph [de_node]:
self.graph [from_node] .remove (to_node)
def has_node (self, nó):
Nó devolver em self.graph
def has_edge (self, from_node, to_node):
Retorne de_node em self.graph e to_node em self.graph [de_node]
def __str __ (self):
retornar str (self.graph)
# Exemplo de uso
GRAPH =DirectedGraph ()
Graph.add_node ("A")
Graph.add_node ("B")
Graph.add_node ("C")
Graph.add_edge ("A", "B")
Graph.add_edge ("A", "C")
Graph.add_edge ("B", "C")
print (gráfico) # saída:{'a':['b', 'c'], 'b':['c'], 'c':[]}
print (graph.get_neighbors ("a")) # saída:['b', 'c']
print (graf.has_edge ("a", "b")) # saída:true
Graph.remove_edge ("A", "B")
print (gráfico) # saída:{'a':['c'], 'b':['c'], 'c':[]}
Graph.remove_node ("B")
print (gráfico) # saída:{'a':['c'], 'c':[]}
`` `
*
Vantagens: * Simples de implementar.
* Eficiente para gráficos esparsos.
* Fácil de encontrar vizinhos de um nó.
* Adicionar e remover nós/arestas pode ser relativamente eficiente (O (1), em média, para dicionários, O (n), na pior das hipóteses, para 'remover_node` devido à iteração de outros nós' listas de adjacência para remover as bordas apontando para o nó excluído).
*
Desvantagens: * Menos eficiente para gráficos densos (gráficos com quase todas as bordas possíveis).
* Verificação se existe uma aresta (exceto o uso de `has_edge ()`) requer iterar a lista do vizinho do nó de origem, que pode ser O (n) no pior dos casos.
2. Matriz de adjacência (usando uma lista/matriz 2D) *
Conceito: Use uma matriz 2D (ou uma lista de listas em python) em que `matriz [i] [j]` é 1 (ou `true`) se houver uma borda direcionada do nó` i` para node `j` e 0 (ou` false`) caso contrário.
*
Implementação: `` `Python
Classe DirectedGraphMatrix:
def __init __ (self, num_nodes):
self.num_nodes =num_nodes
self.matrix =[[0] * num_nodes para _ em range (num_nodes)]
DEFT add_edge (self, from_node, to_node):
se 0 <=from_node
self.matrix [From_Node] [para_node] =1
outro:
Imprimir ("índices de nó inválidos")
def remover_edge (self, from_node, to_node):
se 0 <=from_node self.matrix [From_Node] [para_node] =0
outro:
Imprimir ("índices de nó inválidos")
def has_edge (self, from_node, to_node):
se 0 <=from_node return self.matrix [de_node] [para_node] ==1
outro:
Imprimir ("índices de nó inválidos")
retornar falso
def get_neighbors (self, nó):
se 0 <=nó vizinhos =[]
para i em range (self.num_nodes):
se self.matrix [nó] [i] ==1:
vizinhos.append (i)
retornar vizinhos
outro:
Imprimir ("Índice de nós inválidos")
retornar []
def __str __ (self):
Retorne '\ n'.join ([' '.Join (mapa (str, linha) para linha em self.matrix]))
# Exemplo de uso:
GRAPH =DirectedGraphMatrix (4) # Gráfico com 4 nós
Graph.add_edge (0, 1)
Graph.add_edge (0, 2)
Graph.add_edge (1, 3)
Imprimir (gráfico)
# Saída:
# 0 1 1 0
# 0 0 0 1
# 0 0 0 0
# 0 0 0 0
print (graf.has_edge (0, 1)) # saída:true
print (graf.get_neighbors (0)) # saída:[1, 2]
`` `
* Vantagens:
* Rápido para verificar se existe uma borda (o (1)).
* Simples de implementar.
* Desvantagens:
* Requer predefinir o número de nós. Pode ser modificado para redimensionar dinamicamente, mas isso pode se tornar caro.
* Ineficiente para gráficos esparsos (resíduos muita memória).
* Adicionar/remover nós pode ser caro porque você precisa redimensionar toda a matriz.
3. Usando uma biblioteca de gráficos (por exemplo, Networkx)
* Conceito: Aproveite as bibliotecas de gráficos existentes que fornecem implementações otimizadas e uma riqueza de algoritmos de gráfico. Networkx é uma escolha popular.
* Implementação:
`` `Python
Importar Networkx como NX
# Crie um gráfico direcionado
Gráfico =nx.digraph ()
# Adicionar nós
Graph.add_nodes_from (["A", "B", "C"])
# Adicione arestas
Graph.add_edge ("A", "B")
Graph.add_edge ("A", "C")
Graph.add_edge ("B", "C")
# Verifique se existe uma vantagem
print (graf.has_edge ("a", "b")) # saída:true
# Obtenha vizinhos
print (list (graf.successors ("a"))) # saída:['b', 'c'] (sucessores =vizinhos de saída)
# Remova uma borda
Graph.remove_edge ("A", "B")
print (graf.has_edge ("a", "b")) # saída:false
# Remova um nó
Graph.remove_node ("B")
print (graph.nodes ()) # saída:['a', 'c']
# Você pode desenhar o gráfico (requer matplotlib)
# Importar matplotlib.pyplot como PLT
# nx.draw (gráfico, with_labels =true, node_color ="skyblue", node_size =1500, font_size =15)
# plt.show ()
`` `
* Vantagens:
* Biblioteca madura e bem testada.
* Fornece um rico conjunto de algoritmos de gráfico (caminho mais curto, medidas de centralidade, etc.).
* Mais fácil de executar operações gráficas complexas.
* Suporta a visualização do gráfico.
* Desvantagens:
* Ligeira sobrecarga em comparação com a implementação de sua própria estrutura gráfica.
* Requer a instalação de uma biblioteca externa.
Escolhendo a implementação correta
* gráficos esparsos: A lista de adjacência geralmente é a melhor escolha.
* gráficos densos: A matriz de adjacência pode ser mais rápida para verificações de existência de borda, mas consome mais memória. Considere as compensações.
* operações gráficas complexas: Use o Networkx ou outra biblioteca de gráficos. Se você precisar implementar algoritmos personalizados ou estiver trabalhando com gráficos muito grandes, convém usar as abordagens da lista de adjacência ou da matriz, mas você terá que implementar os algoritmos.
* tarefas simples: Se você só precisar de representação básica de gráficos e travessia, a lista de adjacência geralmente é suficiente.
Considerações importantes:
* Uso da memória: As listas de adjacência são mais eficientes em memória para gráficos esparsos. As matrizes de adjacência podem usar muita memória, especialmente para gráficos grandes e esparsos.
* desempenho: As matrizes de adjacência fornecem uma pesquisa de borda o (1), enquanto as listas de adjacência exigem O (n) no pior dos casos (onde n é o número de vizinhos).
* Facilidade de uso: As bibliotecas de gráficos fornecem uma API mais conveniente e rica em recursos.
* mutabilidade vs. imutabilidade: Decida se você precisa modificar a estrutura do gráfico com frequência. Listas de adjacência e matrizes são mutáveis. Os gráficos Networkx também são mutáveis. Se você precisar de um gráfico imutável, pode ser necessário explorar estruturas de dados alternativas.
* Gráficos ponderados: Se você precisar representar bordas ponderadas, poderá modificar a lista de adjacência ou a matriz para armazenar os pesos da borda. Por exemplo, na lista de adjacência, você pode armazenar um dicionário de `to_node:peso` em vez de apenas uma lista de nós. O NetworkX possui suporte interno para gráficos ponderados.
Antes de implementar um gráfico, considere cuidadosamente os requisitos do seu problema específico para escolher a estrutura e algoritmos de dados mais apropriados. Em caso de dúvida, comece com a lista de adjacência, pois é uma boa solução de uso geral. Se você prevê que precisam de algoritmos de gráficos mais avançados, a biblioteca Networkx geralmente é uma boa escolha.
