Cel mai bun algoritm pentru detectarea ciclurilor într-un graf dirijat [închis] (Programare, Algoritm, Teoria Grafurilor, Graf Dirijat)

Peauters a intrebat.

Care este cel mai eficient algoritm pentru detectarea tuturor ciclurilor dintr-un graf dirijat?

Am un graf dirijat care reprezintă un program de lucrări care trebuie executate, o lucrare fiind un nod și o dependență fiind o muchie. Trebuie să detectez cazul de eroare al unui ciclu în cadrul acestui graf care duce la dependențe ciclice.

Comentarii

  • Spuneți că doriți să detectați toate ciclurile, dar cazul de utilizare sugerează că ar fi suficient să detectați dacă există cicluri. –  > Por Steve Jessop.
  • 32

  • Ar fi mai bine să se detecteze toate ciclurile, astfel încât acestea să poată fi reparate dintr-o singură dată, în loc să se verifice, să se repare, să se repare, să se verifice, să se repare etc. –  > Por Peauters.
  • Ar trebui să citiți lucrarea „Finding all the elementary circuits of a directed graph” de Donald B. Johnson. Acesta va găsi numai circuite elementare, dar acest lucru ar trebui să fie suficient pentru cazul dumneavoastră. Și iată implementarea mea Java a acestui algoritm, gata de utilizare: github.com/1123/johnson –  > Por user152468.
  • Rulați DFS cu o modificare suplimentară pentru algoritm: marcați fiecare nod pe care l-ați vizitat. dacă vizitați un nod care este deja vizitat, atunci aveți un ciclu. când vă retrageți de pe o cale, debifați nodurile vizitate. –  > Por Hesham Yassin.
  • @HeshamYassin, dacă vizitezi un nod pe care l-ai vizitat deja, nu înseamnă neapărat că există o buclă. Vă rog să citiți comentariul meu cs.stackexchange.com/questions/9676/…. –  > Por Maksim Dmitriev.
14 răspunsuri
aku

Algoritmul componentelor puternic conectate al lui Tarjan are O(|E| + |V|) complexitate în timp.

Pentru alți algoritmi, consultați Componente puternic conectate pe Wikipedia.

Comentarii

    74

  • Ce ne spune găsirea componentelor puternic conectate despre ciclurile care există în graf? –  > Por Peter.
  • Poate că cineva poate confirma, dar algoritmul Tarjan nu acceptă cicluri de noduri care arată direct spre ele însele, cum ar fi A->A. –  > Por Cédric Guillemette.
  • 26

  • @Cedrik Corect, nu direct. Acesta nu este un defect al algoritmului Tarjan, ci modul în care este folosit pentru această întrebare. Tarjan nu găsește direct cicluri, ci găsește componente puternic conectate. Desigur, orice SCC cu o dimensiune mai mare de 1 implică un ciclu. Componentele neciclice au de la sine un SCC singleton. Problema este că o buclă proprie va intra, de asemenea, într-o SCC de sine stătătoare. Așadar, aveți nevoie de o verificare separată pentru buclele proprii, ceea ce este destul de banal. –  > Por mgiuca.
  • 16

  • (toate componentele puternic conectate din graf) != (toate ciclurile din graf) – –  > Por optimusfrenk.
  • @ aku : Un DFS cu trei culori are, de asemenea, același timp de execuție O(|E| + |V|). Folosind coduri de culoare alb (niciodată vizitat), gri (nodul curent este vizitat, dar toate nodurile accesibile nu sunt încă vizitate) și negru (toate nodurile accesibile sunt vizitate împreună cu cel curent), dacă un nod gri găsește un alt nod gri, atunci avem un ciclu. [Cam ceea ce avem în cartea de algoritmi a lui Cormen]. Mă întreb dacă „Algoritmul lui Tarjan” are vreun avantaj față de un astfel de DFS!!! –  > Por KGhatak.
Steve Jessop

