Introdução

Um algoritmo de busca é um algoritmo que passa por todos os vértices e todos os arcos de um digrafo.

Cada arco é visitado apenas uma só vez. Depois de visitar a a origem de um arco, o algoritmo percorre o arco e visita seu destino.

Existem muitos algoritmos de busca, cada um possui uma estratégia específica que é caracterizada pela ordem que os vértices são visitados.

Diremos que o k-ésimo vértice visitado durante a busca tem número de ordem k-1 .
Trataremos aqui da busca em profundidade (= depth-first search - DFS). A busca em profundidade está relacionada com conceitos como backtracking, varredura de árvore em pré-ordem.
(Esta parte corresponde aproximadamente às seções 18.1 (Exploring a Maze) e 18.2 (Depth-First Search) do capítulo 18 (Graph Search) do livro de Sedgewick.)

A DFS em si

A função dfs abaixo realiza a estrutura geral de uma busca em profundidade.

//Autor: Filipe Areias Névola
//Ano: 2009
//Licensa: Você pode usar e alterar, mas deve manter o Autor

#define MAXV 100 //número máximo de vértices

int G[MAXV][MAXV]; //grafo representado por matriz de adjacência
int visitado[MAXV]; //se for 1 vértice já visitado, caso contrário 0. Começa com 0 em todas as posições
int n; //número de vértices neste grafo

//Busca em profundidade a partir de um vértice origem
//vértices estão númerados de 0 até n-1
void dfsDigrafo(){
   int v;
   
   for(v = 0; v < n; ++v) //ninguém foi visitado
      visitado[v] = 0;
   
   for(v = 0; v < n; ++v){ //roda todos os vértices
      if( visitado[v] == 0 ){ //se ainda não foi visitado
         dfs(v); //faz a busca para esse vértice
      }
   }
}

void dfs(int origem){ 

  int v = origem; //vértice atual
  visitado[v] = 1; //origem está visitada

  for(int i = 0; i < n; ++i){ //rodar todas as possíveis arestas de v       
    if (G[v][i] == 1 && visitado[i] == 0){ //existe aresta e ainda não visitou          
      //Faz aqui o que quiser antes da chamada recursiva...          
      dfs(i); //visita esse vértice          
      //Faz aqui o que quiser após o retorno do backtracking       
    }    
  } 
}

Referências: IME