Menemukan sumber grafik asiklik terarah dalam waktu linier

Diberikan grafik asiklik langsung , simpul adalah sumber jika indegree - nya adalah nol, artinya hanya memiliki busur keluar. $D = (V,A)$ $v \in V$

Apakah ada algoritma waktu linear untuk menemukan sumber dalam grafik asiklik langsung yang diberikan?

Pertanyaan tindak lanjut: Dapatkah seseorang dalam waktu linier menemukan semua sumber?

algorithms graph-theory breezeintopl
sumber

Dengan root, maksud Anda sebuah simpul yang memiliki semua tepi keluar dan tidak ada tepi masuk? Jika demikian, mungkin ada lebih dari satu akar.

Paresh

Ya kamu benar. Itu sebabnya saya mengatakan "root" tetapi bukan "root".

breezeintopl

Dalam hal itu, bukankah definisi tersebut cukup untuk algoritma waktu linier?

Paresh

Apa struktur datanya? Apakah Anda diberi matriks adjacency, daftar lingkungan, daftar adjacency atau apa? Bisakah Anda memeriksa lingkungan (masuk) dari sebuah titik dalam waktu yang sebanding dengan ukurannya?

Pål GD

Jika maksud Anda linear dalam jumlah simpul, Anda harus menunjukkan itu. Juga, daftar adjacency ambigu untuk grafik diarahkan - apakah Anda daftar tepi masuk, tepi keluar, baik dalam daftar terpisah, atau keduanya bersamaan?

Yuval Filmus

Jawaban:

Seperti yang Yuval katakan, struktur datanya penting di sini. Saya akan mencoba memberikan solusi untuk beberapa jenis daftar adjacency:

Daftar tepi masuk : Untuk setiap node, ada daftar simpul dari mana ada tepi masuk ke node ini. Anda cukup memindai semua simpul dan memeriksa apakah ukuran daftar kedekatan mereka $0$ atau tidak. Ukuran $0$ daftar berarti tidak ada tepi yang masuk, sehingga simpul merupakan sumber atau terputus. Dengan asumsi grafik terhubung, pemindaian setiap titik ini akan memberi Anda daftar semua sumber (atau Anda dapat berhenti setelah menemukan satu) di $O(|V|)$ waktu - linear dalam jumlah simpul .
Daftar tepi keluar : Untuk setiap node, ada daftar simpul yang ada tepi diarahkan dari node ini. Pertahankan bit-string dengan masing-masing bit mewakili sebuah vertex, diinisialisasi ke 0. Mulai dari node pertama, mulai memindai daftar untuk simpul yang ada tepi keluar dari ini. Setiap node seperti itu (tetangga) tidak bisa menjadi sumber, jadi terus atur bit terkait mereka dalam bit-string. Pada akhirnya, semua simpul yang bit terkaitnya masih belum disetel, adalah simpul sumber. Anda dapat melakukan ini dalam waktu linier dalam ukuran grafik - $O(|V| + |E|)$ .
Kedua daftar bersama-sama : Untuk setiap simpul, ada daftar simpul campuran yang memiliki tepi ke atau dari simpul ini, dengan beberapa atribut lain yang menunjukkan yang mana dari keduanya sebenarnya adalah kasus. Pendekatannya mirip dengan 2 di atas, dengan tambahan bahwa setiap tepi yang masuk segera mengesampingkan simpul saat ini (dan Anda dapat menandai bit set-nya). Tidak seperti pada poin 2 di mana Anda harus melalui semua simpul, di sini, Anda mungkin menemukan beberapa sumber lebih cepat. Jika Anda tidak berhenti, Anda akan memiliki semua sumber. Untuk kedua kasus, waktu kembali linier dalam ukuran grafik - $O(|V| + |E|)$ .
Kedua daftar secara terpisah : Cukup pilih daftar tepi yang masuk dan ikuti 1.

Sebagai catatan tambahan, jika memilih struktur data ada di tangan Anda, Anda mungkin ingin menganalisis semua operasi yang ingin Anda lakukan, dan seberapa sering, dan memilih struktur data yang sesuai.

Sunting: Untuk kasus 1, jika Anda memiliki dag di mana jumlah sumber sangat kecil dibandingkan dengan $|V|$ (misalnya, dalam pohon dengan satu sumber), dan di mana jarak rata-rata dari titik mana pun ke sumber kecil dibandingkan dengan $|V|$ dan Anda hanya menginginkan satu sumber saja, Anda dapat menggunakan algoritme rata-rata yang lebih cepat (meskipun kompleksitas asimptotik kasus terburuk akan sama). Pilih sembarang titik secara acak, dan buka salah satu induknya (dari daftar tepi yang masuk), dan terus ke induknya dan seterusnya, hingga Anda mencapai simpul yang tidak memiliki induk - sumber. Keuntungan kecil dari efisiensi ini adalah untuk jenis grafik yang sangat terbatas dengan algoritma yang sedikit lebih kompleks.

Paresh
sumber