Având în vedere că acesta este un program de lucrări, bănuiesc că la un moment dat veți avea de gând să să sortați într-o ordine de execuție propusă.

În acest caz, atunci un sortare topologică ar putea în orice caz să detecteze cicluri. UNIX tsort cu siguranță o face. Cred că este probabil că, prin urmare, este mai eficient să se detecteze ciclurile în același timp cu sortarea, decât într-o etapă separată.

Așadar, întrebarea ar putea deveni „cum să sortez cel mai eficient”, mai degrabă decât „cum să detectez cel mai eficient buclele”. La care răspunsul este, probabil, „utilizați o bibliotecă”, dar, în caz contrar, următorul articol din Wikipedia:

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

conține pseudo-codul pentru un algoritm și o scurtă descriere a altui algoritm de la Tarjan. Ambele au O(|V| + |E|) complexitate în timp.

Comentarii

  • O sortare topologică poate detecta cicluri, în măsura în care se bazează pe un algoritm de căutare în profunzime, dar aveți nevoie de o evidență suplimentară pentru a detecta efectiv ciclurile. Vezi răspunsul corect al lui Kurt Peek. –  > Por Luke Hutchison.
Kurt Peek

În conformitate cu lema 22.11 din Cormen et al., Introduction to Algorithms (CLRS):

Un graf dirijat G este aciclic dacă și numai dacă o căutare în profunzime a lui G nu produce muchii de întoarcere.

Acest lucru a fost menționat în mai multe răspunsuri; aici voi oferi și un exemplu de cod bazat pe capitolul 22 din CLRS. Graful de exemplu este ilustrat mai jos.

Pseudo-codul CLRS pentru căutarea în profunzime este următorul:

În exemplul din figura 22.4 din CLRS, graful este format din doi arbori DFS: unul format din noduri u, , v, , x, , și y, iar cealaltă de noduri w și z. Fiecare arbore conține câte o muchie de întoarcere: una de la x către v și o alta de la z la z (o buclă proprie).

Realizarea cheie este că o muchie din spate este întâlnită atunci când, în DFS-VISIT în timpul iterației peste vecinii v a u, , se întâlnește un nod cu valoarea GRAY culoare.

Următorul cod Python este o adaptare a pseudocodului CLRS cu o funcție if s-a adăugat o clauză care detectează ciclurile:

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)

Rețineți că în acest exemplu, clauza time din pseudocodul CLRS nu este capturat, deoarece ne interesează doar detectarea ciclurilor. Există, de asemenea, un cod boilerplate pentru construirea reprezentării listei de adiacență a unui graf dintr-o listă de muchii.

Atunci când acest script este executat, el tipărește următoarea ieșire:

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

Acestea sunt exact marginile din spate din exemplul din Figura 22.4. CLRS.

Comentarii

  • Se obține RecursionError: maximum recursion depth exceeded while calling a Python object pentru acest cod. –  > Por zino.
  • @zino Se pare că ar trebui să existe un break după ce ciclul este detectat. Am încercat să o adaug, dar coada de editare este plină. –  > Por A_P.
Expertul în fizică

Cel mai simplu mod de a face acest lucru este să efectuați o traversare în profunzime (DFT) a graficului.

În cazul în care graficul are n vârfuri, aceasta este o O(n) algoritm de complexitate în timp. Deoarece este posibil să trebuiască să efectuați un DFT pornind de la fiecare vertex, complexitatea totală devine O(n^2).

Trebuie să mențineți un stivă care să conțină toate vârfurile din traversarea curentă a primei adâncimi, , primul său element fiind nodul rădăcină. Dacă în timpul DFT întâlniți un element care se află deja în stivă, atunci aveți un ciclu.

