Mengapakah algoritma pokok rentang minimum Prim dan Kruskal gagal dalam graf terarah?

Kaedah Prim dan algoritma Kruskal ialah dua kaedah biasa untuk mencari MST (pokok rentang minimum) dalam graf tidak terarah. Walau bagaimanapun, teknik ini tidak boleh menjana MST yang betul untuk graf terarah. Ini kerana graf terarah tidak sesuai dengan andaian asas dan kaedah yang digunakan oleh algoritma Prim dan Kruskal.

Algoritma prim

Pertama, terdapat algoritma Prim, yang melibatkan penambahan tepi pada pokok rentang minimum yang mengembang dengan cara yang tamak sehingga semua bucu ditutup. Bucu di dalam MST disambungkan ke bucu di luar MST melalui tepi dengan berat terendah. Memandangkan semua tepi dalam graf tidak terarah boleh bergerak ke mana-mana arah, laluan terpendek dari MST ke bucu luaran mudah dicari. Walau bagaimanapun, dalam graf terarah, tepi sentiasa menghala ke satu arah dan mungkin tiada garis lurus yang menghubungkan MST dan bucu luaran. Ini bercanggah dengan prinsip asas algoritma Prim.

Contohnya ialah tepi terarah (u,v) yang menghubungkan bucu u dalam MST ke bucu v dalam graf luar MST. Memandangkan MST dalam kaedah Prim mesti disambungkan ke bucu luaran melalui tepi terus, tepi (u, v) diabaikan, mengakibatkan MST mungkin tidak tepat atau tidak mencukupi.

Kaedah Kruskal

Kaedah Kruskal ialah teknik pengisihan tepi berwajaran yang berulang kali menambah tepi berat minimum yang tidak menjana kitaran pada graf. Kaedah ini paling sesuai untuk graf tidak terarah kerana tepi menghala ke dua arah, jadi kitaran boleh dikesan dengan mudah. Memandangkan arah tepi penting dalam graf terarah, konsep kitaran menjadi lebih halus. Pendekatan Kruskal mengabaikan kerumitan ini.

Andaikan terdapat gelung arah dalam MST yang anda sedang bina. Apabila digunakan pada graf terarah, teknik Kruskal boleh menjana pokok yang mengandungi kitaran terarah. Kaedah ini menghasilkan MST yang tidak tepat kerana mekanisme pengesanan kitaran berasaskan tepi tidak terarah gagal menangkap kitaran dengan betul dalam graf terarah.

KESIMPULAN

Boleh disimpulkan bahawa walaupun teknik Prim dan Kruskal berguna untuk mencari MST dalam graf tidak terarah, ia tidak boleh digunakan pada graf terarah. Kaedah-kaedah ini menghasilkan MST yang tidak tepat atau tidak mencukupi kerana andaian dan mekanisme asas yang mana mereka bergantung tidak dipegang dalam tetapan graf terarah. Graf terarah mempunyai sifat unik dan kerumitannya sendiri, jadi adalah penting untuk menggunakan teknik khusus digraf (seperti kaedah Chu−Liu/Edmonds) untuk mendapatkan pokok rentang minimum.

Atas ialah kandungan terperinci Mengapakah algoritma pokok rentang minimum Prim dan Kruskal gagal dalam graf terarah?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!