Busca em Profundidade

Grafos: Busca

SCE-183 Algoritmos e Estruturas de Dados 2

Thiago A. S. Pardo
Maria Cristina

Percorrendo um grafo
Percorrendo um Grafo


Percorrer um grafo é um problema fundamental



Deve-se ter uma forma sistemática de visitar as arestas e os vértices



O algoritmo deve ser suficientemente flexível para se adequar à diversidade de grafos
2

Eficiência
Percorrendo um Grafo


Eficiência


Não deve haver repetições (desnecessárias) de visitas a um vértice e/ou aresta

3

Correção
Percorrendo um Grafo


Correção


Todos os vértices e/ou arestas devem ser visitados

4

Solução
Percorrendo um Grafo


Solução


Marcar os vértices




não visitados visitados processados

5

Solução
Percorrendo um Grafo


Solução


Manter uma lista de vértices no estado visitados



Há duas possibilidades



Busca em largura (usando uma fila)
Busca em profundidade (usando uma pilha)

6

BFS (Busca em Largura)
Percorrendo um Grafo


BFS – Breadth-First Search


Todos os nós com distância k a um nó v são visitados antes dos nós com distância k+1



Descobre todos os vértices alcançáveis a partir de v

7

BFS – exemplo
Percorrendo um Grafo: BFS
2

3

1
4

6

5
8

BFS – exemplo
Percorrendo um Grafo: BFS
2

3

1
4

6
Nó inicial: 1

5
9

BFS – exemplo
Percorrendo um Grafo: BFS
2

3

K=1

1
4

6

5

Visitam-se todos os nós não visitados adjacentes a 1: 2, 5 e 6

10

BFS – exemplo
Percorrendo um Grafo: BFS
2

3

K=2

1
4

6

5

Visitam-se todos os nós não visitados adjacentes a 2: 3

11

BFS – exemplo
Percorrendo um Grafo: BFS
2

3

K=2

1
4

6

5

Visitam-se todos os nós não visitados adjacentes a 5: 4

12

BFS – exemplo
Percorrendo um Grafo: BFS
2

3

K=2

1
4

6

5

Visitam-se todos os nós não visitados adjacentes a 6: nenhum

13

BFS – exemplo