min_span_tree_visualizer
1.0.0
Проект C ++, чтобы визуализировать, как работают два наиболее распространенных алгоритма минимальных связующих деревьев (MST) - в основном Крускала и Прима. Приложение позволяет пользователю случайным образом генерировать структуру дерева или импортировать ее из файла, а затем выбирать, какой алгоритм использовать для поиска MST. Полезная функция воспроизведения реализована таким образом, чтобы пользователь мог визуально визуально визит шаг за шагом, как алгоритмы приходят к окончательному решению. Пользователь имеет возможность шаг за шагом пройти через процесс решения алгоритма или выбрать скорость воспроизведения и смотреть, как он работает, это волшебство.
Проект был вдохновлен следующими двумя видео на YouTube, которые, как мне показалось, было бы весело попробовать себя в C ++:
Анимация алгоритма Прима
Анимация алгоритма Крускала
В информатике график представляет собой набор узлов, которые соединены вместе по краям, которые имеют некоторое связанное с этим взвешивание. С практической точки зрения вес может дать преимущество между двумя узлами некоторым физическим значением, таким как расстояние в метрах, время в часах или стоимость в долларах. Дерево - это график без циклов. т.е.) построен таким образом, что не существует пути к краям, по которому можно следовать, который позволит вам вернуться в тот же узел, от которого вы оставили. Следовательно, охраняющее дерево является подграфом некоторых графиков, который «простирается» или соединяет все вершины графика. Это живое дерево также может быть «минимальным», охватившим дерево (MST), когда оно выбирается таким образом, чтобы выбрать ребра, которые имеют минимальный вес при суммировании. Оказывается, что MST довольно полезны во многих проблемах оптимизации, и на самом деле первый алгоритм MST был обнаружен при разработке сети электроэнергии для города Моравия. 1
В то время как первый алгоритм, который будет обнаружен для решения этой проблемы, был изобретен чешским математиком Отакар Борхвкой, сегодня два самых популярных алгоритма - это и Крускала, которые являются примерами жадных алгоритмов, которые работают немного по -разному.
Алгоритм PRIM-это жадный алгоритм, который строит MST One Edge за раз, изучая все исходящие края из некоторого стартового узла, и добавляя край с самым низким весом к MST. Таким образом, MST строится последовательно до тех пор, пока все края не будут изучены.
Точно так же, как алгоритм PRIM строит MST One Edge за раз, алгоритм Крускала также делает это, однако он делает это, начиная с ряда непересекающихся наборов ребра между узлами и последовательно соединяет наборы вместе по краям наименьшего веса, пока не появится только один оставшийся набор ребра, которые являются MST.
Алгоритм Чазель является почти линейным алгоритмом времени для поиска MST.
git clone репозиторий на местную машину.
Из корневого каталога запуска репозитория:
git clone https://github.com/Microsoft/vcpkg.git
После того, как это сделано, cd в папку VCPKG и запустите:
./bootstrap-vcpkg.sh
Наконец, беги:
./vcpkg integrate install
Запустите cd .. cd build , а затем запустите cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . Если все пойдет хорошо, вы увидите сообщение «Файлы сборки были записаны на ...». Теперь вы можете открыть сгенерированный проект 'Minimum_spanning_tree_visualizer'.
Чтобы запустить тесты, щелкните правой кнопкой мыши и «Выберите как стартап-проект»:
Чтобы запустить тесты, щелкните правой кнопкой мыши и «Выберите как стартап-проект»:
O jistém problému Minimálním (по определенной минимальной проблеме) ↩
