min_span_tree_visualizer
1.0.0
Un proyecto C ++ para visualizar cómo funcionan dos de los algoritmos de árbol mínimo más comunes (MST), principalmente Kruskal y Prim. La aplicación permite al usuario generar aleatoriamente una estructura de árbol o importar uno de un archivo, y luego seleccione qué algoritmo usar para encontrar el MST. Se implementa una funcionalidad de reproducción útil para que el usuario pueda ver visualmente paso a paso cómo llegan los algoritmos a la solución final. El usuario tiene la capacidad de atravesar el proceso de resolución de algoritmos paso a paso, o seleccionar una velocidad de reproducción y verlo funcionar es mágico.
El proyecto se inspiró en los siguientes dos videos de YouTube, que pensé que sería divertido intentar implementarme en C ++:
Animación del algoritmo de Prim
Animación del algoritmo de Kruskal
En informática, un gráfico es una colección de nodos que están conectados juntos por bordes, que tienen alguna ponderación asociada. En términos prácticos, un peso podría darle a la ventaja entre dos nodos un significado físico, como la distancia en metros, tiempo en horas o costo en dólares. Un árbol es un gráfico sin ciclos. es decir) construido de tal manera que no haya ruta de bordes que se puedan seguir, lo que le permitirá regresar al mismo nodo desde el que dejó. Por lo tanto, un árbol de expansión es una subgraph de algún gráfico que "abarca", o conecta, todos los vértices del gráfico. Este árbol de expansión también puede ser un árbol de expansión 'mínimo' (MST) cuando se selecciona de tal manera que seleccione bordes que tengan un peso mínimo cuando se sumen. Resulta que los MST son bastante útiles en muchos problemas de optimización, y en realidad se descubrió el primer algoritmo MST mientras diseñaba una red eléctrica para la ciudad de Moravia. 1
Mientras que el primer algoritmo que se descubre para resolver este problema fue inventado por el matemático checo Otakar Borůvka, los dos algoritmos más populares hoy en día son Prim's y Kruskal, que son ejemplos de algoritmos codiciosos que funcionan de manera ligeramente diferente.
El algoritmo de Prim es un algoritmo codicioso que construye el MST un borde a la vez examinando todos los bordes salientes desde algún nodo inicial y agregando el borde con el peso más bajo al MST. De esta manera, el MST se construye sucesivamente hasta que se hayan explorado todos los bordes.
De la misma manera que el algoritmo de Prim construye el MST One Edge a la vez, el algoritmo de Kruskal también lo hace, sin embargo, lo hace comenzando con una serie de conjuntos de desarches de bordes entre nodos y se unen sucesivamente los conjuntos por bordes de menor peso hasta que solo hay un conjunto de bordes que es el MST.
El algoritmo de Chazelle es un algoritmo de tiempo casi lineal para encontrar un MST.
git clone el repositorio a su máquina local.
Desde el directorio raíz de la ejecución del repositorio:
git clone https://github.com/Microsoft/vcpkg.git
Una vez hecho, cd a la carpeta VCPKG y ejecute:
./bootstrap-vcpkg.sh
Finalmente, corre:
./vcpkg integrate install
Ejecute cd .. cd build y luego ejecute cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . Si todo va bien, verá que el mensaje "Build Arches se ha escrito en ...". Ahora puede abrir el proyecto generado 'Minimum_spanning_tree_Visualizer'.
Para ejecutar las pruebas, haga clic con el botón derecho y "seleccione como proyecto de inicio":
Para ejecutar las pruebas, haga clic con el botón derecho y "seleccione como proyecto de inicio":
O Jistém Problému Minimálnim (en un cierto problema mínimo) ↩
