Necessito de um algoritmo básico para busca de profundidade em grafos, alguém pode me ajudar.
Você não especificou exatamente que tipo de grafo, mas aí vai um exemplo.
Busca em Profundidade:
Dados:
um grafo G(V,A) conexo, e
a raiz da busca, um vértice qualquer r ÎV(G)
buscaEmProfundidade(Lista.nova, r)
buscaEmProfundidade(Q:Lista,v)
G.marcar(v)
Q.adicionaNoInício(v)
para w Î G.adjacentes(v)
se G.marcado(w) então
se w Î Q e v, w não são
consecutivos em Q então
visitar(v,w) ...
fim se
senão
buscaEmProfundidade(Q, w)
fim para
Q.removePrimeiro
fim
Comments
Você não especificou exatamente que tipo de grafo, mas aí vai um exemplo.
Busca em Profundidade:
Dados:
um grafo G(V,A) conexo, e
a raiz da busca, um vértice qualquer r ÎV(G)
buscaEmProfundidade(Lista.nova, r)
buscaEmProfundidade(Q:Lista,v)
G.marcar(v)
Q.adicionaNoInício(v)
para w Î G.adjacentes(v)
se G.marcado(w) então
se w Î Q e v, w não são
consecutivos em Q então
visitar(v,w) ...
fim se
senão
visitar(v,w) ...
buscaEmProfundidade(Q, w)
fim se
fim para
Q.removePrimeiro
fim