Ciclo em Grafos por Profundidade

Programação Java
#1

Bem, estou com um pequeno problema : tenho que detectar se o grafo tem ou não ciclos, a partir de um vértice V.

Meu grafo é assim:

[code]public class Grafo {

listaVertices;
listaArestas;

}

public class Aresta{

    String rotulo;
    Vertice origem;
    Vertice destino;
    ....

}

public class Vertice{

    Object conteudo;
    boolean visitado;
    ...

}[/code]
bem, preciso detectar se o grafo tem ou não ciclos a partir de um vertice V pelo metodo public boolean contemCiclo(Vertice v)

Considerações :

não devo usar matrizes de adjacencia
o método deve ser por profundidade >> deve ser usado aqui algo como Backtracking (algoritmo recursivo)…

alguém possui o algoritmo ou algum link para a resolução definitiva?
já pesquisei aqui no GUJ e em outros forums, além do google, antes de mais nada.

Obrigado.

#2

Oi Breno,
Primeiramente, dê uma lida aqui: http://www.guj.com.br/posts/list/50115.java
Já corrigi a tag code p/ vc.

Quanto à sua dúvida, o algoritmo é simples.
Obtenha o vértice desejado.
Itere pelas suas arestas.
Se o vértice de destino da aresta for igual ao vértice escolhido, é pq existe ciclo. Caso contrário, pegue o vértice e chame novamente o mesmo método.

[]´s

#3

ajuda um pouco, mas ainda to tendo problemas…

seria melhor se pudesse usar matriz de adjacência, pois já vi milhares de algoritmos usando as matrizes, mas como não posso, já viu ne…

não há nenhum código ja pronto nao?

#4