min_span_tree_visualizer
1.0.0
Proyek C ++ untuk memvisualisasikan bagaimana dua algoritma spanning tree minimum (MST) yang paling umum bekerja - terutama Kruskal dan Prim. Aplikasi memungkinkan pengguna untuk secara acak menghasilkan struktur pohon atau mengimpor satu dari file, dan kemudian pilih algoritma mana yang digunakan untuk menemukan MST. Fungsi pemutaran yang bermanfaat diimplementasikan sehingga pengguna dapat secara visual melihat langkah demi langkah bagaimana algoritma tiba di solusi akhir. Pengguna memiliki kemampuan untuk melangkah melalui proses pemecahan algoritma langkah demi langkah, atau memilih kecepatan pemutaran dan menontonnya berfungsi sebagai ajaib.
Proyek ini terinspirasi oleh dua video YouTube berikut, yang saya pikir akan menyenangkan untuk mencoba menerapkan diri saya di C ++:
Animasi Algoritma Prim
Animasi algoritma Kruskal
Dalam ilmu komputer, grafik adalah kumpulan node yang dihubungkan bersama oleh tepi, yang memiliki beberapa bobot terkait. Dalam istilah praktis, berat mungkin memberikan keunggulan antara dua node beberapa makna fisik seperti jarak dalam meter, waktu dalam jam atau biaya dalam dolar. Pohon adalah grafik tanpa siklus. yaitu) dibangun sedemikian rupa sehingga tidak ada jalur tepi yang dapat diikuti yang akan memungkinkan Anda untuk kembali pada simpul yang sama dengan yang Anda tinggalkan. Oleh karena itu, spanning tree adalah subgraph dari beberapa grafik yang "membentang", atau menghubungkan, semua simpul grafik. Pohon spaning ini juga bisa menjadi pohon spanning 'minimum' (MST) ketika dipilih sedemikian rupa untuk memilih tepi yang memiliki bobot minimum saat dijumlahkan. Ternyata MST cukup berguna dalam banyak masalah optimasi, dan pada kenyataannya algoritma MST pertama ditemukan saat merancang jaringan listrik untuk kota Moravia. 1
Sementara algoritma pertama yang ditemukan untuk menyelesaikan masalah ini ditemukan oleh ahli matematika Ceko Otakar Borůvka, dua algoritma paling populer saat ini adalah Prim dan Kruskal yang merupakan contoh dari algoritma serakah yang bekerja dengan cara yang sedikit berbeda.
Algoritma Prim adalah algoritma serakah yang membangun MST satu tepi pada satu waktu dengan memeriksa semua tepi keluar dari beberapa simpul awal, dan menambahkan tepi dengan bobot terendah ke MST. Dengan cara ini MST dibangun secara berturut -turut sampai semua tepi telah dieksplorasi.
Dengan cara yang sama seperti algoritma Prim membangun MST satu tepi pada satu waktu, algoritma Kruskal juga melakukannya, namun ia melakukannya dengan memulai dengan sejumlah set tepi terpisah antara node dan berturut -turut bergabung dengan set bersama oleh tepi yang paling tidak ada hingga hanya ada satu set tepi yang tersisa yang merupakan MST.
Algoritma Chazelle adalah algoritma waktu yang hampir linier untuk menemukan MST.
git clone repositori ke mesin lokal Anda.
Dari direktori root dari Run Run:
git clone https://github.com/Microsoft/vcpkg.git
Setelah selesai, cd ke folder VCPKG dan jalankan:
./bootstrap-vcpkg.sh
Akhirnya, jalankan:
./vcpkg integrate install
Jalankan cd .. cd build dan kemudian jalankan cmake .. -DCMAKE_TOOLCHAIN_FILE=vcpkg/scripts/buildsystems/vcpkg.cmake . Jika semuanya berjalan dengan baik, Anda akan melihat pesan "Bangun telah ditulis ke ...". Anda sekarang dapat membuka proyek 'minimum_spanning_tree_visualizer' yang dihasilkan.
Untuk menjalankan tes, klik kanan dan "SELECT as Startup Project":
Untuk menjalankan tes, klik kanan dan "SELECT as Startup Project":
O jistém problému minimálním (pada masalah minimal tertentu) ↩