Comentarii

    24

  • Acest lucru ar fi adevărat pentru un graf „obișnuit”, dar este fals pentru un graf „obișnuit”. direcționat dirijat. De exemplu, luați în considerare „diagrama de dependență în formă de diamant” cu patru noduri: A cu muchii care indică spre B și C, fiecare dintre acestea având o muchie care indică spre D. Traversarea DFT a acestei diagrame de la A ar concluziona în mod incorect că „bucla” este de fapt un ciclu – deși există o buclă, nu este un ciclu, deoarece nu poate fi traversată urmând săgețile. –  > Por Peter.
  • @peter puteți să explicați cum DFT din A va concluziona în mod incorect că există un ciclu? –  > Por Deepak.
  • @Deepak – De fapt, am interpretat greșit răspunsul de la „phys wizard”: unde a scris „în stivă” am crezut că „a fost deja găsit”. Într-adevăr, ar fi suficient (pentru a detecta o buclă dirijată) să se verifice dacă există dubluri „în stivă” în timpul executării unei DFT. Un upvote pentru fiecare dintre voi. –  > Por Peter.
  • De ce spuneți că complexitatea în timp este O(n) în timp ce sugerați verificarea stivei pentru a vedea dacă aceasta conține deja un nod vizitat? Scanarea stivei adaugă timp la O(n) timpul de execuție, deoarece trebuie să scaneze stiva la fiecare nod nou. Puteți obține O(n) dacă marcați nodurile vizitate –  > Por James Wierzba.
  • După cum a spus Peter, acest lucru este incomplet pentru grafurile direcționate. Consultați răspunsul corect al lui Kurt Peek. –  > Por Luke Hutchison.
Armin Primadi

În opinia mea, cel mai ușor de înțeles algoritm pentru detectarea ciclului într-un graf direcționat este algoritmul de colorare a grafurilor.

Practic, algoritmul de colorare a grafurilor parcurge graful într-o manieră DFS (Depth First Search, ceea ce înseamnă că explorează complet o cale înainte de a explora o altă cale). Atunci când găsește o muchie de întoarcere, acesta marchează graficul ca fiind o buclă.

Pentru o explicație detaliată a algoritmului de colorare a grafurilor, vă rugăm să citiți acest articol: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

De asemenea, ofer o implementare a colorării grafurilor în JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Ajay Garg

Începeți cu un DFS: un ciclu există dacă și numai dacă există a este descoperită o muchie din spate în timpul DFS. Acest lucru este demonstrat ca rezultat al teoriei drumului alb.

Comentarii

  • Da, cred același lucru, dar acest lucru nu este suficient, am postat calea mea cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph –  > Por jonaprieto.
  • Adevărat. Ajay Garg spune doar despre cum să găsești „un ciclu”, care este un răspuns parțial pentru această întrebare. Link-ul dvs. vorbește despre găsirea tuturor ciclurilor, conform întrebării adresate, dar, din nou, se pare că folosește aceeași abordare ca Ajay Garg, dar face și toate arborii dfs-trees posibile. –  > Por Manohar Reddy Poreddy.
  • Acest lucru este incomplet pentru grafurile direcționate. Consultați răspunsul corect al lui Kurt Peek. –  > Por Luke Hutchison.
  • Nu răspunde la o întrebare, o întrebare cere o soluție pentru a găsi toate ciclurile –  > Por sia.
Aaron Digulla

Dacă nu puteți adăuga o proprietate „vizitat” la noduri, folosiți un set (sau o hartă) și adăugați toate nodurile vizitate la set, cu excepția cazului în care acestea se află deja în set. Utilizați o cheie unică sau adresa obiectelor ca „cheie”.

Acest lucru vă oferă, de asemenea, informații despre nodul „rădăcină” al dependenței ciclice, ceea ce va fi util atunci când un utilizator trebuie să rezolve problema.

O altă soluție este să încercați să găsiți următoarea dependență care trebuie executată. Pentru aceasta, trebuie să aveți o stivă în care să vă amintiți unde vă aflați acum și ce trebuie să faceți în continuare. Verificați dacă o dependență se află deja pe această stivă înainte de a o executa. Dacă este, înseamnă că ați găsit un ciclu.

