Apakah dua algoritma untuk penutupan transitif?

Dua algoritma untuk penutupan transitif: 1. Algoritma Warshall: Algoritma Warshall ialah algoritma pengaturcaraan dinamik yang digunakan untuk mengira penutupan transitif. Ia mengemas kini matriks Boolean secara berulang untuk mewakili hubungan kebolehcapaian antara nod 2. Algoritma Roy-Warshall: Algoritma Roy-Warshall juga merupakan algoritma pengaturcaraan dinamik yang digunakan untuk mengira penutupan transitif. Ia mewakili hubungan kebolehcapaian antara nod melalui operasi pendaraban matriks.

Sistem pengendalian untuk tutorial ini: sistem Windows 10, komputer Dell G3.

Penutupan transitif ialah konsep dalam teori graf yang digunakan untuk menerangkan hubungan kebolehcapaian antara nod dalam graf terarah. Dalam graf terarah, jika terdapat laluan dari nod A ke nod B, maka nod B ialah nod pengganti nod A, dan nod A ialah nod pendahulu nod B. Penutupan transitif mewakili hubungan kebolehcapaian antara semua nod dalam graf.

Semasa mengira penutupan transitif, dua algoritma yang biasa digunakan ialah:

1 Algoritma Warshall (algoritma Floyd-Warshall): Algoritma Warshall ialah algoritma pengaturcaraan dinamik penutupan. Ia secara berulang mengemas kini matriks Boolean yang mewakili hubungan kebolehcapaian antara nod. Langkah-langkah khusus adalah seperti berikut:

Memulakan matriks Boolean Jika terdapat tepi dari nod i ke nod j, tetapkan baris ke-i dan lajur ke-j matriks kepada benar, jika tidak. ia adalah palsu.

Untuk setiap nod k, melintasi semua nod i dan nod j Jika nod i tidak boleh dicapai dari nod j dan nod i boleh dicapai dari nod k dan nod k boleh dicapai dari nod j, kemas kini i-. baris ke dan lajur ke-j matriks adalah benar.

Ulang langkah di atas sehingga matriks tidak lagi berubah.

2. Algoritma Roy-Warshall (Penutupan Transitif oleh Matrix Squaring): Algoritma Roy-Warshall juga merupakan algoritma pengaturcaraan dinamik yang digunakan untuk mengira penutupan transitif. Ia mewakili hubungan kebolehcapaian antara nod melalui operasi pendaraban matriks. Langkah-langkah khusus adalah seperti berikut:

Memulakan matriks Boolean Jika terdapat tepi dari nod i ke nod j, tetapkan baris ke-i dan lajur ke-j matriks kepada benar, jika tidak. ia adalah palsu.

Bagi setiap nod k, hitung kuasa dua matriks, iaitu, darabkan matriks dengan dirinya untuk mendapatkan matriks baharu.

Ulang langkah di atas sehingga matriks tidak lagi berubah.

Kedua-dua algoritma boleh digunakan untuk mengira penutupan transitif, tetapi dalam aplikasi praktikal, memilih algoritma yang sesuai bergantung pada masalah tertentu dan saiz data. Algoritma Warshall sesuai untuk graf padat, manakala algoritma Roy-Warshall sesuai untuk graf jarang.

Atas ialah kandungan terperinci Apakah dua algoritma untuk penutupan transitif?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!