Apa algoritma yang paling efisien untuk mendeteksi semua siklus dalam grafik yang diarahkan?
Saya memiliki grafik diarahkan yang mewakili jadwal pekerjaan yang perlu dieksekusi, pekerjaan menjadi simpul dan ketergantungan menjadi keunggulan. Saya perlu mendeteksi kasus kesalahan dari siklus dalam grafik ini yang mengarah ke dependensi siklik.
algorithm
graph-theory
directed-graph
Pengintip
sumber
sumber
Jawaban:
Algoritma komponen Tarjan yang sangat terhubung memiliki
O(|E| + |V|)
kompleksitas waktu.Untuk algoritma lain, lihat Komponen yang terhubung dengan kuat di Wikipedia.
sumber
O(|E| + |V|)
. Menggunakan warna putih (tidak pernah dikunjungi), abu-abu (simpul saat ini dikunjungi tetapi semua simpul yang dapat dijangkau belum dikunjungi) dan hitam (semua simpul yang terjangkau dikunjungi bersama dengan yang sekarang) kode warna, jika simpul abu-abu menemukan simpul abu-abu lain maka kita ' Sudah satu siklus. [Cukup banyak apa yang kita miliki di buku algoritma Cormen]. Ingin tahu apakah 'Algoritma Tarjan' memiliki manfaat dibandingkan DFS seperti itu !!Mengingat ini adalah jadwal pekerjaan, saya curiga pada suatu saat Anda akan menyortir ke dalam urutan eksekusi yang diusulkan.
Jika itu masalahnya, maka implementasi semacam topologi dalam hal apa pun dapat mendeteksi siklus. UNIX
tsort
tentu saja melakukannya. Saya pikir sangat mungkin karena itu lebih efisien untuk mendeteksi siklus pada saat yang sama dengan tsorting, daripada dalam langkah terpisah.Jadi pertanyaannya mungkin menjadi, "bagaimana saya paling efisien tsort", daripada "bagaimana cara paling efisien saya mendeteksi loop". Untuk yang jawabannya mungkin "menggunakan perpustakaan", tetapi gagal bahwa artikel Wikipedia berikut:
memiliki pseudo-code untuk satu algoritma, dan deskripsi singkat lainnya dari Tarjan. Keduanya memiliki
O(|V| + |E|)
kompleksitas waktu.sumber
Cara paling sederhana untuk melakukannya adalah dengan melakukan traversal kedalaman pertama (DFT) dari grafik .
Jika grafik memiliki
n
simpul, ini adalahO(n)
algoritma kompleksitas waktu. Karena Anda mungkin harus melakukan DFT mulai dari setiap titik, kompleksitas total menjadiO(n^2)
.Anda harus memelihara tumpukan yang berisi semua simpul di traversal pertama kedalaman saat ini , dengan elemen pertamanya adalah simpul akar. Jika Anda menemukan elemen yang sudah ada di tumpukan selama DFT, maka Anda memiliki siklus.
sumber
O(n)
sementara Anda menyarankan untuk memeriksa tumpukan untuk melihat apakah sudah mengandung simpul yang dikunjungi? Memindai tumpukan menambah waktu untukO(n)
runtime karena harus memindai tumpukan pada setiap node baru. Anda dapat mencapaiO(n)
jika Anda menandai node yang dikunjungiMenurut Lemma 22.11 dari Cormen et al., Pengantar Algoritma (CLRS):
Ini telah disebutkan dalam beberapa jawaban; di sini saya juga akan memberikan contoh kode berdasarkan bab 22 CLRS. Contoh grafik diilustrasikan di bawah ini.
Kode pseudo CLRS untuk pencarian kedalaman-pertama berbunyi:
Pada contoh di CLRS Gambar 22.4, grafik terdiri dari dua pohon DFS: satu terdiri dari simpul u , v , x , dan y , dan yang lainnya dari simpul w dan z . Setiap pohon berisi satu tepi belakang: satu dari x ke v dan satu lagi dari z ke z (loop otomatis).
Realisasi utama adalah bahwa tepi kembali ditemui ketika, dalam
DFS-VISIT
fungsi, sedangkan iterasi tetanggav
dariu
, sebuah node ditemui denganGRAY
warna.Kode Python berikut adalah adaptasi dari pseudocode CLRS dengan
if
klausa yang ditambahkan yang mendeteksi siklus:Perhatikan bahwa dalam contoh ini, the
time
pseudocode dalam CLRS tidak ditangkap karena kami hanya tertarik untuk mendeteksi siklus. Ada juga beberapa kode boilerplate untuk membangun representasi daftar adjacency dari grafik dari daftar tepi.Ketika skrip ini dieksekusi, ia mencetak output berikut:
Ini persis tepi belakang dalam contoh dalam CLRS Gambar 22.4.
sumber
Mulai dengan DFS: ada siklus jika dan hanya jika back-edge ditemukan selama DFS . Ini terbukti sebagai hasil dari teorema jalur putih.
sumber
Menurut pendapat saya, algoritma yang paling dapat dimengerti untuk mendeteksi siklus dalam grafik terarah adalah grafik-pewarnaan-algoritma.
Pada dasarnya, algoritma pewarnaan grafik berjalan grafik dengan cara DFS (Depth First Search, yang berarti bahwa ia mengeksplorasi jalur sepenuhnya sebelum menjelajahi jalur lain). Ketika menemukan tepi belakang, itu menandai grafik sebagai mengandung lingkaran.
Untuk penjelasan mendalam tentang algoritma pewarnaan grafik, silakan baca artikel ini: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
Juga, saya memberikan implementasi pewarnaan grafik dalam JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js
sumber
Jika Anda tidak bisa menambahkan properti "dikunjungi" ke node, gunakan satu set (atau peta) dan cukup tambahkan semua node yang dikunjungi ke set kecuali jika mereka sudah di set. Gunakan kunci unik atau alamat objek sebagai "kunci".
Ini juga memberi Anda informasi tentang "root" node dari ketergantungan siklik yang akan berguna ketika pengguna harus memperbaiki masalah.
Solusi lain adalah mencoba menemukan ketergantungan selanjutnya untuk dieksekusi. Untuk ini, Anda harus memiliki beberapa tumpukan di mana Anda dapat mengingat di mana Anda berada sekarang dan apa yang perlu Anda lakukan selanjutnya. Periksa apakah ada ketergantungan pada tumpukan ini sebelum Anda menjalankannya. Jika ya, Anda telah menemukan siklus.
Walaupun ini tampaknya memiliki kompleksitas O (N * M), Anda harus ingat bahwa stack memiliki kedalaman yang sangat terbatas (jadi N kecil) dan M menjadi lebih kecil dengan setiap ketergantungan yang dapat Anda centang sebagai "dieksekusi" ditambah Anda dapat menghentikan pencarian ketika menemukan daun (sehingga Anda tidak perlu memeriksa setiap node -> M juga kecil).
Di MetaMake, saya membuat grafik sebagai daftar daftar dan kemudian menghapus setiap node saat saya mengeksekusi mereka yang secara alami mengurangi volume pencarian. Saya tidak pernah benar-benar harus menjalankan pemeriksaan independen, semuanya terjadi secara otomatis selama eksekusi normal.
Jika Anda memerlukan mode "hanya tes", tambahkan saja bendera "run-run" yang menonaktifkan eksekusi pekerjaan aktual.
sumber
Tidak ada algoritma yang dapat menemukan semua siklus dalam grafik terarah dalam waktu polinomial. Misalkan, grafik yang diarahkan memiliki n node dan setiap pasangan node memiliki koneksi satu sama lain yang berarti Anda memiliki grafik yang lengkap. Jadi setiap subset non-kosong dari n node ini menunjukkan sebuah siklus dan ada 2 ^ n-1 jumlah himpunan bagian tersebut. Jadi tidak ada algoritma waktu polinomial. Jadi misalkan Anda memiliki algoritma yang efisien (tidak bodoh) yang dapat memberi tahu Anda jumlah siklus yang diarahkan dalam grafik, Anda dapat menemukan komponen yang terhubung terlebih dahulu, kemudian menerapkan algoritma Anda pada komponen yang terhubung ini. Karena siklus hanya ada di dalam komponen dan bukan di antara mereka.
sumber
Saya telah menerapkan masalah ini di sml (pemrograman imperatif). Inilah garis besarnya. Temukan semua node yang memiliki indegree atau outdegree 0. Node tersebut tidak dapat menjadi bagian dari siklus (jadi hapuslah). Selanjutnya hapus semua tepi masuk atau keluar dari node tersebut. Secara rekursif menerapkan proses ini ke grafik yang dihasilkan. Jika pada akhirnya Anda tidak dibiarkan memiliki simpul atau tepi apa pun, grafik tidak memiliki siklus apa pun, kecuali grafiknya.
sumber
Cara saya melakukannya adalah melakukan Sortasi Topologi, menghitung jumlah simpul yang dikunjungi. Jika jumlah itu kurang dari jumlah total simpul dalam DAG, Anda memiliki siklus.
sumber
/mathpro/16393/finding-a-cycle-of-fixed-length Saya menyukai solusi ini yang terbaik khusus untuk 4 panjang :)
Wisaya fisika juga mengatakan Anda harus melakukan O (V ^ 2). Saya percaya bahwa kita hanya membutuhkan O (V) / O (V + E). Jika grafik terhubung maka DFS akan mengunjungi semua node. Jika grafik telah menghubungkan sub grafik maka setiap kali kita menjalankan DFS pada simpul dari sub grafik ini, kita akan menemukan simpul yang terhubung dan tidak harus mempertimbangkan ini untuk menjalankan DFS berikutnya. Oleh karena itu kemungkinan berjalan untuk setiap simpul tidak benar.
sumber
Jika DFS menemukan tepi yang menunjuk ke titik yang sudah dikunjungi, Anda memiliki siklus di sana.
sumber
Seperti yang Anda katakan, Anda memiliki serangkaian pekerjaan, itu harus dieksekusi dalam urutan tertentu.
Topological sort
memberi Anda pesanan yang diperlukan untuk penjadwalan pekerjaan (atau untuk masalah ketergantungan jika itu adalahdirect acyclic graph
). Jalankandfs
dan pertahankan daftar, dan mulai menambahkan simpul di awal daftar, dan jika Anda menemukan simpul yang sudah dikunjungi. Kemudian Anda menemukan siklus dalam grafik yang diberikan.sumber
Jika sebuah grafik memenuhi properti ini
maka grafik mengandung setidaknya pada siklus.
sumber