Jumlah simpul yang dapat dijangkau dalam DAG untuk setiap simpul

Misalkan menjadi grafik berarah asiklik, sedemikian sehingga derajat dari titik mana pun adalah . Untuk setiap simpul kita dapat menghitung jumlah simpul yang bisa dijangkau, hanya dengan menjalankan dfs dari setiap simpul dan ini akan membutuhkan waktu . Apakah ada cara yang lebih baik untuk menyelesaikan masalah ini? $G(V,E)$ $O(\log{|V|})$ $G$ $O(|V||E|)$

ds.algorithms graph-theory graph-algorithms directed-acyclic-graph MikBB
sumber

Terkait: cstheory.stackexchange.com/q/736/236 cstheory.stackexchange.com/q/553/236

Radu GRIGore

@ Radu apakah ini duplikat langsung? kedengarannya seperti itu

Suresh Venkat

@ Suresh, dibandingkan dengan pertanyaan saya yang satu ini memiliki batas atas pada derajat dhuwur dan tidak meminta batas bawah. Ini adalah perbedaan kecil dalam pendapat saya, jadi saya akan menganggapnya sebagai duplikat, tetapi saya tidak merasa kuat tentang hal itu.

Radu GRIGore

ok jadi kita akan membiarkannya apa adanya.

Suresh Venkat

jawaban virgi untuk pertanyaan saya menyiratkan algoritma

untuk yang satu ini.

O (| V |^{2})

$O(|V|^2)$

Radu GRIGore

Jawaban:

Algoritma eksak terbaik akan berjalan dalam waktu O (min {mn, n ^ 2,38}) dengan menggunakan perkalian matriks biner cepat. Namun, ada algoritma acak, yang berjalan dalam waktu O (m + n) dan memperkirakan jumlah node yang dapat dijangkau dari setiap node dengan kesalahan relatif kecil, silakan merujuk ke kertas " Ukuran-Estimasi Kerangka Kerja dengan Aplikasi untuk Penutupan Transitif dan Reachability "oleh Edith Cohen.

pengguna22547
sumber

-1

Saya bukan ahli di sini saya akan mencoba.

1) Karena itu DAG, itu harus memiliki simpul wastafel yaitu simpul dengan outdegree 0. Cari simpul wastafel katakan x dan tambahkan {x} sebagai simpul yang dapat dijangkau ke Neighbor (x). hapus x dan ulangi proses sampai grafik menjadi kosong

Prabu
sumber

Karena out-degree dibatasi, akan lebih bermanfaat untuk memulai dengan sumber?

András Salamon

@ andras-salamon: tidak, karena Anda tidak tahu berapa banyak node yang dapat dijangkau dari suatu sumber. Anda tidak melakukan itu (nol) untuk wastafel.

Martin B.

O (| V | \cdot | E |)

$O(|V| \cdot |E|)$

x

$x$

O (| V |)

$O(|V|)$

O (| V |)

$O(|V|)$

O (| V |)

$O(|V|)$

O (| V | \cdot | E |)

$O(|V| \cdot |E|)$

-2

(Mirip dengan solusi Prabu ... tetapi lebih rinci)

$N(v)$ $v$ $reach(v)$

$O(|V|+|E|)$
$v$ $reach(v) = \sum_{n\in N(v)} reach(n)$

$|E|$ $O(|V|+|E|)$

Martin B.
sumber