Perbezaan Antara Kruskal Dan Prim

2024 Pengarang: Mildred Bawerman | [email protected]. Diubah suai terakhir: 2023-12-16 08:40

Kruskal vs Prim

Dalam sains komputer, algoritma Prim dan Kruskal adalah algoritma tamak yang mencari pokok rentang minimum untuk graf tak tentu yang berwajaran bersambung. Pohon rentang adalah subgraf grafik sehingga setiap simpul grafik dihubungkan oleh jalan, yang merupakan pokok. Setiap pokok rentang mempunyai berat, dan bobot / biaya minimum yang mungkin untuk semua pokok rentang adalah pokok rentang minimum (MST).

Lebih lanjut mengenai Algoritma Prim

Algoritma ini dikembangkan 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 tersebut dapat dinyatakan dalam tiga langkah utama;

Memandangkan graf bersambung dengan node dan berat masing-masing tepi, 1. Pilih simpul sewenang-wenang dari grafik dan tambahkannya ke pokok T (yang akan menjadi nod pertama)

2. Pertimbangkan berat setiap tepi yang dihubungkan dengan nod di pokok dan pilih minimum. Tambahkan tepi dan simpul di hujung pokok T yang lain dan lepaskan tepi dari graf. (Pilih mana-mana jika ada dua atau lebih minimum)

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

Dalam kaedah ini, pokok bermula dengan satu simpul sewenang-wenangnya dan berkembang dari simpul itu dan seterusnya dengan setiap kitaran. Oleh itu, agar algoritma berfungsi dengan betul, graf perlu menjadi grafik yang bersambung. Bentuk asas algoritma Prim mempunyai kerumitan masa O (V ²).

Lebih lanjut mengenai Algoritma Kruskal

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

Diberi graf dengan n simpul dan berat masing-masing tepi, 1. Pilih lengkok dengan berat paling sedikit keseluruhan graf dan tambahkan ke pokok dan padam dari graf.

2. Dari yang selebihnya pilih tepi yang paling tidak berwajaran, dengan cara yang tidak membentuk kitaran. Tambahkan tepi ke pokok dan hapus dari grafik. (Pilih mana-mana jika ada dua atau lebih minimum)

3. Ulangi proses pada langkah 2.

Dalam kaedah ini, algoritma dimulakan dengan kelebihan paling sedikit dan terus memilih setiap tepi pada setiap kitaran. Oleh itu, dalam algoritma grafik tidak perlu dihubungkan. Algoritma Kruskal mempunyai kerumitan masa O (logV)

Apakah perbezaan antara Algoritma Kruskal dan Prim?

• Algoritma Prim inisialisasi dengan simpul, sedangkan algoritma Kruskal bermula dengan kelebihan.

• Algoritma Prim merangkumi dari satu simpul ke nod yang lain sementara algoritma Kruskal memilih tepi dengan cara bahawa kedudukan tepi tidak berdasarkan langkah terakhir.

• Dalam algoritma prim, grafik mestilah grafik yang bersambung sementara Kruskal juga boleh berfungsi pada grafik yang terputus.

• Algoritma Prim mempunyai kerumitan masa O (V ²), dan kerumitan masa Kruskal adalah O (logV).