Teoria Dos Grafos

 Busca em profundidade

O algoritmo DFS (Depth-First Search) realiza uma busca que progride através da expansão do primeiro nó (o nó raiz) e se aprofunda cada vez mais, até que o alvo seja encontrado, ou até que se depare com um nó folha, daí a busca retrocede (backtrack) e recomeça no próximo nó.

Representação gráfica de uma busca DFS

O método DFS

O algoritmo para busca em profundidade marca v (raiz) como visitado; A seguir toma o vértice w conectado a v, verifica se w é solução:

• Se sim, encerra a busca (e indica a solução que pode ser somente este nó ou todo o percurso do nó-raiz até este nó);

• Se não, continua a DFS em w;

Terminando busca em w, o algoritmo toma outro vértice z conectado a v ainda não visitado e executa a busca, se o nó for a solução, encerra o algoritmo e devolve a solução, caso contrário prossegue, desta forma, sucessivamente.

Propriedades da busca DFS

• Efeito backtrack.

• Formação de uma pilha.

• A complexidade temporal é O(V + E).

• Busca infinita.

Aplicações da busca DFS

• Busca de articulação

• Ordenação topológica

• Identificação de componentes fortemente conexos

Busca de articulação - Aplicações DFS

Um vértice em um grafo não direcionado simples e conexo é uma articulação se sua remoção torna o grafo resultante desconexo.

Exemplo de articulação

Importante, por exemplo, para identificar os pontos frágeis de uma rede de computadores.

 Busca em Largura

O algoritmo BFS (Breadth-First Search)expande e examina sistematicamente todos os nós de uma árvore através de níveis, em busca de uma solução.

Representação gráfica de uma busca BFS

O Método BFS

O algoritmo para busca em largura marca v (raiz) como visitado;

A seguir toma todos os vértices (filhos) conectados a v, verificando se cada um deles é solução:

• Se sim, encerra a busca no respectivo nó e indica a solução;

• Se não, continua a BFS nos filhos dos filhos;

Terminando busca nos filhos dos filhos, o algoritmo toma os filhos dos filhos dos filhos e executa a busca até que encerra o algoritmo ou devolva a solução.