Deși acest lucru ar putea părea a avea o complexitate de O(N*M), trebuie să vă amintiți că stiva are o adâncime foarte limitată (deci N este mic) și că M devine mai mic cu fiecare dependență pe care o puteți bifa ca fiind „executată”, plus că puteți opri căutarea atunci când ați găsit o frunză (astfel încât să niciodată trebuie să verificați fiecare nod -> M va fi și el mic).

În MetaMake, am creat graficul ca o listă de liste și apoi am șters fiecare nod pe măsură ce le executam, ceea ce a redus în mod natural volumul de căutare. De fapt, nu a trebuit niciodată să efectuez o verificare independentă, totul s-a întâmplat automat în timpul execuției normale.

Dacă aveți nevoie de un mod „doar pentru testare”, adăugați doar un indicator „dry-run” care dezactivează execuția lucrărilor efective.

Yuwen

Nu există niciun algoritm care să poată găsi toate ciclurile dintr-un graf direcționat în timp polinomial. Să presupunem că graful direcționat are n noduri și că fiecare pereche de noduri are conexiuni între ele, ceea ce înseamnă că avem un graf complet. Astfel, orice subansamblu nevid al acestor n noduri indică un ciclu și există un număr 2^n-1 de astfel de subansambluri. Prin urmare, nu există niciun algoritm în timp polinomial. Presupunând că aveți un algoritm eficient (care să nu fie stupid) care vă poate spune numărul de cicluri direcționate dintr-un graf, puteți găsi mai întâi componentele puternic conectate, apoi să aplicați algoritmul dumneavoastră pe aceste componente conectate. Deoarece ciclurile există doar în interiorul componentelor și nu între ele.

Comentarii

  • Adevărat, dacă numărul de noduri este luat ca dimensiune a datelor de intrare. De asemenea, ați putea descrie complexitatea timpului de execuție în funcție de numărul de muchii sau chiar de cicluri, sau o combinație a acestor măsuri. Algoritmul „Finding all the elementary circuits of a directed graph” de Donald B. Johnson are un timp de execuție polinomial dat de O((n + e)(c + 1)) unde n este numărul de noduri, e numărul de muchii și c numărul de circuite elementare ale grafului. Iată și implementarea mea Java a acestui algoritm: github.com/1123/johnson. –  > Por user152468.
Rpant

Am implementat această problemă în sml ( programare imperativă) . Iată care este schița . Găsiți toate nodurile care fie au un indegree sau outdegree de 0 . Astfel de noduri nu pot face parte dintr-un ciclu ( deci eliminați-le ) . Apoi eliminați toate marginile de intrare sau de ieșire de la astfel de noduri.Aplicați recursiv acest proces la graful rezultat. Dacă la sfârșit nu rămâne niciun nod sau muchie , graful nu are cicluri , altfel are.

Steve

Modul în care procedez eu este să fac o sortare topologică, numărând numărul de vârfuri vizitate. Dacă acest număr este mai mic decât numărul total de vârfuri din DAG, înseamnă că aveți un ciclu.

Comentarii

  • Acest lucru nu are sens. Dacă graful are cicluri, nu există sortare topologică, ceea ce înseamnă că orice algoritm corect de sortare topologică va eșua. –  > Por sleske.
  • de pe wikipedia: Mulți algoritmi de sortare topologică vor detecta și ciclurile, deoarece acestea sunt obstacole pentru ca ordinea topologică să existe. –  > Por Oleg Mikheev.
  • @OlegMikheev Da, dar Steve spune: „Dacă acest număr este mai mic decât numărul total de vârfuri din DAG, aveți un ciclu”, ceea ce nu are sens. –  > Por nbro.
  • @nbro Aș paria, ei se referă la o variantă a algoritmului de sortare topologică care avortează atunci când nu există o sortare topologică (și atunci nu vizitează toate vârfurile). –  > Por maaartinus.
  • Dacă faci o sortare topologică pe un graf cu ciclu vei ajunge la o ordine care are cea mai mică cantitate de muchii proaste(numărul de ordine > numărul de ordine al vecinului). Dar după ce ați făcut sortarea este ușor de detectat acele muchii rele, ceea ce duce la detectarea unui graf cu ciclu –  > Por Plagon.
