Perbezaan Antara Kruskal dan Prim: Kruskal vs Prim

< Kruskal vs Prim

Dalam sains komputer, algoritma Prim dan Kruskal adalah algoritma tamak yang mendapati pokok merentang minimum untuk graf yang tidak diarahkan secara berikat. Pohon yang merentang adalah subgraph graf supaya setiap nod graf dihubungkan dengan jalan, iaitu pokok. Setiap pokok merangkumi mempunyai berat badan, dan berat minimum / kos yang mungkin untuk semua pokok merangkumi adalah pokok merentang minimum (MST).

Lebih lanjut mengenai Algoritma Prim

Algoritma ini dibangunkan oleh ahli matematik Czech Vojtěch Jarník pada tahun 1930 dan kemudiannya 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 n nod dan berat masing-masing tepi, 1. Pilih nod sewenang-wenang dari graf dan tambahkannya ke pokok T (yang akan menjadi nod pertama)

2. Pertimbangkan berat setiap kelebihan yang disambungkan ke nod dalam pokok itu dan pilih minimum. Tambahkan tepi dan nod pada hujung lain pokok T dan keluarkan tepi dari graf. (Pilih mana-mana sekiranya terdapat dua atau lebih minimum)

3. Ulang langkah 2, sehingga n-1 tepi ditambahkan ke pokok.

Dalam kaedah ini, pokok itu bermula dengan nod tunggal sewenang-wenangnya dan mengembang dari nod tersebut seterusnya dengan setiap kitaran. Oleh itu, untuk algoritma berfungsi dengan baik, graf itu perlu menjadi graf yang bersambung. Bentuk dasar algoritma Prim mempunyai kerumitan masa O (V

2 ^).

Lebih lanjut mengenai Algoritma Kruskal

Algoritma yang dibangunkan oleh Joseph Kruskal muncul dalam prosiding Persatuan Matematik Amerika pada tahun 1956. Algoritma Kruskal juga dapat dinyatakan dalam tiga langkah mudah.

Memandangkan graf dengan n nod dan berat masing-masing setiap tepi, 1. Pilih arka dengan berat badan yang paling kurang dari keseluruhan graf dan tambahkan pada pokok itu dan padamkan dari graf.

2. Baki selebihnya pilih pinggiran tertimbang, dengan cara yang tidak membentuk kitaran. Tambah tepi ke pokok dan padamkan dari graf. (Pilih mana-mana sekiranya terdapat dua atau lebih minimum)

3. Ulangi proses dalam langkah 2.

Dalam kaedah ini, algoritma bermula dengan kelebihan berat sebelah dan terus memilih setiap tepi pada setiap kitaran. Oleh itu, dalam algoritma grafik tidak perlu disambungkan. Algoritma Kruskal mempunyai kerumitan masa O (logV)

Apakah perbezaan antara Algoritma Kruskal dan Prim?

• Algoritma Prim memulakan dengan nod, sedangkan algoritma Kruskal bermula dengan kelebihan.

• Algoritma Prim berpanjangan dari satu simpul ke yang lain manakala algoritma Kruskal memilih tepi dengan cara kedudukan kedudukan tidak berdasarkan pada langkah terakhir.

• Dalam algoritma primitif, graf mestilah graf bersambung sementara fungsi Kruskal boleh berfungsi pada graf yang tidak terputus juga.

• Algoritma Prim mempunyai kerumitan masa O (V

2 ^{), dan kerumitan masa Kruskal adalah O (logV).}