Duplicar Possível:
Melhor algoritmo para detectar ciclos em um grafo direcionado
Eu estou procurando um algoritmo para encontrar loops em um grafo direcionado.
Meu gráfico tem rótulos apenas nos nós, não nas bordas e pode ficar muito grande.
A saída do algoritmo deve ser os loopscomo um conjunto de listas, cada lista deve conter os rótulos dos nós envolvidos em um loop, portanto, o primeiro e o último elemento da lista devem ser os mesmos.
Os gráficos que estou usando provavelmente terão apenas um componente conectado e nenhum componente fortemente conectado. Espera-se que o número de ciclos seja baixo (eu ainda tenho que verificar isso).
Qualquer bom algoritmo para exatamente isso ou algo semelhante é bem-vindo.
Muito obrigado.
PS: Se algo não está claro, fique à vontade para me perguntar mais detalhes, por exemplo, o gráfico é armazenado (até agora) como um conjunto de conjuntos de arestas, de um nó para vários nós, geralmente um, isso deve ser irrelevante, IMHO.
Respostas:
1 para resposta № 1Uma pergunta semelhante foi feita e alguém forneceu uma resposta muito detalhada que pode ajudá-lo - Encontrando todos os ciclos em um grafo direcionado