1. Elenco di adiacenza (utilizzando un dizionario)
* Concetto: Ogni nodo nel grafico è una chiave in un dizionario. Il valore associato a ciascun tasto (nodo) è un elenco dei suoi vicini (i nodi a cui il nodo chiave ha un bordo diretto). Questo è spesso il metodo più efficiente e comunemente usato, in particolare per i grafici sparsi (grafici con relativamente pochi bordi).
* Implementazione:
`` `Python
Classe DirectedGraph:
def __init __ (self):
self.graph ={} # Dizionario per archiviare l'elenco di adiacenza
def add_node (self, nodo):
Se nodo non in self.graph:
self.graph [nodo] =[]
def add_edge (self, from_node, to_node):
Se da_node non in self.graph:
self.add_node (from_node)
Se to_node non in self.graph:
self.add_node (to_node) # o sollevare un errore se è necessario aggiungere esplicitamente nodi esplicitamente
self.graph [from_node] .append (to_node)
def get_neighbors (self, nodo):
Se nodo in self.graph:
return self.graph [nodo]
altro:
restituire [] # o sollevare un errore, a seconda del comportamento desiderato
def thtoy_node (self, nodo):
Se nodo in self.graph:
del self.graph [nodo]
# Rimuovere i bordi indicando * * il nodo cancellato
per n in self.graph:
Se nodo in self.graph [n]:
self.graph [n] .remove (nodo)
def thtoy_edge (self, from_node, to_node):
Se from_node in self.graph e to_node in self.graph [from_node]:
self.graph [from_node] .remove (to_node)
def has_node (self, node):
restituire il nodo in self.graph
def has_edge (self, from_node, to_node):
restituire da_node in self.graph e to_node in self.graph [from_node]
def __str __ (self):
return str (self.graph)
# Esempio di utilizzo
grafico =direttoGraph ()
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 (grafico) # output:{'a':['b', 'c'], 'b':['c'], 'c':[]}
print (graph.get_neighbors ("a")) # output:['b', 'c']
print (graph.has_edge ("a", "b")) # output:true
graph.remove_edge ("a", "b")
print (grafico) # output:{'a':['c'], 'b':['c'], 'c':[]}
graph.remove_node ("b")
print (grafico) # output:{'a':['c'], 'c':[]}
`` `
* Vantaggi:
* Semplice da implementare.
* Efficiente per grafici sparsi.
* Facile da trovare vicini di un nodo.
* L'aggiunta e la rimozione di nodi/bordi può essere relativamente efficiente (O (1) in media per i dizionari, O (N) nel caso peggiore per `remove_node` a causa dell'iterazione attraverso elenchi di adiacenza di altri nodi per rimuovere i bordi indicando il nodo eliminato).
* Svantaggi:
* Meno efficiente per grafici densi (grafici con quasi tutti i bordi possibili).
* Verifica se esiste un vantaggio (diverso dall'uso di `has_edge ()`) richiede l'iteratura attraverso l'elenco vicino del nodo di origine, che può essere O (n) nel peggiore dei casi.
2. Matrice di adiacenza (utilizzando un elenco/array 2D)
* Concetto: Usa un array 2D (o un elenco di elenchi in Python) in cui `matrice [i] [j]` è 1 (o `vero`) se c'è un bordo diretto dal nodo` io` al nodo `j` e 0 (o` false`) altrimenti.
* Implementazione:
`` `Python
Classe DirectedGraphMatrix:
def __init __ (self, num_nodes):
self.num_nodes =num_nodes
self.matrix =[[0] * num_nodes per _ in gamma (num_nodes)]
def add_edge (self, from_node, to_node):
Se 0 <=from_node
altro:
Stampa ("Indici di nodo non validi.")
def thtoy_edge (self, from_node, to_node):
Se 0 <=from_node
altro:
Stampa ("Indici di nodo non validi.")
def has_edge (self, from_node, to_node):
Se 0 <=from_node
altro:
Stampa ("Indici di nodo non validi.")
restituire false
def get_neighbors (self, nodo):
Se 0 <=nodo
per i in gamma (self.num_nodes):
if self.matrix [nodo] [i] ==1:
vicini.append (i)
restituire i vicini
altro:
Stampa ("Indice di nodo non valido.")
ritorno []
def __str __ (self):
return '\ n'.Join ([' '.Join (map (str, riga)) per riga in self.matrix])
# Esempio di utilizzo:
Grafico =DirectedGraphMatrix (4) # Grafico con 4 nodi
Graph.add_edge (0, 1)
Graph.add_edge (0, 2)
Graph.add_edge (1, 3)
Stampa (grafico)
# Produzione:
# 0 1 1 0
# 0 0 0 1
# 0 0 0 0
# 0 0 0 0
print (graph.has_edge (0, 1)) # output:true
print (graph.get_neighbors (0)) # output:[1, 2]
`` `
* Vantaggi:
* Veloce da verificare se esiste un bordo (o (1)).
* Semplice da implementare.
* Svantaggi:
* Richiede predefinire il numero di nodi. Può essere modificato per ridimensionare dinamicamente, ma può diventare costoso.
* Inefficiente per i grafici sparsi (spreca molta memoria).
* L'aggiunta/rimozione di nodi può essere costosa perché è necessario ridimensionare l'intera matrice.
3. Utilizzo di una libreria di grafici (ad es. NetworkX)
* Concetto: Sfruttare le librerie di grafici esistenti che forniscono implementazioni ottimizzate e una vasta gamma di algoritmi grafici. NetworkX è una scelta popolare.
* Implementazione:
`` `Python
Importa NetworkX come NX
# Crea un grafico diretto
grafico =nx.digraph ()
# Aggiungi nodi
graph.add_nodes_from (["a", "b", "c"])
# Aggiungi bordi
graph.add_edge ("a", "b")
Graph.add_edge ("a", "c")
Graph.add_edge ("b", "c")
# Controlla se esiste un vantaggio
print (graph.has_edge ("a", "b")) # output:true
# Ottieni i vicini
stampa (elenco (graph.successors ("a")) # output:['b', 'c'] (successori =vicini uscenti)
# Rimuovi un bordo
graph.remove_edge ("a", "b")
print (graph.has_edge ("a", "b")) # output:false
# Rimuovi un nodo
graph.remove_node ("b")
print (graph.nodes ()) # output:['a', 'c']
# Puoi disegnare il grafico (richiede matplotlib)
# Importa matplotlib.pyplot come PLT
# nx.draw (grafico, with_labels =true, node_color ="skyblue", node_size =1500, font_size =15)
# plt.show ()
`` `
* Vantaggi:
* Biblioteca matura e ben testata.
* Fornisce un ricco set di algoritmi grafici (percorso più breve, misure di centralità, ecc.).
* Più facile eseguire operazioni grafiche complesse.
* Supporta la visualizzazione del grafico.
* Svantaggi:
* Leggero sovraccarico rispetto all'implementazione della propria struttura grafica.
* Richiede l'installazione di una libreria esterna.
Scegliere l'implementazione giusta
* Grafici sparsi: L'elenco di adiacenza è generalmente la scelta migliore.
* Grafici densi: La matrice di adiacenza può essere più veloce per i controlli dell'esistenza Edge, ma consuma più memoria. Considera i compromessi.
* Operazioni grafiche complesse: Utilizzare NetworkX o un'altra libreria di grafici. Se hai bisogno di implementare algoritmi personalizzati o stai lavorando con grafici molto grandi, potresti voler utilizzare l'elenco di adiacenza o gli approcci a matrice, ma dovrai implementare tu stesso gli algoritmi.
* Attività semplici: Se hai solo bisogno di una rappresentazione e di attraversamento del grafico di base, l'elenco di adiacenza è spesso sufficiente.
Considerazioni chiave:
* Utilizzo della memoria: Gli elenchi di adiacenza sono più efficienti dalla memoria per i grafici sparsi. Le matrici di adiacenza possono usare molta memoria, specialmente per grafici grandi e sparsi.
* Performance: Le matrici di adiacenza forniscono una ricerca di bordo O (1), mentre gli elenchi di adiacenza richiedono O (n) nel caso peggiore (dove n è il numero di vicini).
* Facilità d'uso: Le librerie di grafici forniscono un'API più conveniente e ricca di funzionalità.
* Mutabilità vs. immutabilità: Decidi se è necessario modificare frequentemente la struttura del grafico. Gli elenchi e le matrici di adiacenza sono mutabili. Anche i grafici NetworkX sono mutabili. Se hai bisogno di un grafico immutabile, potrebbe essere necessario esplorare strutture di dati alternative.
* Grafici ponderati: Se è necessario rappresentare i bordi ponderati, è possibile modificare l'elenco di adiacenza o la matrice per archiviare i pesi del bordo. Ad esempio, nell'elenco di adiacenza, è possibile archiviare un dizionario di `to_node:peso` invece di solo un elenco di nodi. NetworkX ha un supporto integrato per grafici ponderati.
Prima di implementare un grafico, considera attentamente i requisiti del problema specifico per scegliere la struttura e gli algoritmi più appropriati. In caso di dubbio, inizia con l'elenco di adiacenza, poiché è una buona soluzione per scopi generali. Se prevedi di aver bisogno di algoritmi grafici più avanzati, la libreria NetworkX è spesso una buona scelta.
Informazioni correlate
Programmazione © www.354353.com