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, direitaa, 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.

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

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 é não marcado então:

      visitar (v,w)      (i)

      P(w)

    senão

      se w pertence a Q e v,w não são consecutivos em Q então:

        visitar (v,w)     (ii)

  retirar v de Q



/* Procedimento Principal */

desmarcar todos os vértices

definir uma pilha Q

escolher uma raiz s

P(s)

Note que, no primeiro exemplo, utilizamos apenas (i) para realizar visitas nas arestas do grafo. Na realidade, o algoritmo acima divide as arestas do grafo G em dois conjuntos distintos:
as arestas visitadas em:
(i): arestas de árvore
(ii): arestas de retorno ou frondes

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 vértices

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 é não marcado então

      visitar (v,w)

      marcar w

      inserir w em Q

  caso contrário

    se w pertence a Q então 

      visitar (v,w)

  retirar v de Q

Coloração em Grafos

Árvore Geradora Máxima