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. Pokok spanning adalah subgraph graf supaya setiap nod graf dihubungkan dengan jalan, iaitu pokok. Setiap pokok merangkumi mempunyai berat badan, dan berat minimum / kos yang mungkin bagi semua pokok merangkumi pokok minimum merangkumi (MST).

Lebih banyak 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 ini boleh dinyatakan dalam tiga langkah utama;

Memandangkan graf yang bersambung dengan n nod dan berat setiap kelebihan,

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 dan pilih minimum. Tambahkan tepi dan nod pada hujung lain pokok T dan keluarkan tepi dari graf. (Pilih mana-mana jika terdapat dua atau lebih minimum)

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

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

Lebih banyak 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 n nod dan berat setiap kelebihannya,

1. Pilih arka dengan sekurang-kurangnya berat graf keseluruhan dan tambahkan pada pokok itu dan hapus dari graf.

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

3. Ulangi proses dalam langkah 2.

Dalam kaedah ini, algoritma bermula dengan kelebihan kurang berat dan terus memilih setiap kelebihan 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?

• Prim algoritma memulakan dengan node, sedangkan algoritma Kruskal bermula dengan kelebihan.

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

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

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