python - recubrimiento - arbol de peso minimo
Implementación de todos los árboles de expansión mínima. (4)
He estado buscando una implementación (estoy usando networkx library) que encontrará todos los árboles de expansión mínimos (MST) de un gráfico ponderado no dirigido.
Solo puedo encontrar implementaciones para el algoritmo de Kruskal y el algoritmo de Prim, los cuales solo devolverán un MST único.
He visto artículos que abordan este problema (como Representar todos los árboles de expansión mínima con aplicaciones para conteo y generación ) pero mi cabeza tiende a explotar de alguna manera al tratar de pensar cómo traducirlo a código.
De hecho, no he podido encontrar una implementación en ningún idioma.
No sé si esta es la solución, pero es una solución (diría que es la versión gráfica de una fuerza bruta):
- Encuentra el MST de la gráfica usando el algoritmo de kruskal o prim. Esto debería ser O (E log V).
- Generar todos los árboles que se extienden. Esto se puede hacer en
O(Elog(V) + V + n) for n = number of spanning trees, según entiendo que desde el valor de 2 minutos de Google, posiblemente se puede mejorar. - Filtre la lista generada en el paso # 2 porque el peso del árbol es igual al peso de la MST. Este debe ser O (n) para n como el número de árboles generados en el paso # 2.
Nota: ¡Haz esto perezosamente! Generar todos los árboles posibles y luego filtrar los resultados tomará memoria O (V ^ 2), y los requisitos de espacio polinómico son malos: genere un árbol, examine su peso, si es un MST, agréguelo a una lista de resultados, si no, descártelos .
Complejidad de tiempo global: O(Elog(V) + V + n) for G(V,E) with n spanning trees
Puedes encontrar una idea en el trabajo de Sorensen y Janssens (2005) .
La idea es generar los ST en el orden creciente, y tan pronto como obtenga el valor mayor de ST, detenga la enumeración.
Ronald Rivest tiene una buena implementación en Python, mst.py
Rubys da una buena respuesta general. Pero escribir código eficiente para generar todos los árboles que se extienden en una gráfica es una bestia de desafío.
En la mitad de esta página , alrededor de diciembre de 2003, encontrará una implementación CWEB del algoritmo de Knuth que encuentra todos los árboles de expansión de un gráfico determinado.