Melhor algoritmo para detectar ciclos em um grafo orientado

Question

O que é o algoritmo mais eficiente para detectar todos os ciclos em um gráfico direcionado?

Eu tenho um gráfico direcionado representando uma agenda de trabalhos que precisam ser executadas, um trabalho que é um nó e uma dependência sendo uma vantagem. Preciso para detectar o caso de erro de um ciclo dentro deste gráfico levando a dependências cíclicos.

Answer 1

de Tarjan componentes fortemente conectados algoritmo tem complexidade de tempo O(|E| + |V|).

Para outros algoritmos, consulte fortemente ligado na Wikipedia.

Answer 2

Dado que esta é uma agenda de trabalhos, eu suspeito que em algum momento você vai tipo -los em uma proposta de ordem de execução.

Se for esse o caso, então um topológica tipo implementação pode em qualquer caso, detectar ciclos. UNIX tsort certamente faz. Eu acho que é provável que, portanto, é mais eficiente para detectar ciclos, ao mesmo tempo que tsorting, em vez de em uma etapa separada.

Portanto, a questão pode tornar-se, "como é que eu mais eficiente tsort", em vez de "como faço mais eficiente detectar loops". Para que a resposta provavelmente é "usar uma biblioteca", mas não que o artigo Wikipedia seguinte:

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

tem o pseudo-código para um algoritmo, e uma breve descrição de uma outra de Tarjan. Ambos têm complexidade de tempo O(|V| + |E|).

Answer 3

Comece com uma DFS: existe um ciclo se e somente se um back-edge é descoberto durante DFS . Isto é provado como resultado de theorum branco-path.

Answer 4

A maneira mais simples de fazer isso é a fazer uma profundidade primeira travessia (DFT) do gráfico .

Se o gráfico tem vértices n, este é um algoritmo de complexidade de tempo O(n). Desde que você vai, eventualmente, ter de fazer um DFT a partir de cada vértice, a complexidade total de torna-se O(n^2).

Você tem que manter um pilha contendo todos os vértices na profundidade atual primeira travessia , com o seu primeiro elemento é o nó de raiz. Se você se deparar com um elemento que já está na pilha durante o DFT, então você tem um ciclo.

Answer 5

Na minha opinião, o algoritmo mais compreensível para a detecção de ciclo em um grafo dirigido é the-coloração de grafos-algoritmo.

Basicamente, o gráfico colorem o algoritmo anda o gráfico de uma maneira DFS (busca em profundidade, o que significa que explora um caminho completamente antes de explorar um outro caminho). Quando se encontra uma extremidade traseira, que marca o gráfico como contendo um laço.

Para uma explicação em profundidade do algoritmo da coloração gráfico, por favor, leia este artigo: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Além disso, eu fornecer uma implementação de coloração de grafos em JavaScript https: / /github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Answer 6

Se você não pode adicionar uma propriedade "visitada" para os nós, use um conjunto (ou mapear) e apenas adicionar todos os nós visitadas ao conjunto a menos que já no conjunto são. Use uma chave única ou o endereço dos objetos como a "chave".

Isto também lhe dá a informação sobre o nó "raiz" da dependência cíclica, que virá a calhar quando um usuário tem para corrigir o problema.

Outra solução é tentar encontrar o próximo dependência para executar. Para isso, você deve ter alguma pilha, onde você pode se lembrar onde você está agora eo que você precisa fazer a seguir. Verifique se uma dependência já está nesta pilha antes de executá-lo. Se for, você encontrou um ciclo.

Embora isso possa parecer ter uma complexidade de O (N * M) é preciso lembrar que a pilha tem uma profundidade muito limitado (de modo N é pequeno) e que M torna-se menor com cada dependência que você pode marcar como " executado" além disso, você pode parar a busca quando encontrou uma folha (assim você não tem que verificar cada nó -> M será pequeno, também).

Em MetaMake, criei o gráfico como uma lista de listas e, em seguida, eliminado cada nó como eu executá-los que, naturalmente, reduzir o volume de pesquisa. Eu nunca realmente tive que executar uma verificação independente, tudo aconteceu automaticamente durante a execução normal.

Se você precisa de um "único teste" modo, basta adicionar uma bandeira "run-seca" que desativa a execução dos trabalhos reais.

