Dado um grafo, deseja-se obter um processo matemático de como caminhar pelos vértices e arestas do mesmo. Se o grafo é uma árvore, esta questão se torna simples, podem utilizar as visitas em pré-ordem, ou ordem de nível, por
Exemplo:

pré-ordem: a b d e i j c f k g h l m
ordem de nível: a b c d e f g h i j k l m n

Quando se transporta o problema para grafos, uma dificuldade surge imediatamente: não há um referencial geral a ser considerado, ou seja, não são definidos conceitos de esquerda, direita, nível. Surgem as seguintes perguntas:

1. como caminhar no grafo de modo a visitar todos os vértices e arestas, evitando contudo repetições desnecessárias ?
2. como definir um caminhamento sistemático no grafo, de modo que fique determinado qual o vértice a ser visitado na sequência de visitas.

Algoritmo Básico para Buscas
Seja G um grafo no qual todos os vértices estão inicialmente desmarcados.

No passo inicial, marca-se um vértice escolhido arbitrariamente.
No passo geral, seleciona-se um vértice v que esteja marcado, e não seja incidente a alguma aresta (v,w) ainda não selecionado.

A aresta (v,w) torna-se selecionado, e o vértice w marcado (caso ainda não o seja). O processo termina quando todas as arestas de G tiverem sido selecionadas.

Quando a aresta (v,w) é selecionada a partir de v, dizemos que (v,w) foi explorado quando todas as arestas incidentes a ele tiverem sido exploradas.
Note que durante o processo de exploração de um vértice, é possível que ele seja alcançado diversas vezes (tantas quantas forem o número de arestas incidentes). O vértice inicial chama-se raiz da busca.
Durante o processo de busca, temos liberdade de escolha:

Passo inicial: seleção da raiz
Passo geral:

• vértice marcado: podemos escolher qual vértice marcado v, a partir do qual se visitará uma aresta
• aresta incidente: qual aresta incidente ao vértice será explorada

Na busca geral, essas escolhas são arbitrárias
Nos critérios de busca em profundidade, e busca em largura, que veremos a seguir, a escolha do próximo vértice torna-se única, mas para os casos do vértice inicial e aresta incidente, a escolha permanece arbitrária.

Busca em profundidade
Dentre todos os vértices marcados e incidentes a alguma aresta ainda não explorada, escolher aquela mais recentemente alcançada na busca.

Algoritmo: Busca em Profundidade

dados: G(V,E) conexo
procedimento P(v)
  marcar v
  colocar v na pilha Q
  para w pertencente a A(v) efetuar /* A(v): lista de adj de v */
    se w e nao marcado entao:
      visitar (v,w)      (i)
      P(w)
    senao
      se w pertence a Q e v,w nao sao consecutivos em Q entao:
	visitar (v,w)     (ii)
  retirar v de Q

/* Procedimento Principal */
desmarcar todos os vertices
definir uma pilha Q
escolher uma raiz s
P(s)

Exemplo:

Seja Et o conjunto das arestas da árvore. Sobre este conjunto, temos os seguintes resultados:

• o grafo T(V,Et) é uma árvore geradora de G(V,E).
• seja G(V,E) um grafo conexo e T uma árvore de profundidade, então toda aresta (v,w) pertencente a E é tal que v é ancestral (ou descendente) de w em T.
• seja G(V,E) um grafo conexo e T(V,Et) uma árvore de profundidade de G, então todo caminho c de G contém um vértice p tal que todos os vértices de c são descendentes de P em T.

Busca em Profundidade - Dígrafos

Algoritmo:

dados: dígrafo D(v)
Procedimento P(v)
  marcar v
  colocar v na pilha Q
  para w pertencente a A(v) efetuar
    visitar (v,w)
    se w nao marcado entao P(w)
      retirar v de Q

/* programa principal */
desmarcar todos os vertices
definir uma pilha Q
definir uma raiz se V
P(s)

Note que a pilha Q pode ser ignorada no algoritmo sem modificar a essência do procedimento.

Exemplo:

Busca em Largura
Dentre todos os vértices marcados e incidentes a alguma aresta ainda não explorada, escolher aquele menos recentemente alcançado na busca.

Algoritmo:

dados: G(V,E)
desmarcar todos os vertices
escolher uma raiz s pertencente a V
definir uma filha Q, vazia
marcar s
inserir s em Q
enquanto Q for diferente de 0 efetuar  /* diferente de vazio  */
  seja v o primeiro elemento de Q
  para w pertencente a A(v) efetuar
    se w e nao marcado entao
      visitar (v,w)
      marcar w
      inserir w em Q
  caso contrario
    se w pertence a Q entao 
      visitar (v,w)
  retirar v de Q

Exemplo:

Coloração em Grafos

Árvore Geradora Máxima