Busca em Profundidade

Ludmila Maciel R. Souza
Lorrane Idevic

você vai aprender

- Definições da Busca em Profundidade em um Grafo (G =V, E)

- Tempos de Marcação

- Classificação das Arestas

pré requisitos

Noções em Projeto de Algoritmos

Noções em Recursividade

definições

- Todos os vértices iniciam BRANCOS.

- Quando um vértice é visitado pela primeira vez, o mesmo passa para AZUL.

- Quando todos os seus adjacentes são visitados (todos são azuis), então ele passa para VERMELHO.

TEMPOS DE MARCAÇÃO

- Tempo de Descoberta (TD): Momento em que o vértice é marcado como

AZUL.

- Tempo de Término (TT): Momento em que o vértice é marcado como

VERMELHO.

classificação das arestas

Arestas são classificadas de acordo com a "marcação" (branco, azul ou vermelho) de cada vértice, informando-nos sobre ciclos ali existentes ou, na maioria das vezes, grafos direcionados ou não.

Árvore: É a aresta que liga um vértice azul a um branco.

Retorno: É a aresta que liga um vértice azul ou vermelho a um azul ou vermelho.

Avanço: É a aresta que liga um vértice ao seu adjacente, sendo que o tempo de descoberta do vértice deve ser MAIOR do que o tempo de descoberta do seu vértice adjacente.

Cruzamento: É a aresta que liga um vértice ao seu adjacente, sendo que o tempo de descoberta do vértice deve ser MENOR do que o tempo de descoberta do seu vértice adjacente.