min_span_tree_visualizer
1.0.0
가장 일반적인 최소 스패닝 트리 (MST) 알고리즘 (주로 Kruskal과 Prim)의 작동 방식을 시각화하는 C ++ 프로젝트. 응용 프로그램을 통해 사용자는 트리 구조를 무작위로 생성하거나 파일에서 하나를 가져온 다음 MST를 찾는 데 사용할 알고리즘을 선택할 수 있습니다. 유용한 재생 기능이 구현되어 사용자가 알고리즘이 최종 솔루션에 도달하는 방법을 단계별로 시각적으로 볼 수 있습니다. 사용자는 과정을 단계별로 해결하거나 재생 속도를 선택하고 Magic의 작동을 볼 수 있습니다.
이 프로젝트는 다음 두 개의 YouTube 비디오에서 영감을 얻었습니다. C ++에서 나 자신을 구현하는 것이 재미있을 것이라고 생각했습니다.
Prim의 알고리즘 애니메이션
Kruskal의 알고리즘 애니메이션
컴퓨터 과학에서 그래프는 가장자리로 연결된 노드 모음이며, 일부 관련 가중치가 있습니다. 실용적으로 무게는 두 노드 사이의 가장자리에 미터 거리, 시간 시간 또는 비용과 같은 물리적 의미를 줄 수 있습니다. 나무는 사이클이없는 그래프입니다. 즉) 팔로우 할 수있는 경로가 없도록 구성되어있어 남은 동일한 노드에 다시 도착할 수 있습니다. 따라서 스패닝 트리는 그래프의 모든 정점을 "스파링"하거나 연결하는 일부 그래프의 하위 그래프입니다. 이 스패닝 트리는 합산시 최소 무게를 선택하는 가장자리를 선택하는 방식으로 선택할 때 '최소'스패닝 트리 (MST) 일 수도 있습니다. MST는 많은 최적화 문제에 매우 유용하며 실제로 Moravia시를위한 전기 네트워크를 설계하는 동안 첫 번째 MST 알고리즘이 발견되었습니다. 1
이 문제를 해결하기 위해 발견 된 첫 번째 알고리즘은 체코 수학자 인 Otakar Borůvka에 의해 발명되었지만, 오늘날 가장 인기있는 두 가지 알고리즘은 Prim과 Kruskal 's입니다.
Prim의 알고리즘은 일부 시작 노드에서 나가는 모든 모서리를 검사하고 MST에 무게가 가장 낮은 모서리를 추가하여 한 번에 한 번에 MST One Edge를 구성하는 탐욕스러운 알코리즘입니다. 이러한 방식으로 MST는 모든 모서리가 탐색 될 때까지 연속적으로 구축됩니다.
Prim의 알고리즘이 한 번에 MST One Edge를 구축하는 것과 마찬가지로 Kruskal의 알고리즘도 마찬가지이지만, 노드 사이의 많은 분리 된 가장자리 세트로 시작하여 MST 인 가장자리가 남아있을 때까지 최소 무게의 가장자리로 세트를 연속적으로 결합하여 시작합니다.
Chazelle의 알고리즘은 MST를 찾기위한 거의 선형 시간 알고리즘입니다.
git clone .
저장소 실행의 루트 디렉토리에서 :
git clone https://github.com/Microsoft/vcpkg.git
완료되면 VCPKG 폴더로 cd 수행하고 실행하십시오.
./bootstrap-vcpkg.sh
마지막으로, 실행 :
./vcpkg integrate install
cd .. cd build 실행 한 다음 cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . 모든 것이 잘 진행되면 "빌드 파일이 작성되었습니다 ..."메시지가 표시됩니다. 이제 생성 된 '최소_spanning_tree_visualizer'프로젝트를 열 수 있습니다.
테스트를 실행하려면 마우스 오른쪽 버튼을 클릭하고 "시작 프로젝트 선택":
테스트를 실행하려면 마우스 오른쪽 버튼을 클릭하고 "시작 프로젝트 선택":
o Jistém Problému Minimálním (특정 최소 문제에) ↩
