Algoritma terbaik untuk mendeteksi siklus dalam grafik yang diarahkan

396

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.

Pengintip
sumber
13
Anda mengatakan ingin mendeteksi semua siklus, tetapi use case Anda menunjukkan bahwa itu akan cukup untuk mendeteksi apakah ada siklus.
Steve Jessop
29
Akan lebih baik untuk mendeteksi semua siklus sehingga mereka dapat diperbaiki dalam sekali jalan, daripada memeriksa, memperbaiki, memeriksa, dll.
Peauters
2
Anda harus membaca makalah "Menemukan semua sirkuit dasar dari grafik yang diarahkan" oleh Donald B. Johnson. Ini hanya akan menemukan sirkuit dasar, tetapi ini harus cukup untuk kasus Anda. Dan inilah implementasi Java saya dari algoritma ini yang siap digunakan: github.com/1123/johnson
user152468
Jalankan DFS dengan modifikasi tambahan untuk algoritme: tandai setiap node yang Anda kunjungi. jika Anda mengunjungi node yang sudah dikunjungi, maka Anda memiliki sebuah cicle. ketika Anda mundur dari jalur, hapus centang pada node yang dikunjungi.
Hesham Yassin
2
@HeshamYassin, jika Anda mengunjungi node yang sudah Anda kunjungi, itu tidak berarti ada satu loop Silakan baca komentar saya cs.stackexchange.com/questions/9676/… .
Maksim Dmitriev

Jawaban:

193

Algoritma komponen Tarjan yang sangat terhubung memiliki O(|E| + |V|)kompleksitas waktu.

Untuk algoritma lain, lihat Komponen yang terhubung dengan kuat di Wikipedia.

aku
sumber
70
Bagaimana cara menemukan komponen yang sangat terhubung memberi tahu Anda tentang siklus yang ada dalam grafik?
Peter
4
Mungkin seseorang dapat mengonfirmasi tetapi algoritma Tarjan tidak mendukung siklus node yang menunjuk langsung ke diri mereka sendiri, seperti A-> A.
Cédric Guillemette
24
@ Cedrik Benar, tidak langsung. Ini bukan cacat dalam algoritma Tarjan, tetapi cara ini digunakan untuk pertanyaan ini. Tarjan tidak secara langsung menemukan siklus , ia menemukan komponen yang sangat terhubung. Tentu saja, setiap SCC dengan ukuran lebih besar dari 1 menyiratkan siklus. Komponen non-siklik memiliki SCC singleton sendiri. Masalahnya adalah loop-diri juga akan masuk ke SCC dengan sendirinya. Jadi, Anda perlu pemeriksaan terpisah untuk pengulangan sendiri, yang cukup sepele.
mgiuca
13
(semua komponen yang sangat terhubung dalam grafik)! = (semua siklus dalam grafik)
optimusfrenk
4
@ aku: DFS tiga warna juga memiliki runtime yang sama 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 !!
KGhatak
73

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 tsorttentu 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:

http://en.wikipedia.org/wiki/Topological_sorting

memiliki pseudo-code untuk satu algoritma, dan deskripsi singkat lainnya dari Tarjan. Keduanya memiliki O(|V| + |E|)kompleksitas waktu.

Steve Jessop
sumber
Jenis topologi dapat mendeteksi siklus, karena bergantung pada algoritma pencarian mendalam-pertama, tetapi Anda membutuhkan pembukuan tambahan untuk benar-benar mendeteksi siklus. Lihat jawaban Kurt Peek yang benar.
Luke Hutchison
33

Cara paling sederhana untuk melakukannya adalah dengan melakukan traversal kedalaman pertama (DFT) dari grafik .

