min_span_tree_visualizer
1.0.0
Un projet C ++ pour visualiser le fonctionnement de deux des algorithmes de l'arbre à portée minimum les plus courants (MST) - principalement des Kruskal et des Prim. L'application permet à l'utilisateur de générer de manière aléatoire une structure d'arbre ou d'en importer un à partir d'un fichier, puis de sélectionner quel algorithme à utiliser pour trouver le MST. La fonctionnalité de lecture utile est implémentée afin que l'utilisateur puisse voir visuellement étape par étape comment les algorithmes arrivent à la solution finale. L'utilisateur a la possibilité de parcourir le processus de résolution de l'algorithme étape par étape, ou de sélectionner une vitesse de lecture et de le regarder fonctionner sa magie.
Le projet a été inspiré par les deux vidéos YouTube suivantes, ce que je pensais être amusant d'essayer de me mettre en œuvre en C ++:
Animation de l'algorithme de Prim
Animation de l'algorithme de Kruskal
En informatique, un graphique est une collection de nœuds qui sont connectés ensemble par des bords, qui ont une pondération associée. En termes pratiques, un poids peut donner un avantage entre deux nœuds un sens physique tel que la distance en mètres, le temps en heures ou le coût en dollars. Un arbre est un graphique sans cycles. c'est-à-dire) construit de telle manière qu'il n'y a pas de chemin de bords qui peut être suivi qui vous permettra de revenir au même nœud que vous avez quitté. Un arbre couvrant est donc un sous-graphique d'un graphique qui "s'étend" ou se connecte, tous les sommets du graphique. Cet arbre couvrant peut également être un arbre couvrant «minimum» (MST) lorsqu'il est sélectionné de manière à sélectionner les bords qui ont un poids minimum lorsqu'ils sont additionnés. Il s'avère que les MST sont assez utiles dans de nombreux problèmes d'optimisation, et en fait, le premier algorithme MST a été découvert lors de la conception d'un réseau d'électricité pour la ville de Moravie. 1
Alors que le premier algorithme à être découvert pour résoudre ce problème a été inventé par le mathématicien tchèque Otakar Borůvka, les deux algorithmes les plus populaires aujourd'hui sont les primes et Kruskal qui sont des exemples d'algorithmes gourmands qui fonctionnent de manière légèrement différents.
L'algorithme de Prim est un algorithme gourmand qui construit le bord MST un à la fois en examinant tous les bords sortants à partir d'un nœud de départ et en ajoutant le bord avec le poids le plus bas au MST. De cette façon, le MST est construit successivement jusqu'à ce que tous les bords aient été explorés.
De la même manière que l'algorithme de Prim construit le MST One Edge à la fois, l'algorithme de Kruskal le fait également, mais il le fait en commençant par un certain nombre d'ensembles disjoints de bords entre les nœuds et rejoint successivement les ensembles ensemble par les bords du moins de poids jusqu'à ce qu'il n'y ait qu'un seul ensemble restant de bords qui est le MST.
L'algorithme de Chazelle est un algorithme de temps presque linéaire pour trouver un MST.
git clone le référentiel de votre machine locale.
à partir du répertoire racine du référentiel RUN:
git clone https://github.com/Microsoft/vcpkg.git
Une fois terminé, cd dans le dossier VCPKG et exécutez:
./bootstrap-vcpkg.sh
Enfin, courez:
./vcpkg integrate install
Exécutez cd .. cd build , puis exécutez cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . Si tout se passe bien, vous verrez le message "Build Files a été écrit sur ...". Vous pouvez maintenant ouvrir le projet «minimum_spanning_tree_visualizer» généré.
Pour exécuter les tests, cliquez avec le bouton droit et "Sélectionnez comme projet de démarrage":
Pour exécuter les tests, cliquez avec le bouton droit et "Sélectionnez comme projet de démarrage":
O jistém problému minimálním (sur un certain problème minimal) ↩
