Algoritma yang efisien untuk mengambil penutupan transitif dari grafik asiklik diarahkan

Saya mencoba untuk memecahkan masalah grafik (ini bukan untuk pekerjaan rumah, hanya untuk melatih keterampilan saya). DAG diberikan, di mana V adalah himpunan simpul dan E tepi. Grafik diwakili sebagai daftar adjacency, jadi A v adalah himpunan yang berisi semua koneksi v . Tugas saya adalah untuk menemukan yang simpul dicapai dari setiap sudut v ∈ V . Solusi yang saya gunakan memiliki kompleksitas O ( V 3$G(V,E)$$V$$E$$A_v$$v$$v\in V$$O(V^3)$, dengan penutupan transitif, tetapi saya membaca bahwa di blog bisa lebih cepat, meskipun tidak mengungkapkan caranya. Adakah yang bisa memberitahu saya cara lain (dengan kompleksitas yang lebih baik) untuk memecahkan masalah penutupan transitif dalam DAG?

Fakta bahwa grafik kita asiklik membuat masalah ini lebih sederhana.

Sortasi topologi dapat memberi kita urutan simpul sehingga, jika i < j , maka tidak ada tepi dari v j kembali ke v i . Kami telah membuat daftar simpul sedemikian rupa sehingga semua ujung masuk "maju" dalam daftar kami.$v_1,v_2,\dots,v_n$$i < j$$v_j$$v_i$

(diedit untuk memperbaiki analisis dan memberikan algoritma yang sedikit lebih cepat)

Sekarang kita kembali ke daftar ini, mulai dari titik terakhir . v n 's penutupan transitif hanya sendiri. Juga tambahkan v n ke penutupan transitif setiap simpul dengan tepi ke v n .$v_n$$v_n$$v_n$$v_n$

Untuk setiap vertex , pergi dari ujung ke belakang, pertama-tama tambahkan v i ke penutupan transitifnya sendiri, kemudian tambahkan semua yang ada di penutupan transitif v i ke penutupan transitif semua simpul dengan ujung ke v i .$v_i$$v_i$$v_i$$v_i$

Waktu berjalan adalah dalam kasus terburuk, dengan n jumlah simpul dan m ∈ O ( n 2 ) jumlah tepi. Sortasi topologis membutuhkan waktu O ( n + m ) . Kemudian kita melakukan pekerjaan O ( m n ) yang lain di backward pass: Ketika kita mundur daftar, untuk setiap edge, kita harus menambahkan hingga $O(n+m+nm) = O(n^3)$$n$$m \in O(n^2)$$O(n+m)$$O(mn)$$n$ simpul untuk penutupan transitif seseorang.

$n=64$$i$$i$$i$$j$$c_j$$c_i$

$n > 64$

$O$$O(n^3)$