Untuk daftar tepi yang masuk, jika Anda hanya perlu menemukan satu sumber, bukankah akan lebih cepat untuk hanya mengikuti tepi arbitrer untuk mendapatkan pendahulunya, sampai Anda mencapai sumber? Terutama jika grafiknya datar, yaitu jarak rata-rata ke setiap sumber setiap titik jauh lebih kecil daripada

| V |

$|V|$ .

Simon S

@SimonS Meskipun kompleksitas kasus terburuk adalah sama (mis., Rantai linear), Anda mungkin membuatnya lebih cepat jika grafik memiliki sumber yang sangat sedikit (dibandingkan dengan

| V |

$|V|$ ) dan jarak rata - rata dari titik ke sumber sangat kecil - misalnya. grafik bintang dengan pusat sebagai sumber. Hanya memiliki kondisi yang Anda sebutkan tidak mencukupi - mis. 1-> 2, 1-> 3, 4-> 2, 4-> 3 - (Anda dapat memiliki grafik dengan avg distance 0.5 dan | V | / 2 sumber) jarak rata-rata kecil, tetapi kedua algoritma akan memberikan waktu yang sama / mirip. Saya akan menambahkannya ke jawaban saya.

Paresh

Terima kasih atas jawaban Anda! Saya pikir apa yang saya maksud adalah kasus kedua, daftar keluar. BTW, mengapa itu O (| V | + | E |)? Saya tahu | E |, karena Anda harus memindai semua tepi, tetapi di mana | V | dari? Terima kasih!

breezeintopl

@breezeintopl Ini adalah cara representasi. Anda memeriksa setiap sisi satu kali dan setiap titik juga konstan beberapa kali. Paling tidak, pada akhirnya Anda harus memindai semua simpul sekali untuk melihat bit mana yang tidak disetel. Cara lain untuk melihatnya adalah menggunakan daftar adjacency

Θ (| V | + | E |)

$\Theta(|V| + |E|)$ space - menyimpan titik dan daftar ujungnya. Dan Anda menelusuri seluruh daftar. Tentu saja sejak itu

| E |

$|E|$ dapat berkisar dari

O (| V |)

$O(|V|)$ untuk

O (| V |^{2})

$O(|V|^2)$ , Anda bisa melewatkan

| V |

$|V|$ bagian. Lihat contoh untuk BFS .

Paresh

Mari kita pertimbangkan pertanyaan yang lebih sederhana. Misalkan Anda tahu grafik Anda adalah pohon. Kemudian Anda dapat menemukan simpul sumber dalam waktu linier. Cukup pilih simpul acak, jika itu adalah root maka Anda memiliki jawaban Anda, jika bukan itu haruslah anak atau orang tua lalu lintasi kembali hingga Anda mencapai root. Ini bisa dilakukan di $O(|V|-1)$ .

Reza
sumber

Jika struktur data Anda tidak menyertakan daftar tepi untuk sebuah simpul, maka menemukan induk sudah mengambil O (m) (dalam pohon maka O (n) waktu. Karena jalur ke akar pohon dapat linier panjang, ini hanya solusi kuadrat Tapi jika Anda memiliki di-tepi, kemudian menemukan beberapa simpul dengan 0 di tepi adalah sepele..

adrianN

-1

Dengan asumsi Anda memiliki grafik G = (V, E) yang diberikan dalam format daftar adjacency. (agar lebih jelas di sini daftar berisi semua tepi keluar dari sumber). Anda dapat membuat kebalikan dari grafik G dalam waktu linier. Kemudian Anda dapat mengulangi grafik terbalik dan mengumpulkan semua simpul yang memiliki daftar adjacency kosong. Verteks ini tidak memiliki tepi keluar dalam grafik terbalik yang berarti mereka tidak memiliki tepi masuk dalam grafik asli, oleh karena itu, ini adalah simpul sumber Anda.

Waktu berjalan adalah linear. Membangun terbalik grafik membutuhkan waktu maksimal O (| V | + | E |). Iterasi atas invers grafik membutuhkan waktu O (| V |).

MGB
sumber

Jujur, menghitung grafik kebalikannya terdengar seperti masalah yang lebih sulit daripada menemukan sumbernya. Saya ragu bahwa seseorang yang tidak tahu cara mendapatkan sumber bisa mengetahui cara membalikkan semua tepinya.

David Richerby

@ DavidRicherby Anda mengatakan menghitung terbalik grafik lebih sulit. Bagaimana Anda mendefinisikan lebih sulit? Jika kompleksitas waktu dapat dilakukan dalam waktu linier. Anda dapat melihat solusinya di sini [tautan] ( stackoverflow.com/questions/40378152/… ). Pertanyaannya adalah tentang solusi waktu linier yang menemukan sumber grafik dan solusi yang saya usulkan melakukannya. Jika Anda pikir itu tidak dapat Anda spesifik dan katakan padaku bagaimana algoritma saya tidak memenuhi persyaratan waktu linier?

MGB

Maksud saya lebih sulit secara konseptual. Anda mengatakan bahwa, untuk menyelesaikan latihan ini, penanya hanya perlu menyelesaikan beberapa latihan lain, tetapi latihan lain itu tampaknya lebih sulit daripada yang pertama.

David Richerby