Perbezaan antara Kruskal dan Prim
Kruskal vs Prim
Dalam Sains Komputer, algoritma Prim dan Kruskal adalah algoritma tamak yang mendapati pokok merangkumi minimum untuk graf yang tidak diarahkan berwajaran yang disambungkan. Pokok yang merangkumi adalah subgraph graf sehingga setiap nod graf disambungkan oleh jalan, yang merupakan pokok. Setiap pokok yang merangkumi mempunyai berat badan, dan berat badan/kos minimum semua pokok yang merangkumi adalah pokok minimum (MST).
Lebih banyak mengenai algoritma Prim
Algoritma ini dibangunkan oleh ahli matematik Czech Vojtěch Jarník pada tahun 1930 dan kemudian secara bebas oleh saintis komputer Robert C. Prim pada tahun 1957. Ia ditemui semula oleh Edsger Dijkstra pada tahun 1959. Algoritma boleh dinyatakan dalam tiga langkah utama;
Memandangkan graf yang disambungkan dengan nod N dan berat masing -masing dari setiap kelebihan,
1. Pilih nod sewenang -wenang dari graf dan masukkannya ke pokok T (yang akan menjadi nod pertama)
2. Pertimbangkan berat setiap kelebihan yang disambungkan ke nod di dalam pokok dan pilih minimum. Tambahkan tepi dan nod di hujung pokok T dan keluarkan tepi dari graf. (Pilih mana -mana jika dua atau lebih minimum wujud)
3. Ulangi langkah 2, sehingga tepi N-1 ditambah ke pokok.
Dalam kaedah ini, pokok bermula dengan nod sewenang -wenangnya dan mengembang dari nod itu dan seterusnya dengan setiap kitaran. Oleh itu, untuk algoritma berfungsi dengan betul, grafik perlu menjadi graf yang disambungkan. Bentuk asas algoritma prim mempunyai kerumitan masa O (v2).
Lebih lanjut mengenai algoritma Kruskal
Algoritma yang dibangunkan oleh Joseph Kruskal muncul dalam Prosiding Persatuan Matematik Amerika pada tahun 1956. Algoritma Kruskal juga boleh dinyatakan dalam tiga langkah mudah.
Memandangkan graf dengan nod N dan berat masing -masing dari setiap kelebihan,
1. Pilih arka dengan berat badan paling sedikit keseluruhan dan tambahkan ke pokok dan padamkan dari graf.
2. Baki pilih kelebihan berwajaran paling kurang, dengan cara yang tidak membentuk kitaran. Tambahkan tepi ke pokok dan padamkan dari graf. (Pilih mana -mana jika dua atau lebih minimum wujud)
3. Ulangi proses dalam langkah 2.
Dalam kaedah ini, algoritma bermula dengan kelebihan berwajaran paling rendah dan terus memilih setiap kelebihan pada setiap kitaran. Oleh itu, dalam algoritma graf tidak perlu disambungkan. Algoritma Kruskal mempunyai kerumitan masa O (LOGV)
Apakah perbezaan antara algoritma Kruskal dan Prim?
• Algoritma Prim dimulakan dengan nod, sedangkan algoritma Kruskal bermula dengan kelebihan.
• Algoritma Prim dari satu nod ke nod yang lain manakala algoritma Kruskal memilih tepi dengan cara kedudukan tepi tidak berdasarkan langkah terakhir.
• Dalam algoritma Prim, graf mesti menjadi graf yang disambungkan manakala Kruskal boleh berfungsi pada graf yang terputus juga.
• Algoritma Prim mempunyai kerumitan masa O (v2), dan kerumitan masa Kruskal adalah o (logv).
