Melhor algoritmo para detectar ciclos em um gráfico direcionado

396

Qual é 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 executados, um trabalho sendo um nó e uma dependência sendo uma aresta. Preciso detectar o caso de erro de um ciclo neste gráfico, levando a dependências cíclicas.

Peauters
fonte
13
Você diz que deseja detectar todos os ciclos, mas seu caso de uso sugere que seria suficiente detectar se há algum ciclo.
Steve Jessop
29
Seria melhor para detectar todos os ciclos, para que pudessem ser fixado de uma só vez, em vez de cheque, correção, verificação, correção etc.
Peauters
2
Você deve ler o artigo "Encontrar todos os circuitos elementares de um gráfico direcionado", de Donald B. Johnson. Ele encontrará apenas circuitos elementares, mas isso deve ser suficiente para o seu caso. E aqui está minha implementação Java deste algoritmo pronta para uso: github.com/1123/johnson
user152468
Execute o DFS com modificações adicionais para o algoritmo: marque cada nó que você visitou. se você visitar um nó que já foi visitado, terá um ciclo. quando você se retirar de um caminho, desmarque os nós visitados.
Hesham Yassin
2
@HeshamYassin, se você visitar um nó que já visitou, isso não significa necessariamente que há um loop. Por favor, leia meu comentário cs.stackexchange.com/questions/9676/… .
Maksim Dmitriev 15/01

Respostas:

193

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

Para outros algoritmos, consulte Componentes fortemente conectados na Wikipedia.

aku
fonte
69
Como encontrar os componentes fortemente conectados informa sobre os ciclos existentes no gráfico?
Peter
4
Pode ser que alguém possa confirmar, mas o algoritmo Tarjan não suporta ciclos de nós apontando diretamente para si mesmos, como A-> A.
Cédric Guillemette
24
@ Cedrik Certo, não diretamente. Esta não é uma falha no algoritmo de Tarjan, mas na maneira como é usada para esta questão. O Tarjan não encontra ciclos diretamente , encontra componentes fortemente conectados. Obviamente, qualquer SCC com tamanho maior que 1 implica um ciclo. Os componentes não cíclicos possuem um SCC único. O problema é que um auto-loop também entra no SCC por si só. Portanto, você precisa de uma verificação separada para auto-loops, o que é bastante trivial.
mgiuca 9/02/11
13
(todos os componentes fortemente ligados no gráfico) = (todos os ciclos no gráfico)!
optimusfrenk
4
@ aku: Um DFS de três cores também possui o mesmo tempo de execução O(|E| + |V|). Usando branco (nunca visitado), cinza (o nó atual é visitado, mas todos os nós alcançáveis ​​ainda não foram visitados) e preto (todos os nós alcançáveis ​​são visitados junto com o atual) codificação de cores, se um nó cinza encontrar outro nó cinza, então ' tenho um ciclo. [Praticamente o que temos no livro de algoritmos de Cormen]. Pensando se o 'algoritmo de Tarjan' tem algum benefício sobre esse DFS !!
KGhatak
73

Como esse é um cronograma de trabalhos, suspeito que, em algum momento, você os classifique em uma ordem de execução proposta.

Se for esse o caso, uma implementação de classificação topológica pode, em qualquer caso, detectar ciclos. O UNIX tsortcertamente faz. Eu acho que é provável que seja, portanto, mais eficiente detectar ciclos ao mesmo tempo que o tsorting, e não em uma etapa separada.

Portanto, a pergunta pode se tornar "como faço para tsort com mais eficiência", em vez de "como faço para detectar loops com mais eficiência". Para a qual a resposta provavelmente é "use a library", mas falhando no seguinte artigo da Wikipedia:

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

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

Steve Jessop
fonte
Uma classificação topológica pode detectar ciclos, na medida em que se baseia em um algoritmo de busca em profundidade, mas você precisa de contabilidade adicional para realmente detectar ciclos. Veja a resposta correta de Kurt Peek.
Luke Hutchison
33

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

Se o gráfico tiver nvértices, este é um O(n)algoritmo de complexidade de tempo. Como você possivelmente precisará executar uma DFT a partir de cada vértice, a complexidade total se tornará O(n^2).

