Cel mai bun algoritm pentru detectarea ciclurilor într-un graf orientat

Tarjan's componente puternic conectate algoritmul a O(|E| + |V|) complexitate timp.

Pentru alți algoritmi, vezi componente Puternic conectate de pe Wikipedia.

Având în vedere că acesta este un program de locuri de muncă, cred că, la un moment dat aveți de gând să sort-le în ordinea propusă de execuție.

Dacă asta's caz, o topological sort punerea în aplicare poate, în orice caz detecta cicluri. UNIX tsort cu siguranță nu. Cred că este foarte probabil că acesta este, prin urmare, mai eficient pentru a detecta cicluri în același timp, ca tsorting, mai degrabă decât într-un pas separat.

Deci, întrebarea ar putea deveni, "cum am mai eficient tsort", mai degrabă decât "cum am mai eficient detecta buclele". La care răspunsul este, probabil, "utilizați o bibliotecă", dar nu că următorul articol Wikipedia:

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

a pseudo-cod pentru un algoritm, și o scurtă descriere a alt de Tarjan. Ambele au O(|V| + |E|) complexitate timp.

Începe cu un DFS: un ciclu există dacă și numai dacă o back-edge este descoperit în timpul DFS. Acest lucru este dovedit ca rezultat al alb-calea theorum.

Cel mai simplu mod de a face asta este de a do o adâncime prima traversare (DFT) din graph.

Dacă graful are n noduri, aceasta este o O(n) timp complexitatea algoritmului. Din moment ce va putea face un DFT pornind de la fiecare nod, total complexitatea devine O(n^2).

Trebuie să mențină un stack care conține toate nodurile în adâncimea actuală prima traversal, cu primul element fiind nodul rădăcină. Dacă întâlniți un element care este deja în stivă în timpul DFT, atunci ai un ciclu.

În opinia mea, cel mai ușor de înțeles algoritm pentru detectarea ciclu într-un graf orientat este grafic-colorat-algoritm.

Practic, graficul de colorat algoritmul merge grafic într-un DFS mod (Adâncime Prima Căutare, ceea ce înseamnă că explorează o cale complet înainte de a explora o altă cale). Atunci când se constată o înapoi margine, se marchează grafic ca conține o buclă.

Pentru o explicație în profunzime a graficului de colorat algoritm, vă rugăm să citiți acest articol: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

De asemenea, am oferi o implementare de grafic colorat în JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Dacă poți't a adăuga un "a vizitat" proprietate a nodurilor, utilizați un set (sau harta) și trebuie doar să adăugați vizitat toate nodurile la set, dacă nu sunt deja în set. Utilizați o cheie unică sau adresa de obiecte ca "cheie".

Acest lucru, de asemenea, vă oferă informații despre "rădăcină" nod al ciclic de dependență, care va veni la îndemână atunci când un utilizator are pentru a rezolva problema.

O altă soluție este de a încerca pentru a găsi următoarea dependență pentru a executa. Pentru aceasta, trebuie să aveți o stivă în cazul în care vă puteți aminti unde ești acum și ce trebuie să facă în continuare. Verificați dacă o dependență este deja pe această stivă înainte de a-l execute. Dacă e, te'am găsit un ciclu.

În timp ce acest lucru ar putea părea să aibă o complexitate de O(N*M), trebuie să vă amintiți-vă că stiva are o perioadă foarte limitată de adâncime (deci N este mic) și care M devine tot mai mic cu fiecare dependență pe care o puteți verifica pe ca "executat" în plus, puteți opri căutarea, atunci când ai găsit-o frunză (deci ai n trebuie să verificați fiecare nod -> M va fi mic, prea).

În MetaMake, am creat grafic ca o listă de liste și apoi șterse de fiecare nod ca nu i-a executat natural, care reduce volumul de căutare. N-am mai avut pentru a rula un control independent, totul s-a întâmplat în mod automat în timpul programului normal de execuție.

Dacă aveți nevoie de un "de testare numai" modul, trebuie doar să adăugați un "dry-run" pavilion care dezactivează executarea de locuri de muncă reale.

