1. Lista de adyacencia (usando un diccionario)
* Concepto: Cada nodo en el gráfico es una clave en un diccionario. El valor asociado con cada clave (nodo) es una lista de sus vecinos (los nodos a los que el nodo clave tiene un borde dirigido). Este es a menudo el método más eficiente y comúnmente utilizado, especialmente para gráficos dispersos (gráficos con relativamente pocos bordes).
* Implementación:
`` `Python
Clase DirectedGraph:
def __init __ (self):
self.graph ={} # diccionario para almacenar la lista de adyacencias
def add_node (self, nodo):
Si el nodo no está en uno mismo. Graph:
self.graph [nodo] =[]
def add_edge (self, from_node, to_node):
Si de_node no está en self.graph:
self.add_node (from_node)
Si to_node no en self.graph:
self.add_node (to_node) # o elevar un error si requiere que los nodos se agregan explícitamente primero
self.graph [from_node] .append (to_node)
Def get_neighbors (self, nodo):
Si nodo en self.graph:
return self.graph [nodo]
demás:
devolver [] # o aumentar un error, dependiendo del comportamiento deseado
Def remove_node (self, nodo):
Si nodo en self.graph:
Del Self.Graph [nodo]
# Eliminar los bordes apuntando * a * el nodo eliminado
para n en uno mismo. Graph:
Si nodo en self.graph [n]:
self.graph [n] .remove (nodo)
Def remove_edge (self, from_node, to_node):
Si from_node en self.graph y to_node en self.graph [from_node]:
self.graph [from_node] .remove (to_node)
def has_node (self, nodo):
return nodo en self.graph
def has_edge (self, from_node, to_node):
Regrese de_node en self.graph y to_node en self.graph [from_node]
def __str __ (self):
return str (self.graph)
# Uso de ejemplo
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) # salida:{'a':['b', 'c'], 'b':['c'], 'c':[]}
print (gráfico.get_neighbors ("a")) # salida:['b', 'c']]
print (gráfico.has_edge ("A", "B")) # Salida:Verdadero
Graph.Remove_EDGE ("A", "B")
print (gráfico) # salida:{'a':['c'], 'b':['c'], 'c':[]}
Graph.remove_node ("B")
print (gráfico) # salida:{'a':['c'], 'c':[]}
`` `` ``
* ventajas:
* Simple de implementar.
* Eficiente para gráficos dispersos.
* Vecinos de un nodo fáciles de encontrar.
* Agregar y eliminar nodos/bordes puede ser relativamente eficiente (o (1) en promedio para los diccionarios, o (n) en el peor de los casos para `remove_node` debido a la itera a través de las listas de adyacencia de otros nodos para eliminar los bordes que apuntan al nodo eliminado).
* Desventajas:
* Menos eficiente para gráficos densos (gráficos con casi todos los bordes posibles).
* Comprobación de si existe un borde (aparte de usar `has_edge ()`) requiere iterarse a través de la lista de vecinos del nodo fuente, que puede ser o (n) en el peor de los casos.
2. Matriz de adyacencia (usando una lista/matriz 2D)
* Concepto: Use una matriz 2D (o una lista de listas en Python) donde `matriz [i] [j]` es 1 (o `true`) si hay un borde dirigido desde el nodo` i` a nodo `j`, y 0 (o` falso`) de lo contrario.
* Implementación:
`` `Python
Clase DirectedGraphmatrix:
def __init __ (self, num_nodes):
self.num_nodes =num_nodes
self.matrix =[[0] * num_nodes para _ en rango (num_nodes)]
def add_edge (self, from_node, to_node):
if 0 <=from_node
demás:
imprimir ("índices de nodo no válidos").
Def remove_edge (self, from_node, to_node):
if 0 <=from_node
demás:
imprimir ("índices de nodo no válidos").
def has_edge (self, from_node, to_node):
if 0 <=from_node
demás:
imprimir ("índices de nodo no válidos").
devolver falso
Def get_neighbors (self, nodo):
if 0 <=node
para i en rango (self.num_nodes):
if self.matrix [nodo] [i] ==1:
vecinos.append (i)
Vecinos de regreso
demás:
Imprimir ("Índice de nodo no válido").
devolver []
def __str __ (self):
return '\ n'.Join ([' '.Join (map (str, fila)) para fila en self.matrix])
# Uso de ejemplo:
gráfico gráfico =DirectedGraphMatrix (4) # con 4 nodos
Graph.Add_Edge (0, 1)
Graph.Add_Edge (0, 2)
Graph.Add_Edge (1, 3)
Imprimir (gráfico)
# Producción:
# 0 1 1 0
# 0 0 0 1
# 0 0 0 0
# 0 0 0 0
print (gráfico.has_edge (0, 1)) # Salida:Verdadero
print (gráfico.get_neighbors (0)) # Salida:[1, 2]
`` `` ``
* ventajas:
* Rápido para verificar si existe un borde (o (1)).
* Simple de implementar.
* Desventajas:
* Requiere predefinir el número de nodos. Se puede modificar para cambiar el tamaño dinámicamente, pero eso puede volverse costoso.
* Ineficiente para gráficos dispersos (desperdicia mucha memoria).
* Agregar/eliminar nodos puede ser costoso porque necesita cambiar el tamaño de toda la matriz.
3. Uso de una biblioteca de gráficos (por ejemplo, Networkx)
* Concepto: Aproveche las bibliotecas gráficas existentes que proporcionan implementaciones optimizadas y una gran cantidad de algoritmos gráficos. NetworkX es una opción popular.
* Implementación:
`` `Python
Importar Networkx como NX
# Crea un gráfico dirigido
gráfico =nx.digraph ()
# Agregar nodos
Graph.add_nodes_from (["A", "B", "C"])
# Agregar bordes
Graph.Add_Edge ("A", "B")
Graph.Add_Edge ("A", "C")
Graph.Add_Edge ("B", "C")
# Compruebe si existe un borde
print (gráfico.has_edge ("A", "B")) # Salida:Verdadero
# Consigue vecinos
print (list (list.successors ("a")) # salida:['b', 'c'] (sucesores =vecinos salientes)
# Retire un borde
Graph.Remove_EDGE ("A", "B")
print (gráfico.has_edge ("A", "B")) # Salida:Falso
# Eliminar un nodo
Graph.remove_node ("B")
print (gráfico.nodes ()) # Salida:['A', 'C']
# Puede dibujar el gráfico (requiere matplotlib)
# Importar matplotlib.pyplot como PLT
# nx.draw (gráfico, with_labels =true, node_color ="skyblue", node_size =1500, font_size =15)
# plt.show ()
`` `` ``
* ventajas:
* Biblioteca madura y bien probada.
* Proporciona un rico conjunto de algoritmos gráficos (ruta más corta, medidas de centralidad, etc.).
* Más fácil de realizar operaciones gráficas complejas.
* Admite la visualización de gráficos.
* Desventajas:
* Ligera sobrecarga en comparación con la implementación de su propia estructura gráfica.
* Requiere instalar una biblioteca externa.
Elegir la implementación correcta
* gráficos escasos: La lista de adyacencia es generalmente la mejor opción.
* gráficos densos: La matriz de adyacencia puede ser más rápida para las verificaciones de existencia de borde, pero consume más memoria. Considere las compensaciones.
* Operaciones de gráficos complejos: Use NetworkX u otra biblioteca de gráficos. Si necesita implementar algoritmos personalizados o está trabajando con gráficos muy grandes, es posible que desee utilizar la lista de adyacencia o los enfoques de matriz, pero tendrá que implementar los algoritmos usted mismo.
* tareas simples: Si solo necesita representación y transversal de gráficos básicos, la lista de adyacencia a menudo es suficiente.
Consideraciones clave:
* Uso de la memoria: Las listas de adyacencia son más eficientes en la memoria para gráficos dispersos. Las matrices de adyacencia pueden usar mucha memoria, especialmente para gráficos grandes y escasos.
* Rendimiento: Las matrices de adyacencia proporcionan una búsqueda de borde o (1), mientras que las listas de adyacencia requieren O (n) en el peor de los casos (donde n es el número de vecinos).
* Facilidad de uso: Las bibliotecas gráficas proporcionan una API más conveniente y rica en características.
* mutabilidad versus inmutabilidad: Decida si necesita modificar la estructura del gráfico con frecuencia. Las listas y matrices de adyacencia son mutables. Los gráficos de NetworkX también son mutables. Si necesita un gráfico inmutable, es posible que deba explorar estructuras de datos alternativas.
* Gráficos ponderados: Si necesita representar bordes ponderados, puede modificar la lista de adyacencia o la matriz para almacenar los pesos de los bordes. Por ejemplo, en la lista de adyacencias, puede almacenar un diccionario de `to_node:peso 'en lugar de solo una lista de nodos. Networkx tiene soporte incorporado para gráficos ponderados.
Antes de implementar un gráfico, considere cuidadosamente los requisitos de su problema específico para elegir la estructura y los algoritmos de datos más apropiados. En caso de duda, comience con la lista de adyacencias, ya que es una buena solución de propósito general. Si anticipa que necesita algoritmos gráficos más avanzados, la biblioteca NetworkX es a menudo una buena opción.