Jika grafik memiliki nsimpul, ini adalah O(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.

nbro
sumber
21
Hal ini akan berlaku untuk grafik "biasa", tetapi palsu untuk diarahkan grafik. Sebagai contoh, perhatikan "diagram ketergantungan berlian" dengan empat simpul: A dengan ujung-ujungnya menunjuk ke B dan C, masing-masing memiliki tepi yang menunjuk ke D. Traversal DFT Anda dari diagram ini dari A akan secara keliru menyimpulkan bahwa "lingkaran" itu sebenarnya sebuah siklus - meskipun ada loop, itu bukan siklus karena tidak dapat dilalui dengan mengikuti panah.
Peter
9
@ Peter bisa tolong jelaskan bagaimana DFT dari A akan salah menyimpulkan bahwa ada siklus?
Deepak
10
@Deepak - Sebenarnya, saya salah membaca jawaban dari "penyihir fisika": di mana ia menulis "di tumpukan" Saya pikir "sudah ditemukan". Memang akan cukup (untuk mendeteksi loop yang diarahkan) untuk memeriksa dupes "di tumpukan" selama pelaksanaan DFT. Satu upvote untuk Anda masing-masing.
Peter
2
Mengapa Anda mengatakan kompleksitas waktu O(n)sementara Anda menyarankan untuk memeriksa tumpukan untuk melihat apakah sudah mengandung simpul yang dikunjungi? Memindai tumpukan menambah waktu untuk O(n)runtime karena harus memindai tumpukan pada setiap node baru. Anda dapat mencapai O(n)jika Anda menandai node yang dikunjungi
James Wierzba
Seperti kata Peter, ini tidak lengkap untuk grafik berarah. Lihat jawaban Kurt Peek yang benar.
Luke Hutchison
32

Menurut Lemma 22.11 dari Cormen et al., Pengantar Algoritma (CLRS):

Grafik berarah G adalah asiklik jika dan hanya jika pencarian G-kedalaman tidak menghasilkan tepi belakang.

Ini telah disebutkan dalam beberapa jawaban; di sini saya juga akan memberikan contoh kode berdasarkan bab 22 CLRS. Contoh grafik diilustrasikan di bawah ini.

masukkan deskripsi gambar di sini

Kode pseudo CLRS untuk pencarian kedalaman-pertama berbunyi:

masukkan deskripsi gambar di sini

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-VISITfungsi, sedangkan iterasi tetangga vdari u, sebuah node ditemui dengan GRAYwarna.

Kode Python berikut adalah adaptasi dari pseudocode CLRS dengan ifklausa yang ditambahkan yang mendeteksi siklus:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

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:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

Ini persis tepi belakang dalam contoh dalam CLRS Gambar 22.4.

Kurt Peek
sumber
29

Mulai dengan DFS: ada siklus jika dan hanya jika back-edge ditemukan selama DFS . Ini terbukti sebagai hasil dari teorema jalur putih.

Ajay Garg
sumber
3
Ya, saya kira sama, tetapi ini tidak cukup, saya memposting cara saya cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph
jonaprieto
Benar. Ajay Garg hanya menceritakan tentang bagaimana menemukan "siklus", yang merupakan bagian jawaban untuk pertanyaan ini. Tautan Anda berbicara tentang menemukan semua siklus sesuai pertanyaan yang diajukan, tetapi sekali lagi sepertinya menggunakan pendekatan yang sama seperti Ajay Garg, tetapi juga melakukan semua kemungkinan dfs-tree.
Manohar Reddy Poreddy
Ini tidak lengkap untuk grafik yang diarahkan. Lihat jawaban Kurt Peek yang benar.
Luke Hutchison
26

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

Armin Primadi
sumber
8

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.

Aaron Digulla
sumber
7

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.

Yuwen
sumber
1
Benar, jika jumlah node diambil sebagai ukuran input. Anda juga bisa mendeskripsikan kompleksitas runtime dalam hal jumlah tepi atau bahkan siklus, atau kombinasi dari langkah-langkah ini. Algoritma "Menemukan semua sirkuit dasar dari grafik berarah" oleh Donald B. Johnson memiliki waktu berjalan polinomial yang diberikan oleh O ((n + e) ​​(c + 1)) di mana n adalah jumlah node, e jumlah tepi dan c jumlah sirkuit dasar dari grafik. Dan ini adalah implementasi Java saya untuk algoritma ini: github.com/1123/johnson .
user152468
4

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.

Rpant
sumber
2

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.

Steve
sumber
4
Itu tidak masuk akal. Jika grafik memiliki siklus, tidak ada pengurutan topologis, yang berarti algoritma yang tepat untuk pengurutan topologi akan dibatalkan.
sleske
4
dari wikipedia: Banyak algoritma penyortiran topologi akan mendeteksi siklus juga, karena itu adalah hambatan untuk tatanan topologi ada.
Oleg Mikheev
1
@ OlegMikheev Ya, tetapi Steve mengatakan "Jika jumlah itu kurang dari jumlah total simpul dalam DAG, Anda memiliki siklus", yang tidak masuk akal.
nbro
@nbro Saya berani bertaruh, itu berarti varian algoritma penyortiran topologi yang dibatalkan ketika tidak ada penyortiran topologis (dan kemudian mereka tidak mengunjungi semua simpul).
maaartinus
Jika Anda melakukan pengurutan topologi pada grafik dengan siklus, Anda akan mendapatkan urutan yang memiliki tepi buruk paling sedikit (nomor pesanan> nomor pesanan tetangga). Tetapi setelah Anda menyortirnya, mudah untuk mendeteksi tepi buruk yang mengakibatkan mendeteksi grafik dengan siklus
UGP
2

/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.

amitgoswami
sumber
1

Jika DFS menemukan tepi yang menunjuk ke titik yang sudah dikunjungi, Anda memiliki siklus di sana.

mafonya
sumber
1
Gagal 1,2,3: 1,2; 1,3; 2,3;
kucing berisik
4
@JakeGreene Lihat di sini: i.imgur.com/tEkM5xy.png Cukup sederhana untuk dipahami. Katakanlah Anda mulai dari 0. Kemudian Anda pergi ke node 1, tidak ada lagi jalur dari sana, reucrsion kembali. Sekarang Anda mengunjungi simpul 2, yang memiliki tepi ke simpul 1, yang sudah dikunjungi. Menurut pendapat Anda, Anda akan memiliki siklus pada saat itu - dan Anda tidak memiliki
kucing yang
3
@kittyPL Grafik itu tidak mengandung siklus. Dari Wikipedia: "Siklus terarah dalam grafik berarah adalah urutan titik mulai dan berakhir pada titik yang sama sehingga, untuk setiap dua titik berurutan dari siklus, ada tepi yang diarahkan dari titik awal ke titik berikutnya" Anda harus dapat mengikuti jalur dari V yang mengarah kembali ke V untuk siklus yang diarahkan. solusi mafonya bekerja untuk masalah yang diberikan
Jake Greene
2
@ JakeGreene Tentu saja tidak. Dengan menggunakan algoritma Anda dan mulai dari 1 Anda akan mendeteksi suatu siklus ... Algoritma ini hanya buruk ... Biasanya itu akan cukup untuk berjalan mundur setiap kali Anda menemukan titik dikunjungi.
kucing berisik
6
@kittyPL DFS berfungsi untuk mendeteksi siklus dari titik awal yang diberikan. Tetapi ketika melakukan DFS Anda harus mewarnai node yang dikunjungi untuk membedakan cross-edge dari back-edge. Pertama kali mengunjungi titik itu berubah menjadi abu-abu, kemudian Anda mengubahnya menjadi hitam setelah semua tepinya dikunjungi. Jika ketika melakukan DFS Anda menekan simpul abu-abu maka simpul itu adalah leluhur (yaitu: Anda memiliki siklus). Jika verteksnya hitam maka itu hanya cross-edge.
Kyrra
0

Seperti yang Anda katakan, Anda memiliki serangkaian pekerjaan, itu harus dieksekusi dalam urutan tertentu. Topological sortmemberi Anda pesanan yang diperlukan untuk penjadwalan pekerjaan (atau untuk masalah ketergantungan jika itu adalah direct acyclic graph). Jalankan dfsdan 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.

Bhagwati Malav
sumber
-11

Jika sebuah grafik memenuhi properti ini

|e| > |v| - 1

maka grafik mengandung setidaknya pada siklus.

Dharmendra Singh
sumber
10
Itu mungkin benar untuk grafik yang tidak diarahkan, tetapi tentu saja tidak untuk grafik yang diarahkan.
Hans-Peter Störr
6
Contoh penghitung adalah A-> B, B-> C, A-> C.
user152468
Tidak semua simpul memiliki tepi.
Debanjan Dhar