Busca em Grafos

Busca em grafos:

Raiz da busca:

Considere o grafo que se segue:

São apresentados a seguir dois algoritmos básicos de busca, em grafos:

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)

  1. buscaEmProfundidade(Q:Lista,v)
  2.     G.marcar(v)
  3.     Q.adicionaNoInício(v)
  4.     para  w Î G.adjacentes(v)
  5.         se G.marcado(w) então
  6.             se w Î Q  e v, w não são
                               consecutivos em Q então
  7.                 visitar(v,w) ...
  8.             fim se
  9.         senão
  10.             visitar(v,w) ...
  11.             buscaEmProfundidade(Q, w)
  12.          fim se
  13.     fim para
  14.     Q.removePrimeiro
  15. fim

Busca em Largura:
Dados:
  • um grafo G(V,A) conexo, e
  • a raiz da busca, um vértice qualquer r ÎV(G)
  1. F ¬ Lista.com(r)
  2. G.marcar(r)
  3. enquanto F  ¹ f
  4.     v ¬ F.primeiro
  5.     para  w Î G.adjacentes(v)
  6.         se G.marcado(w) então
  7.             se w Î F então
  8.                 visitar(v,w) ...
  9.             fim se
  10.         senão
  11.             visitar(v,w) ...
  12.             G.marcar(w)
  13.             F.adicionaNoFim(w)
  14.          fim se
  15.     fim para
  16.     F.removePrimeiro
  17. fim enquanto

Voltar