O método usado pelo DFS é, como o seu nome indica, procurar num grafo o mais profundo possível.

Pode ser definido da seguinte forma:

Algoritmo: marcam-se os nós do grafo para indicar em que medida é que já foram visitados. Para tal começa-se por marcar todos os nós como não tendo sido visitados (Brancos). Os nós que já foram vistos dividem-se em duas categorias: os que estão "em curso" (Verdes) e os que já foram inteiramente vistos (Vermelhos), ou seja, aqueles que se encontram a verde mas que já não tem mais adjacentes brancos.

O algoritmo pode ser implementado do seguinte modo:

1. void DFS (grafo G) {

2.     for (all v in G) {

3.         v -> color = branco;

4.         v -> p = null; }

5.     time = 0;

6.     for (all v in G)

7.         if (v -> color = = branco)

8.             DFS_Visit (v); }

9. void DFS_Visit (vértice v) {

10.     time = time+1;

11.     v -> color = verde;

12.     v -> d = time;

13.     for (all u in v -> adj)

14.         if (u -> color = = branco) {

15.             u -> p = v;

16.             DFS_Visit (u); }

17.     time = time+1;

18.     v -> color = vermelho;

19.     v -> f = time; }

O atributo d representa o tempo em que um nó foi visto pela primeira vez, isto é, a altura em que foi marcado a verde.

O atributo f representa o tempo em que o nó foi completamente visitado, neste caso isto significa que todos os seus descendentes foram vistos. Coincide com a altura  em que é marcado a vermelho.

As figuras que se seguem ilustram o progresso do algoritmo DFS no grafo que se segue. Este grafo tem como source o vértice I.

O source é o primeiro vértice a ser visitado. Ao ser visitado passa a verde o que quer dizer que o seu "tratamento" está em curso.

Vamos agora ver o estado dos seus adjacentes. Como Isó tem como adjacente o vértice E, e este se encontra a branco, será o próximo a ser tratado, passando então para verde.

Podemos agora verificar que E tem dois adjacentes e que os dois se encontram a branco. Qual dos dois será o próximo a ser tratado? Devemos adoptar uma convenção para faze-lo, neste caso optamos por percorrer os vértices por ordem alfabética. Assim sendo, o próximo vértice a ser tratado será o B, passando este também a verde.

Seguindo o "modo de visita" adoptado, vamos tratar o vértice A.

Neste passo "tratamos" o vértice C que, também ele, tem dois vértices adjacentes ainda a branco. Seguindo a mesma convenção segue-se o vértice D.

Tratamos agora o vértice D, que passa a verde.

Segue-se o vértice G.

Neste passo "tratamos" o vértice F que, como podemos verificar, não tem nenhum adjacente a branco. O que fazer agora?

Quando um vértice já não tem adjacentes a branco, este considera-se completamente tratado passando então para vermelho.

Neste momento já temos o vértice F completamente tratado, temos então que recuar para o vértice que foi visitado anteriormente. Neste caso foi o vértice G que como também já não tem adjacentes brancos passa também a vermelho.

Recuamos então até ao vértice D, mas D ainda tem um adjacente a branco o qual deverá ser tratado.

H também não tem adjacentes a branco, é então a altura de passar a vermelho.

Podemos agora verificar que já não existem vértices com adjacentes brancos. Agora temos sempre que ir recuando e tratar os vértices completamente, ou seja, eles vão passar a vermelho, até já não haverem vértices com o "tratamento em curso", isto é, a verde.

A ultima figura representa o grafo final depois de ser percorrido através do algoritmo de DFS.