Answer 7

Não existe algoritmo que pode encontrar todos os ciclos em um grafo dirigido em tempo polinomial. Suponha-se, o grafo orientado tem n nós e cada par dos nós tem conexões com o outro o que significa que têm um gráfico completo. Assim, qualquer subconjunto não vazio desses nós n indica um ciclo e existem duas ^ n-1 número de tais subconjuntos. Portanto, não algoritmo de tempo polinomial existe. Então, suponha que você tenha um algoritmo eficiente (não estúpido) que pode dizer-lhe o número de ciclos dirigidos em um gráfico, você pode primeiro encontrar as fortes componentes conectados, em seguida, aplicar o seu algoritmo sobre esses componentes conectados. Desde ciclos só existem dentro dos componentes e não entre eles.

Answer 8

Se DFS encontra uma borda que aponta para um vértice já visitado, você tem um ciclo lá.

Answer 9

De acordo com o Lema 22.11 de Cormen et al, Introdução aos Algoritmos (CLRS):.

Um gráfico G é acíclico dirigido se e somente se uma busca em profundidade de G não produz extremidades traseiras.

Este foi mencionado em várias respostas; aqui eu também vou dar um exemplo de código baseado em capítulo 22 de CLRS. O gráfico exemplo é ilustrado abaixo.

pseudo-código 'CLRS para busca em profundidade lê-se:

No exemplo em CLRS Figura 22.4, o gráfico é composto por duas árvores DFS: um constituído por nodos u , v , x , e y , e o outro dos nós w e Z . Cada árvore contém borda uma volta: um de x e v e outro de z e z (a auto loop).

A realização chave é que a borda traseira é encontrado quando, na função DFS-VISIT, enquanto a iteração sobre os vizinhos v de u, um nó é encontrado com a cor GRAY.

O seguinte código Python é uma adaptação do pseudocódigo 'CLRS com uma cláusula if acrescentou que detecta ciclos:

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)

Note que, neste exemplo, o time em pseudocódigo 'CLRS não é capturado, porque estamos interessados ??apenas na detecção de ciclos. Há também algum código clichê para a construção da representação lista de adjacência de um gráfico a partir de uma lista de bordas.

Quando este script é executado, ele imprime a seguinte saída:

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

Estas são exactamente as arestas traseiras no exemplo em CLRS Figura 22.4.

Answer 10

A forma como eu fazer isso é fazer uma topológica Sort, contando o número de vértices visitados. Se esse número for menor do que o número total de vértices no DAG, você tem um ciclo.

Answer 11

Eu tinha implementado este problema na LME (programação imperativa). Aqui está o esboço. Localizar todos os nós que quer ter um indegree ou outdegree de 0. Tais nódulos não pode ser parte de um ciclo (de modo removê-los). Em seguida remover todas as arestas de entrada ou saída de tais nós. Recursivamente aplicar este processo para o gráfico resultante. Se no final você não fica com qualquer nó ou aresta, o gráfico não tem nenhum ciclos, então ele tem.

Answer 12

https://mathoverflow.net/questions/16393/finding-a-cycle -de-fixa de comprimento I como esta solução a melhor especialmente para 4 comprimento:)

Além disso Phys assistente diz u tem que fazer O (V ^ 2). Eu acredito que precisamos apenas O (V) / O (V + E). Se o gráfico está ligado, em seguida, DFS vai visitar todos os nós. Se o gráfico se conectou sub gráficos, em seguida, cada vez que executar um DFS em um vértice deste sub gráfico vamos encontrar os vértices conectados e não terá de considerar estes para a próxima corrida do DFS. Portanto, a possibilidade de correr para cada vértice está incorreto.

Answer 13

Como você disse, você tem um conjunto de postos de trabalho, ele precisa ser executado em determinada ordem. Topological sort dado necessário para que a programação dos postos de trabalho (ou por problemas de dependência, se é um direct acyclic graph). Execute dfs e manter uma lista e começar a adicionar nó no início da lista, e se você encontrou um nó que já é visitado. Então você encontrou um ciclo em dado grafo.

Answer 14

Se um gráfico satisfazer esta propriedade

|e| > |v| - 1

, em seguida, o gráfico contém, pelo menos, em ciclo.