min_span_tree_visualizer
1.0.0
Ein C ++ - Projekt zur Visualisierung, wie zwei der häufigsten Algorithmen mit minimalem Spanning Tree (MST) - hauptsächlich Kruskals und Prims funktionieren. Mit der Anwendung kann der Benutzer zufällig eine Baumstruktur generieren oder eine aus einer Datei importieren und dann auswählen, welchen Algorithmus die MST ermittelt werden soll. Hilfreiche Wiedergabefunktionen werden implementiert, damit der Benutzer Schritt für Schritt visuell erkennen kann, wie die Algorithmen zur endgültigen Lösung gelangen. Der Benutzer hat die Möglichkeit, Schritt für Schritt den Algorithmus -Lösungsprozess durchzusetzen oder eine Wiedergabegeschwindigkeit auszuwählen und zu beobachten, wie er funktioniert.
Das Projekt wurde von den folgenden zwei YouTube -Videos inspiriert, von denen ich dachte, dass sie Spaß machen würden, mich in C ++ zu implementieren:
Prims Algorithmusanimation
Kruskals Algorithmusanimation
In der Informatik ist eine Grafik eine Sammlung von Knoten, die durch Kanten miteinander verbunden sind, die eine gewisse Gewichtung aufweisen. In praktischer Hinsicht kann ein Gewicht die Kante zwischen zwei Knoten eine körperliche Bedeutung wie Entfernung in Messgeräten, Zeitzeiten oder Kosten in Dollar geben. Ein Baum ist ein Diagramm ohne Zyklen. dh) so konstruiert, dass es keinen Weg von Kanten gibt, die befolgt werden können, die es Ihnen ermöglichen, wieder zu demselben Knoten zurückzukehren, von dem Sie gelassen haben. Ein Spanning -Baum ist daher ein Untergraphen eines Diagramms, das alle Scheitelpunkte des Diagramms "überspannt" oder verbindet. Dieser Spanning -Baum kann auch ein "minimaler" Spanning Tree (MST) sein, wenn er so ausgewählt wird, dass diese im summierten Summieren ein Mindestgewicht ausgewählt haben. Es stellt sich heraus, dass MSTs bei vielen Optimierungsproblemen ziemlich nützlich sind, und in der Tat wurde der erste MST -Algorithmus bei der Gestaltung eines Stromnetzes für die Stadt Moravia entdeckt. 1
Während der erste Algorithmus, der für die Lösung dieses Problems entdeckt wurde, von tschechischem Mathematiker Otakar Borůvka erfunden wurde, sind die beiden beliebtesten Algorithmen heute Prims und Kruskals, die Beispiele für gierige Algorithmen sind, die auf leicht unterschiedliche Weise arbeiten.
Der Algorithmus von Prim ist ein gieriger Algorithmus, der die MST-Rand nacheinander konstruiert, indem alle ausgehenden Kanten von einem Startknoten untersucht und die Kante mit dem niedrigsten Gewicht zum MST hinzugefügt werden. Auf diese Weise wird der MST nacheinander aufgebaut, bis alle Kanten untersucht wurden.
Ebenso wie der Algorithmus von Prim den MST -Rand nacheinander baut, beginnt der Algorithmus von Kruskal auch dies, indem er mit einer Reihe von disjunkten Kanten zwischen Knoten und nacheinander mit einer Reihe von Disjunkt -Kanten beginnt und die Sätze nacheinander mit den Kanten mit dem geringsten Gewicht verbinden, bis nur eine verbleibende Menge von Kanten vorhanden ist.
Chazelles Algorithmus ist ein fast linearer Zeitalgorithmus zum Auffinden eines MST.
git clone das Repository in Ihre lokale Maschine.
Aus dem Stammverzeichnis des Repository -Laufs:
git clone https://github.com/Microsoft/vcpkg.git
Sobald Sie fertig sind, cd zum vcpkg -Ordner und ausführen:
./bootstrap-vcpkg.sh
Endlich rennen:
./vcpkg integrate install
Führen Sie cd .. cd build und dann cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . Wenn alles gut läuft, sehen Sie, dass die Nachricht "Erstellen Dateien geschrieben wurden". Sie können jetzt das Projekt "minimum_spanning_tree_visualizer" öffnen.
Um die Tests auszuführen, klicken Sie mit der rechten Maustaste und "Wählen Sie als Startprojekt aus":
Um die Tests auszuführen, klicken Sie mit der rechten Maustaste und "Wählen Sie als Startprojekt aus":
O Jistém problému minimalním (zu einem bestimmten minimalen Problem) ↩