É necessário manter uma pilha contendo todos os vértices no primeiro percurso de profundidade atual , com o primeiro elemento sendo o nó raiz. Se você se deparar com um elemento que já está na pilha durante a DFT, então você tem um ciclo.

nbro
fonte
21
Isso seria verdadeiro para um gráfico "regular", mas é falso para um gráfico direcionado . Por exemplo, considere o "diagrama de dependência de diamante" com quatro nós: A com arestas apontando para B e C, cada um com uma aresta apontando para D. Sua passagem por DFT deste diagrama de A concluiria incorretamente que o "loop" era na verdade, um ciclo - embora exista um loop, não é um ciclo porque não pode ser percorrido seguindo as setas.
Peter
9
@ Peter, você pode explicar como o DFT de A concluirá incorretamente que existe um ciclo?
Deepak
10
@ Deepak - Na verdade, eu li mal a resposta do "assistente físico": onde ele escreveu "na pilha" eu pensei "já foi encontrado". De fato, seria suficiente (para detectar um loop direcionado) verificar se há dupes "na pilha" durante a execução de um DFT. Um voto positivo para cada um de vocês.
Peter Peter
2
Por que você diz que a complexidade do tempo é O(n)sugerida para verificar a pilha para ver se ela já contém um nó visitado? A varredura da pilha adiciona tempo ao tempo de O(n)execução porque ela precisa varrer a pilha em cada novo nó. Você pode conseguir O(n)se marcar os nós visitados
James Wierzba 03/08
Como Peter disse, isso é incompleto para gráficos direcionados. Veja a resposta correta de Kurt Peek.
Luke Hutchison
32

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

Um gráfico direcionado G é acíclico se, e somente se, uma pesquisa profunda de G não produzir arestas posteriores.

Isso foi mencionado em várias respostas; aqui também fornecerei um exemplo de código baseado no capítulo 22 do CLRS. O gráfico de exemplo é ilustrado abaixo.

insira a descrição da imagem aqui

O pseudocódigo do CLRS para a pesquisa de profundidade é o seguinte:

insira a descrição da imagem aqui

No exemplo da Figura 22.4 do CLRS, o gráfico consiste em duas árvores DFS: uma que consiste nos nós u , v , x e y e a outra nos nós w e z . Cada árvore contém uma extremidade traseira: uma de x para ve outra de z para z (um auto-loop).

A principal conclusão é que uma borda traseira é encontrada quando, na DFS-VISITfunção, enquanto itera sobre os vizinhos vde u, um nó é encontrado com a GRAYcor.

O código Python a seguir é uma adaptação do pseudocódigo do CLRS com uma ifcláusula adicionada 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 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)

Observe que, neste exemplo, o timepseudocódigo do CLRS não é capturado porque estamos interessados ​​apenas em detectar ciclos. Há também algum código padrão para criar a representação da lista de adjacências de um gráfico a partir de uma lista de arestas.

Quando esse 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.

Essas são exatamente as arestas traseiras no exemplo da Figura 22.4 do CLRS.

Kurt Peek
fonte
29

Comece com um DFS: existe um ciclo se e somente se uma extremidade traseira for descoberta durante o DFS . Isso é provado como resultado do teorema do caminho branco.

Ajay Garg
fonte
3
Sim, eu acho que o mesmo, mas isso não é suficiente, eu postar meu caminho cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph
jonaprieto
Verdade. Ajay Garg está apenas falando sobre como encontrar "um ciclo", que é uma parte da resposta para esta pergunta. Seu link fala sobre encontrar todos os ciclos de acordo com a pergunta, mas novamente parece que ele usa a mesma abordagem que Ajay Garg, mas também faz todas as árvores dfs possíveis.
Manohar Reddy Poreddy 11/11/16
Isso está incompleto para gráficos direcionados. Veja a resposta correta de Kurt Peek.
Luke Hutchison
26

Na minha opinião, o algoritmo mais compreensível para detectar ciclo em um gráfico direcionado é o algoritmo de coloração de gráfico.

