aula11

Teoria dos Grafos
Aula 11 - Busca em Largura
Erika Morais [e-mail] Instituto de Informática
Universidade Federal de Goiás

Representação de grafos
Lista de Adjacência
A lista de adjacências de um grafo G = (V , E ) consiste em um arranjo Adj. de |V | listas, uma para cada vértice em V . Para cada u ∈ V , a lista de adjacências Adj[u] contém todos os vértices v tais que existe uma aresta (u, v ) ∈ E .

Exemplo:
1
•

2
•
3
•

•
5

•
4✄

✄
Adj[1] → ✂2 ✁→ ✂5 ✁

✄ ✄
Adj[2]
✄ ✄→ ✂1 ✁→ ✂5 ✁→
✂3 ✁→ ✂4 ✁✄ ✄
Adj[3] → ✂2 ✁→ ✂4 ✁
✄ ✄
Adj[4]
→
✂2 ✁→ ✂5 ✁→
✄
3
✂ ✁
✄ ✄
✄Adj[5]
→ ✂4 ✁→ ✂1 ✁→
✂2 ✁

Busca em largura
◮

A Busca em largura é um dos algoritmos mais simples para se pesquisar em um grafo.

Ideia:
◮

Dado um grafo G = (V , E ) e um vértice de origem distinta s, a busca em largura explora sistematicamente as arestas de G até “descobrir” cada vértice acessível a partir de s.

◮

O algoritmo calcula a distância (menor número de arestas) desde s até todos os vértices acessíveis desse tipo.

◮

O algoritmo produz uma “árvore primeiro na extensão” com raiz s que contém todos os vértices acessíveis.

◮

Para qualquer vértice v acessível a partir de s, o caminho na árvore primeiro na extensão de s até v corresponde a um
“caminho mais curto” de s até v em G .

Busca em largura

O nome
◮

A busca recebe este nome porque expande a fronteira entre vértices descobertos e não descobertos uniformemente ao longo da extensão da fronteira.

◮

Descobre todos os vértices à distância k a partir de s, antes de descobrir quaisquer vértices à distância k + 1.

Busca em Largura

Esquema de cores
Os vértices serão pintados de branco, cinza ou preto, para controlar o andamento da busca.
◮

Branco: Um vértice será pintado de branco, quando ele ainda não foi descoberto/encontrado durante a pesquisa.

◮

Cinza: Um vértice que já foi visitado, mas pode conter vértice vizinho de cor branca. Estes vértices representam a fronteira entre vértices descobertos e