Algoritmo de buscam em profundidade - DFS §

---

A Busca em Profundidade, ou DFS (Depth-First Search), é um algoritmo para percorrer ou pesquisar em um grafo.

A ideia central do DFS é explorar o mais “fundo” possível ao longo de cada ramo antes de retroceder (o que é chamado de backtracking).

Algoritmo §

Este algoritmo, em sua essência, é um processo recursivo e o seu funcionamento a partir de um vértice u segue estes passos:

1. Atinge um Vértice: A busca atingiu em um vértice u.
2. Escolhe um Vizinho: A partir de u, o algoritmo procura por um vizinho v que ainda não tenha sido visitado.
3. Aprofunda Recursivamente: Assim que um vizinho v não visitado é encontrado, a busca em profundidade é chamada recursivamente para começar a partir de v.
4. Retorna da Recursão: Quando a busca recursiva que começou em v termina (ou seja, explorou todos os caminhos possíveis a partir de v), o algoritmo retorna para o vértice u.
5. Tenta Outro Vizinho: De volta a u, o algoritmo tenta encontrar outro vizinho que ainda não foi visitado para repetir o processo.
6. Retrocede (Backtracking): Se não houver mais vizinhos não visitados a partir de u, a busca a partir de u é considerada completa. O algoritmo então retorna ao nível anterior da recursão (o vértice que o levou a u), um processo conhecido como backtracking.

Mecanismo de Controle (Cores) §

Para controlar quais vértices já foram visitados, o algoritmo utiliza um sistema de três cores:

• BRANCO: O vértice ainda não foi descoberto.
• CINZA: O vértice foi descoberto, mas está aguardado encerrar a visita em todos os seus descendentes.
• PRETO: O vértice e todos os seus descendentes já foram completamente explorados.

Classificação de Arestas §

Os arcos de retorno (back), avanço (forward) e cruzado (cross) são classificações dadas às arestas de um grafo durante a execução de uma Busca em Profundidade (DFS).

Arco de Retorno (Back Edge) §

É um arco que conecta um vértice a um de seus ancestrais.

Note

A presença de um arco de retorno indica a existência de um ciclo no grafo.

Arco de Avanço (Forward Edge) §

É um arco que conecta um vértice a um de seus descendentes, mas que não é uma aresta do caminho principal.

Arco Cruzado (Cross Edge) §

É um arco que conecta dois vértices que não têm relação de ancestralidade (não são nem ancestrais nem descendentes um do outro).

Implementação §

Referências §

---

Teoria dos grafos - Subgrafos, passeios, trilhas e caminhos