Basicamente, o algoritmo de coloração de gráfico percorre o gráfico de maneira DFS (Depth First Search, que significa que ele explora um caminho completamente antes de explorar outro caminho). Quando encontra uma aresta traseira, marca o gráfico como contendo um loop.

Para uma explicação detalhada do algoritmo de coloração de gráficos, leia este artigo: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Além disso, forneço uma implementação de coloração de gráfico no JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Armin Primadi
fonte
8

Se você não puder adicionar uma propriedade "visitada" aos nós, use um conjunto (ou mapa) e adicione todos os nós visitados ao conjunto, a menos que eles já estejam no conjunto. Use uma chave exclusiva ou o endereço dos objetos como a "chave".

Isso também fornece informações sobre o nó "raiz" da dependência cíclica, que será útil quando um usuário precisar corrigir o problema.

Outra solução é tentar encontrar a próxima dependência a ser executada. Para isso, você deve ter uma pilha onde possa lembrar onde está agora e o que precisa fazer a seguir. Verifique se já existe uma dependência nessa pilha antes de executá-la. Se for, você encontrou um ciclo.

Embora isso possa parecer ter uma complexidade de O (N * M), lembre-se de que a pilha tem uma profundidade muito limitada (portanto, N é pequena) e que M se torna menor a cada dependência que você pode marcar como "executado" mais você pode interromper a pesquisa quando encontrou uma folha (para nunca precisar verificar todos os nós -> M também será pequeno).

No MetaMake, criei o gráfico como uma lista de listas e, em seguida, excluí todos os nós enquanto os executava, o que naturalmente reduzia o volume de pesquisa. Na verdade, nunca tive que executar uma verificação independente, tudo aconteceu automaticamente durante a execução normal.

Se você precisar de um modo "somente teste", basta adicionar um sinalizador "execução a seco" que desativa a execução dos trabalhos reais.

Aaron Digulla
fonte
7

Não existe um algoritmo capaz de encontrar todos os ciclos em um gráfico direcionado em tempo polinomial. Suponha que o gráfico direcionado tenha nós e todos os pares tenham conexões entre si, o que significa que você possui um gráfico completo. Portanto, qualquer subconjunto não vazio desses nós indica um ciclo e há 2 ^ n-1 número desses subconjuntos. Portanto, não existe algoritmo de tempo polinomial. Portanto, suponha que você tenha um algoritmo eficiente (não estúpido) que pode lhe dizer o número de ciclos direcionados em um gráfico, você pode primeiro encontrar os componentes conectados fortes e, em seguida, aplicar seu algoritmo nesses componentes conectados. Como os ciclos existem apenas dentro dos componentes e não entre eles.

Yuwen
fonte
11
Verdadeiro, se o número de nós for considerado como o tamanho da entrada. Você também pode descrever a complexidade do tempo de execução em termos do número de arestas ou mesmo ciclos, ou uma combinação dessas medidas. O algoritmo "Encontrar todos os circuitos elementares de um gráfico direcionado" de Donald B. Johnson possui um tempo de execução polinomial dado por O ((n + e) ​​(c + 1)) em que n é o número de nós e o número de arestas ec o número de circuitos elementares do gráfico. E aqui está minha implementação em Java deste algoritmo: github.com/1123/johnson .
User152468
4

Eu havia implementado esse problema no sml (programação imperativa). Aqui está o esboço. Encontre todos os nós que possuem um grau indegree ou outdegree de 0. Esses nós não podem fazer parte de um ciclo (remova-os). Em seguida, remova todas as arestas de entrada ou saída desses nós. Aplique recursivamente esse processo ao gráfico resultante. Se no final você não tiver nenhum nó ou aresta, o gráfico não terá ciclos, caso contrário, ele terá.

Rpant
fonte
2

O jeito que eu faço é fazer uma Classificação Topológica, contando o número de vértices visitados. Se esse número for menor que o número total de vértices no DAG, você terá um ciclo.