Potrivit Lema 22.11 de Cormen et al., Introduction să Algorithms (CLRS):

Un graf orientat G este aciclic dacă și numai dacă o adancime de căutare de G randamentele fara margini.

Acest lucru a fost menționat în mai multe răspunsuri; aici am'll oferi, de asemenea, un exemplu de cod bazat pe capitolul 22 din CLRS. De exemplu grafic este ilustrat mai jos.

CLRS' pseudo-cod pentru adancime de căutare prevede:

În exemplul din CLRS Figura 22.4, graficul este format din două DFS copaci: unul format din noduri u, v, x, și y, și alte noduri w și z. Fiecare copac conține unul c: unul din x să v și altul de la z să z (o auto-loop).

Cheia realizare este că marginea este întâlnită atunci când, în anii `DFS-VIZITA funcția, în timp ce iterarea peste vecinii " v "de la "u", un nod este întâmpinat cu " GRI " de culoare.

Următoarele cod Python este o adaptare a CLRS' pseudocod cu un "dacă" clauză adăugată care detectează cicluri:

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 discovered and 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, "timp" în CLRS' pseudocod nu este capturat pentru că ne-am're interesat doar în detectarea cicluri. Există, de asemenea, un cod șabloane pentru cladire adiacenta lista de reprezentare a unui grafic dintr-o listă de muchii.

Atunci când acest script este executat, se imprimă următoarele 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 în exemplul din CLRS Figura 22.4.

Nu există nici un algoritm care să poată găsi toate ciclurilor într-un graf orientat în timp polinomial. Să presupunem că, graf are n noduri și fiecare pereche de noduri are legături cu alte fiecare, ceea ce înseamnă că aveți o finaliza graficul. Deci, orice non-gol subset al acestor n noduri indică un ciclu și există 2^n-1 numărul de astfel de subseturi. Deci, nici un algoritm în timp polinomial există. Deci, să presupunem că aveți un mod eficient (non-prost) algoritm care pot să vă spun numărul de regia de cicluri într-un grafic, puteți găsi mai întâi puternice componente conectate, apoi aplicarea algoritmului pe aceste componente conectate. De cicluri există doar în componente și nu între ele.

Dacă DFS găsește un c care indică un deja-a vizitat vertex, ai un ciclu de acolo.

Am implementat această problemă în lms ( imperativ de programare) . Aici este o schiță . Găsi toate nodurile care au un indegree sau outdegree de 0 . Astfel de noduri nu poate fi parte dintr-un ciclu ( deci a le elimina ) . Următoarea elimina toate de intrare sau de ieșire marginile de astfel de noduri. Recursiv se aplică acest proces a rezultat grafic. Dacă la sfârșitul anului nu sunt lăsate cu orice nod sau o muchie , graful nu are cicluri , altceva nu are.

Modul în care am face este de a face o Sortare Topologică, de numărare numărul de noduri vizitate. Dacă acest număr este mai mic decât numărul total de noduri în DAG, ai un ciclu.

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

De asemenea, phys expertul spune că trebuie să faci O(V^2). Eu cred că avem nevoie doar de O(V)/O(V+E). Dacă graficul este conectat, atunci DFS va vizita toate nodurile. Dacă graficul are conectat sub grafice apoi de fiecare dată când vom rula un DFS pe un nod al acestei sub grafic vom găsi noduri conectate și au obiceiul să ia în considerare aceste pentru următorul termen de DFS. Prin urmare, posibilitatea de funcționare pentru fiecare vertex este incorectă.

Cum ai spus, ai pus de locuri de muncă, acesta trebuie să fie executate într-o anumită ordine. Topologice fel dat ordine necesar pentru programarea de locuri de muncă(sau pentru probleme de dependență, dacă acesta este direct graf aciclic). Ruladfs` și menține o listă, și începeți să adăugați nod la începutul listei, iar dacă ați avut un nod care este deja vizitat. Atunci ai gasit un ciclu în graf.

Dacă un grafic satisface această proprietate

|e| > |v| - 1

atunci graful contine cel putin pe ciclu.