Estoy seguro de que hay bibliotecas de terceros disponibles para gráficos en python. NetworkX viene a la mente. Yo personalmente sugiero los gráficos de implementación de OP al menos una vez como ejercicio. También sugiero implementar algunos métodos comunes como el algoritmo de Dijkstra, la búsqueda de profundidad primero, la búsqueda de amplitud primero y la clasificación topológica.
¿Cuáles son los métodos para hacerlo? Primero debe decidir cómo representar la gráfica. Hay dos formas comunes:
Lista de adyacencia
- ¿Por qué se le dio al F-117 Nighthawk un prefijo F?
- ¿La codificación está relacionada con las matemáticas?
- ¿Cómo se puede encontrar el logaritmo de base 10 de un número de hasta 5 decimales con solo usar las cuatro operaciones básicas (+, -, *, /) con la ayuda de una calculadora?
- Cómo encontrar la suma de todos los números distintos cuyo MCM es N
- ¿Cómo se usa la teoría de juegos en la IA?
Para este gráfico, tendríamos un conjunto de listas vinculadas para cada vértice, indicando los otros nodos a los que está conectado.
A B C}
B: {A, C}
TAXI}
Matriz de adyacencia
Para el mismo gráfico, ahora tenemos una matriz bidimensional de entradas [math] V ^ {2} [/ math], donde cada entrada es un valor booleano que indica si un nodo está conectado a otro.
{{0, 1, 1},
{1, 0, 1},
{1, 1, 0}}
Puede pensar que las listas de adyacencia siempre son mejores, pero eso depende en gran medida del tipo de gráfico. Los gráficos densos son cuando la mayoría de los nodos están conectados entre sí. Los gráficos dispersos son lo opuesto, cuando la mayoría de los nodos no tienen conexiones con otros. Para gráficos dispersos, las listas de adyacencia superan en gran medida a las matrices de adyacencia, pero las matrices son las ganadoras de los gráficos densos. El problema principal es la complejidad del espacio frente a la complejidad del tiempo para acceder a los miembros. En una lista de adyacencia, averiguar si el nodo A está conectado a cualquier otro nodo es [matemático] O (grado (A)) [/ matemático] tiempo. Es el tiempo [matemático] O (1) [/ matemático] para una matriz de adyacencia. Sin embargo, las listas de adyacencia tienen un uso de espacio considerablemente menor. Para más discusión sobre esto, visite la página de wikipedia. Lista de adyacencia
Graphs en Python proporciona una buena implementación usando un diccionario, pero sugiero probar una de las dos opciones anteriores por su cuenta para obtener una mejor comprensión. Los gráficos son muy fáciles de implementar, pero la elección de la construcción depende de las necesidades del usuario.
Lo bueno de los gráficos es que, independientemente de la implementación, los métodos importantes casi siempre tienen el mismo aspecto. Los gráficos básicos en python son realmente una traducción línea por línea del pseudocódigo. Aquí hay un ejemplo con la búsqueda de profundidad primero:
Pseudocódigo:
procedimiento DFS-iterativo (G, v):
deja que S sea una pila
S.push (v)
mientras que S no está vacío
v = S.pop ()
si v no está etiquetado como descubierto:
etiqueta v como descubierta
para todos los bordes de v a w en G.ad adyacentesEdges (v) do
S.push (w)
Cosa real:
def dfs (gráfico, inicio):
visitado, stack = set (), [inicio]
mientras que la pila:
vértice = stack.pop ()
si el vértice no está en visitado:
visitado.add (vértice)
stack.extend (gráfico [vértice] – visitado)
volver visitado
# crédito a: http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
Ahora haga esto con la implementación gráfica real, luego pase a paquetes como NetworkX.