Steve
fonte
4
Isso não faz sentido. Se o gráfico tiver ciclos, não haverá classificação topológica, o que significa que qualquer algoritmo correto para classificação topológica será interrompido.
sleske 30/09/09
4
da wikipedia: Muitos algoritmos de classificação topológica também detectam ciclos, pois esses são obstáculos para a ordem topológica.
precisa saber é o seguinte
11
@OlegMikheev Sim, mas Steve está dizendo "Se esse número for menor que o número total de vértices no DAG, você tem um ciclo", o que não faz sentido.
Nbro 28/07
@ nbro Eu aposto que eles significam uma variante do algoritmo de classificação topológica que aborta quando não existe uma classificação topológica (e eles não visitam todos os vértices).
maaartinus 11/09
Se você fizer uma classificação topológica em um gráfico com ciclo, você terminará com um pedido com a menor quantidade de arestas incorretas (número do pedido> número do pedido do vizinho). Mas depois que você tem que a triagem é fácil de detectar as bordas ruins resultantes na detecção de um gráfico com um ciclo
UGP
2

/mathpro/16393/finding-a-cycle-of-fixed-length Eu gosto desta solução, a melhor, especialmente para 4 comprimentos :)

Também phys wizard diz que você tem que fazer O (V ^ 2). Acredito que precisamos apenas de O (V) / O (V + E). Se o gráfico estiver conectado, o DFS visitará todos os nós. Se o gráfico tiver conectado subgráficos, toda vez que executarmos um DFS em um vértice desse subgrafo, encontraremos os vértices conectados e não precisaremos considerá-los para a próxima execução do DFS. Portanto, a possibilidade de execução para cada vértice está incorreta.

amitgoswami
fonte
1

Se o DFS encontrar uma aresta que aponte para um vértice já visitado, você terá um ciclo lá.

mafonya
fonte
11
Falha em 1,2,3: 1,2; 1,3; 2,3;
gato barulhento
4
@JakeGreene Veja aqui: i.imgur.com/tEkM5xy.png Simples o suficiente para entender. Digamos que você comece a partir de 0. Então você vai para o nó 1, não há mais caminhos a partir daí, a reucessão volta. Agora você visita o nó 2, que possui uma borda para o vértice 1, que já foi visitado. Na sua opinião, você teria um ciclo na época - e você realmente não tem um
barulhento gato
3
@kittyPL Esse gráfico não contém um ciclo. Da Wikipedia: "Um ciclo direcionado em um gráfico direcionado é uma sequência de vértices iniciando e terminando no mesmo vértice, de modo que, para cada dois vértices consecutivos do ciclo, exista uma aresta direcionada do vértice anterior para o posterior" precisa seguir um caminho de V que leva de volta a V para um ciclo direcionado. A solução da mafonya trabalha para o problema dado
Jake Greene
2
@JakeGreene Claro que não. Usando seu algoritmo e começando de 1, você detectaria um ciclo de qualquer maneira ... Esse algoritmo é ruim ... Normalmente, seria suficiente voltar atrás sempre que você encontrar um vértice visitado.
gato barulhento
6
@kittyPL O DFS trabalha para detectar ciclos do nó inicial especificado. Porém, ao executar o DFS, você deve colorir os nós visitados para distinguir uma borda da borda da borda traseira. Quando visita um vértice pela primeira vez, ele fica cinza e depois você fica preto quando todas as suas bordas são visitadas. Se, ao fazer o DFS, você atingir um vértice cinza, esse vértice é um ancestral (ou seja: você tem um ciclo). Se o vértice for preto, será apenas uma borda cruzada.
Kyrra
0

Como você disse, você tem um conjunto de trabalhos, ele precisa ser executado em certa ordem. Topological sortdado o pedido necessário para agendamento de trabalhos (ou para problemas de dependência, se for um direct acyclic graph). Execute dfse mantenha uma lista e comece a adicionar um nó no início da lista e se você encontrou um nó que já foi visitado. Então você encontrou um ciclo em determinado gráfico.

Bhagwati Malav
fonte
-11

Se um gráfico satisfazer esta propriedade

|e| > |v| - 1

então o gráfico contém pelo menos no ciclo.

dharmendra singh
fonte
10
Isso pode ser verdade para gráficos não direcionados, mas certamente não para gráficos direcionados.
Hans-Peter Störr
6
Um exemplo contrário seria A-> B, B-> C, A-> C.
user152468
Nem todos os vértices têm arestas.
Debanjan Dhar