Kruskal vs Prim
Dalam sains komputer, algoritma Prim dan Kruskal ialah algoritma tamak yang mencari pepohon rentang minimum untuk graf berwajaran tidak berarah yang bersambung. Pokok spanning ialah subgraf bagi graf supaya setiap nod graf disambungkan oleh laluan, iaitu pokok. Setiap pokok rentang mempunyai berat, dan berat/kos minimum yang mungkin untuk semua pokok rentang ialah pokok rentang minimum (MST).
Lagi tentang 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 ini boleh dinyatakan dalam tiga langkah utama;
Memandangkan graf yang disambungkan dengan n nod dan berat masing-masing bagi setiap tepi, 1. Pilih nod arbitrari daripada graf dan tambahkannya pada pokok T (yang akan menjadi nod pertama)
2. Pertimbangkan berat setiap tepi yang disambungkan ke nod dalam pokok dan pilih yang minimum. Tambah tepi dan nod di hujung satu lagi pokok T dan keluarkan tepi daripada graf. (Pilih mana-mana jika dua atau lebih minimum wujud)
3. Ulangi langkah 2, sehingga n-1 tepi ditambahkan pada pokok.
Dalam kaedah ini, pepohon bermula dengan satu nod arbitrari dan mengembang dari nod itu dan seterusnya dengan setiap kitaran. Oleh itu, untuk algoritma berfungsi dengan betul, graf tersebut mestilah graf bersambung. Bentuk asas algoritma Prim mempunyai kerumitan masa O(V2).
Lagi tentang 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 n nod dan berat masing-masing bagi setiap tepi, 1. Pilih lengkok dengan berat keseluruhan graf yang paling sedikit dan tambahkan pada pokok dan padamkan daripada graf.
2. Daripada baki pilih kelebihan paling kurang wajaran, dengan cara yang tidak membentuk kitaran. Tambahkan tepi pada pokok dan padam daripada graf. (Pilih mana-mana jika dua atau lebih minimum wujud)
3. Ulangi proses dalam langkah 2.
Dalam kaedah ini, algoritma bermula dengan tepi paling kurang wajaran dan terus memilih setiap tepi 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, manakala algoritma Kruskal bermula dengan tepi.
• Algoritma Prim menjangkau dari satu nod ke nod yang lain manakala algoritma Kruskal memilih tepi dengan cara kedudukan tepi tidak berdasarkan langkah terakhir.
• Dalam algoritma prim, graf mestilah graf bersambung manakala Kruskal juga boleh berfungsi pada graf terputus sambungan.
• Algoritma Prim mempunyai kerumitan masa O(V2), dan kerumitan masa Kruskal ialah O(logV).
