quiero implementar el algoritmo de Kruskal en python, ¿cómo puedo representar el árbol/gráfico y qué enfoque debo seguir para detectar los ciclos?cómo representar gráficos/árboles en python y cómo detectar ciclos?
La forma más sencilla de representar a ella (en mi opinión) es mediante el uso de un diccionario de matrices Listas:
graph = {}
graph[node_id] = [other_node_id for other_node_id in neighbors(node_id)]
Una forma sencilla de encontrar ciclos es mediante el uso de una BF o búsqueda DF:
def df(node):
if visited(node):
pass # found a cycle here, do something with it
visit(node)
[df(node_id) for node_id in graph[node]]
Descargo de responsabilidad: se trata en realidad de un boceto; neighbors(), visited() y visit() son simplemente tontos para representar cómo debería ser el algoritmo.
Python Graph API es un buen lugar para comenzar.
Por ejemplo, NetworkX tiene una implementación de algoritmo de Kruskal para encontrar el árbol de expansión mínimo.
Si desea reinventar la rueda y hacerlo usted mismo, también es posible.
sí, estoy tratando de reinventar la rueda al menos esta primera vez. –
por diccionario de matrices u significa diccionario de listas? –
@Bunny Rabbit erm .. sí. Lo siento, he usado mal el nombre>< –