A pesquisa em profundidade inicia a travessia de um gráfico em um vértice arbitrário, marcando-o como visitado. Em cada iteração, o algoritmo prossegue para um vértice não visitado que é adjacente àquele em que está atualmente. (Se houver vários desses vértices, um empate pode ser resolvido arbitrariamente. Como uma questão prática, qual dos candidatos adjacentes não visitados é escolhido é ditado pela estrutura de dados que representa o gráfico. Em nossos exemplos, sempre quebramos os laços pela ordem alfabética dos vértices.) Esse processo continua até um beco sem saída - um vértice sem vértices adjacentes não visitados encontrados. Em um beco sem saída, o algoritmo faz o backup de uma aresta até o vértice de onde veio e tenta continuar visitando os vértices não visitados de lá. O algoritmo eventualmente para após retornar ao vértice inicial, sendo o último um beco sem saída. Até então, todos os vértices no mesmo componente conectado que o vértice inicial foram visitados. Se os vértices não visitados ainda permanecerem, a pesquisa em profundidade deve ser reiniciada em qualquer um deles.