Arahan-arahan ditemukan

Pertimbangkan grafik terarah di mana seseorang dapat secara dinamis menambahkan tepi dan membuat beberapa pertanyaan tertentu.$G$

Contoh: hutan disjoint-set

Pertimbangkan serangkaian pertanyaan berikut:

arrow(u, v)
equiv(u, v)
find(u)

yang pertama menambahkan panah ke grafik, yang kedua memutuskan jika u ↔ ∗ v , yang terakhir menemukan perwakilan kanonik dari kelas ekivalensi ↔ ∗ , yaitu r ( u ) sedemikian rupa sehingga u ↔ ∗ v menyiratkan r ( v ) = r ( u ) .$u→v$$u↔^*v$$↔^*$$r(u)$$u↔^*v$$r(v)=r(u)$

Ada algoritma yang terkenal menggunakan struktur data hutan disjoint-set yang mengimplementasikan query ini dalam kompleksitas diamasi-konstan diamasi, yaitu . Perhatikan bahwa dalam hal ini diterapkan menggunakan .$O(α(n))$equivfind

Varian yang lebih kompleks

Sekarang saya tertarik pada masalah yang lebih kompleks di mana arahnya penting:

arrow(u, v)
confl(u, v)
find(u)

yang pertama menambahkan panah , detik memutuskan apakah ada simpul w yang dapat dicapai dari kedua u dan v , yaitu u → ∗ ← ∗ v . Yang terakhir harus mengembalikan objek r ( u ) sehingga u → ∗ ← ∗ v menyiratkan r ( u ) ∙ r ( v ) di mana ∙ harus mudah dihitung. (Untuk, katakanlah, menghitung$u→v$$w$$u$$v$$u→^*←^*v$$r(u)$$u→^*←^*v$$r(u) \bullet r(v)$$\bullet$confl). Tujuannya adalah untuk menemukan struktur data yang baik sehingga operasi ini cepat.

Siklus

Grafik dapat berisi siklus.

Saya tidak tahu apakah ada cara untuk secara efisien dan bertahap menghitung komponen yang sangat terhubung, untuk hanya mempertimbangkan DAG untuk masalah utama.

Tentu saja saya akan menghargai solusi untuk DAG juga. Ini akan sesuai dengan perhitungan tambahan dari leluhur yang paling tidak umum.

Pendekatan naif

Struktur data hutan yang terpisah-pisah tidak membantu di sini, karena mengabaikan arah tepi. Perhatikan bahwa tidak boleh berupa satu node, dalam kasus ini grafiknya tidak rapat.$r(u)$

Satu dapat menentukan dan untuk mendefinisikan ∙ sebagai S 1 ∙ S 2 ketika S 1 ∩ S 2 ≠ ∅ . Tetapi bagaimana cara menghitung ini secara bertahap?$r(u)=\{v ∣ u→^*v\}$$\bullet$$S_1\bullet S_2$$S_1 ∩ S_2≠∅$

Mungkin komputasi himpunan sebesar itu tidak berguna, himpunan yang lebih kecil seharusnya lebih menarik, seperti pada algoritma union-find yang biasa.

( Sunting : tulis ulang sepenuhnya jawaban saya sekarang karena pemahaman saya tentang masalah ini (saya harap) lebih jelas.)

Sepertinya masalah ini dapat direduksi menjadi konstruksi bertahap dan meningkatkan perkiraan penutupan transitif grafik, saat grafik dibuat dan dicari.

$r(u)$$u$$v$$v \ne u$$u, v$$u$$v$$u$$w$$v$$w$

$u$$u$$R(u)$

Saya tidak punya ide begitu saja untuk struktur data yang menangkap ini yang lebih efisien daripada kasus umum (misalnya vektor sedikit atau tabel hash,) tetapi Anda dapat memperbarui set ini secara bertahap:

$u$$v$$R(u) = R(u) \cup R(v)$

confl$R(u) \cap R(v)$$R(u)$$R(v)$$R(u)$$R(v)$$R$dan jika Anda menemukan simpul yang sama, atur R (u) = R (v) = R (u) \ cup R (v) .

find(u)$R(u)$conflfind$R$$O(\alpha(n))$confl$R$

Ini kedengarannya seperti itu mungkin kasus khusus metode La Poutré dan van Leeuwen untuk menjaga penutupan transitif dari grafik .

$R$