Problemas com a detecção de ciclos…
Na verdade precisava de uma luz…
como fazer para detectar um ciclo em um grafo qualquer?
Agradeço a ajuda
Há um tempo implementei o algoritmo de Kruskal em C++.
Trata-se de um algoritmo capaz de calcular uma árvore geradora mínima de um grafo.
Apesar de não se tratar de um algoritmo para detectar ciclos propriamente dito, para gerar a árvore ele precisa, a cada passo, verificar se existe ciclo
antes de adicionar determinada aresta à árvore.
Uma busca no google code search deve retornar resultados interessantes.
Qualquer coisa tamo ae.
Não tenho a implementação do Kruskal, porém…
tenho de alguns outros algoritmos destes implementados…
porém não posso utilizá-los pois são ineficientes para o meu problema…
Resolvi o problema apenas verificando se um arco no grafo…
não está voltando para nós anteriores a ele…
desta forma elimino a ciclagem de maneira rápida…
mas de qualquer forma muito obrigado pela ajuda…
OLá balena, vc tem o algoritmo da sua proposta de solução? Tenho o mesmo problema, mas devo tomar certo cuidado com a performance.
depois de muitos testes acabei por descobrir que a solução que eu pensava ter encontrado…
na verdade não funciona para todos os casos, um ciclo não necessariamente volta para um nó anterior,
e sim retorna no sentido do grafo, meio complexo…
mas a maneira mais simples e rápida para encontrar o ciclo e eliminá-lo é inserindo o grafo em uma árvore…
depois de inserido podamos os nós folhas…
até que sobrem apenas os nós que determinam a existência de um ciclo…
para que haja um ciclo em um grafo é necessário que um nó consiga indicar dois caminhos…
sendo assim este nó nunca será podado na árvore, pois nunca chegará a ser folha…
Era assim que eu deveria ter resolvido, entretanto não terminei a solução…
não sabia utilizar a árvore do java.