amitgoswami

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Îmi place cel mai mult această soluție, în special pentru 4 lungimi:)

De asemenea, phys wizard spune că trebuie să faci O(V^2). Eu cred că avem nevoie doar de O(V)/O(V+E). Dacă graful este conectat, atunci DFS va vizita toate nodurile. Dacă graful are subgrafi conectați, atunci de fiecare dată când executăm un DFS pe un vârf al acestui subgrafic vom găsi vârfurile conectate și nu va trebui să le luăm în considerare la următoarea execuție a DFS. Prin urmare, posibilitatea de a rula pentru fiecare verigă este incorectă.

mafonya

Dacă DFS găsește o muchie care indică un vertex deja vizitat, atunci aveți un ciclu acolo.

Comentarii

  • Nu reușește la 1,2,3: 1,2; 1,3; 2,3; –  > Por pisica zgomotoasă.
  • @JakeGreene Uită-te aici: i.imgur.com/tEkM5xy.png Destul de simplu pentru a înțelege. Să zicem că pornești de la 0. Apoi mergi la nodul 1, nu mai există alte căi de acolo, reuccesiunea se întoarce. Acum vizitați nodul 2, care are o muchie către vertexul 1, care a fost deja vizitat. După părerea dumneavoastră, atunci ați avea un ciclu – și nu aveți niciunul.  > Por pisica zgomotoasă.
  • @kittyPL Graficul respectiv nu conține un ciclu. Din Wikipedia: „Un ciclu dirijat într-un graf dirijat este o secvență de vârfuri care începe și se termină la același vârf astfel încât, pentru fiecare două vârfuri consecutive ale ciclului, există o muchie dirijată de la primul vârf la cel din urmă.” Pentru un ciclu dirijat trebuie să poți urma o cale din V care să ducă înapoi la V. Soluția lui mafonya funcționează pentru problema dată –  > Por Jake Greene.
  • @JakeGreene Bineînțeles că nu. Folosind algoritmul tău și pornind de la 1, ai detecta oricum un ciclu… Acest algoritm este pur și simplu prost… De obicei ar fi suficient să mergi înapoi de fiecare dată când întâlnești un vertex vizitat. –  > Por pisica zgomotoasă.
  • @kittyPL DFS funcționează pentru a detecta ciclurile de la nodul de pornire dat. Dar atunci când faceți DFS trebuie să colorați nodurile vizitate pentru a distinge o muchie încrucișată de o muchie din spate. Prima dată când se vizitează un vertex, acesta se transformă în gri, apoi se transformă în negru după ce toate marginile sale au fost vizitate. Dacă în timpul DFS atingeți un vertex gri, atunci acel vertex este un strămoș (adică aveți un ciclu). Dacă vertexul este negru, atunci este doar o muchie încrucișată. –  > Por Kyrra.
Bhagwati Malav

După cum ați spus, aveți un set de sarcini, care trebuie executate într-o anumită ordine. Topological sort dată fiind ordinea necesară pentru programarea lucrărilor (sau pentru probleme de dependență, dacă este vorba de o direct acyclic graph). Rulați dfs și mențineți o listă, și începeți să adăugați nod la începutul listei și dacă ați întâlnit un nod care este deja vizitat. Atunci ați găsit un ciclu în graficul dat.

dharmendra singh

Dacă un graf satisface această proprietate

|e| > |v| - 1

atunci graful conține cel puțin un ciclu.

Comentarii

  • Acest lucru ar putea fi adevărat pentru grafurile nedirecționate, dar cu siguranță nu și pentru grafurile direcționate. –  > Por Hans-Peter Störr.
  • Un contraexemplu ar fi A->B, B->C, A->C. –  > Por utilizator152468.
  • Nu toate vârfurile au muchii. –  > Por Debanjan Dhar.