El mínimo más rápido algoritmo de árbol de expansión

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

estoy buscando a mi punto de referencia expansión mínima algoritmo de árbol contra el mejor de los mejores. ¿Alguien sabe dónde puedo encontrar una implementación en C++ de estos algoritmos? Busqué y busqué en Google y no encontré nada. Si estos algoritmos son los mejores, seguramente debe haber una implementación de C++ en alguna parte.

El mínimo más rápido árbol de expansión algoritmo hasta la fecha ha sido desarrollado por David Karger, Philip Klein, y Robert Tarjan, que encontró un tiempo lineal algoritmo aleatorio basado en una combinación del algoritmo de Borůvka y la inversa -delete algoritmo. [2] [3] El algoritmo no aleatorio más rápido, por Bernard Chazelle, se basa en el montón dinámico , una cola de prioridad aproximada . [4] [5] Su tiempo de ejecución es O (m α (m, n)), donde m es el número de bordes, n es el número de vértices y α es el inverso funcional clásico de la función Ackermann. La función α crece extremadamente despacio, por lo que que para todos los fines prácticos puede considerarse una constante no mayor que 4; por lo tanto, el algoritmo de Chazelle toma muy cerca del tiempo lineal. Si los pesos de borde son enteros con una longitud de bit limitada , entonces se conocen los algoritmos determinísticos con el tiempo de ejecución lineal . [6] Si existe un algoritmo determinista con lineal tiempo de ejecución para pesos generales es sigue siendo una pregunta abierta. Sin embargo, Seth Petie y Vijaya Ramachandran han encontrado encontrado un algoritmo de árbol de expansión mínimo determinantemente óptimo, la complejidad computacional de la cual es desconocido. [7]

Ya probé con los algoritmos de gráfico de Boost C++.

Answer 1

Cuando la página de Wikipedia dice "el algoritmo de árbol de expansión mínimo más rápido", lo que quieren decir es el algoritmo con los límites asintóticos más bajos, en este caso, O (m α (m, n)), con m, n y α definido como en la cita que pegó. En pocas palabras, esto significa que para valores de entrada muy grandes, la cantidad de tiempo siempre estará limitada por C * m * α (m, n), para algún valor de C. Pero tenga en cuenta que C podría ser muy grande, es decir, , este algoritmo podría ser más lento que otros cuando se aplica a valores de entrada más pequeños, aunque es más rápido que otros para valores de entrada muy grandes.

Cuando se comparan los límites asintóticos de dos algoritmos, no hay "pruebas" para ver cuál es más rápido: se comprueban los límites asintóticos de cada algoritmo y se ve cuál es el más bajo. ("Asintótica" se refiere al comportamiento que el tamaño de entrada tiende a infinito - y es difícil de realizar pruebas con valores de entrada infinita de tamaño.)

Pero tenga en cuenta que hay casos en los que debe no utilizar el asintóticamente algoritmo más rápido. Si la "C" es muy grande, entonces sería mejor usar un algoritmo más simple para valores de datos más pequeños.

Supongo que su algoritmo puede mejorar en la C, pero no en los límites asintóticos. ¡Pero si me equivoco al respecto, entonces debe enviarlo a ACM!

Para obtener más información, consulte: http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf "En Clasificación, montones, y mínimo Spanning Trees", Gonzalo Navarro y Rodrigo Paredes

presenta algunas de las "mejores de las mejores" medidas de memoria internas y externas , y da referencias a las implementaciones más antiguas de .

Informan # de E/S y el tiempo de CPU en función del tamaño de gráfica, y describir bien sus casos de prueba, por lo que, en principio, que podría hacer las pruebas y comparar con sus gráficos publicados. Puede usar su referencia Prim2 (código de Peter Sanders, quien hace que muchos de sus códigos rápidos estén disponibles gratuitamente) para calibrar sus propias medidas.