Discreta Aula 6

14/11/2014

Busca em Largura
• Descobre todos os vértices à distância k a partir de um vértice de origem s, antes de descobrir quaisquer vértices à distância k + 1
• Controle da Busca:

Aula 6:
Busca em Grafos

– BRANCO = vértice NÃO descoberto
– CINZA = vértice descoberto dentro da FILA
– PRETO = vértice descoberto removido da FILA

Prof. Rodrigo Clemente Thom de Souza

• Tempo de Execução: O(V+E)
1

Resumo
• Algoritmos de Busca
– Busca em Largura
– Busca em Profundidade
– Aplicações de Algoritmos de Busca

Busca em Largura (Algoritmo)
1. Pintar todos os vértices de BRANCO
2. Pintar de CINZA um vértice qualquer
(colocando-o na FILA)
3. Enquanto FILA ≠ Ø faça:
3.1

• Ordenação Topológica

Pintar de PRETO o vértice v da frente da
FILA (removendo-o da FILA)
Para toda aresta (v, w), tal que w é BRANCO
(isto é, w ainda não foi descoberto), pinte w de CINZA (colocando-o na FILA)

3.2

Algoritmos de Busca em Grafos
• Acompanham sistematicamente as arestas do grafo de modo a alcançar todos seus vértices
– Busca em Largura
– Busca em Profundidade

Busca em Largura (Exemplo)
1

2
3

1

1
4

5

2
3

1

2

1

5

5

5

2

3

5

3
4

3

5
4
5

4
4

5

4

5

2

1

3
4

2
3

2

1
4

3
1

4

4

3

5

1

2

2

1

1
4

2
3

3
1

4

3

2

2
3

1

5
4

5

4

5

2
3

1

14/11/2014

Busca em Largura (Exercício)

Busca em Profundidade (Exemplo)
1

2
3

1

1
4

5

2
3

1

3
1

4

5

2

4
2
1

2
4

3
1

4
2

1

Busca em Profundidade

5

2
3

7

4

2
1
4

5

3
1

4

3

4

1

4

5

2
3

1

2
1
4

5

4

5

4

5

2
1

5
3
4
2
1

2

4
2
1

2
3

5
4
2
1

1
3

5
5
4
2
1

2

1

3
1

5

2
3

Busca em Profundidade (Exercício)

• As arestas são percorridas a partir do vértice mais recentemente descoberto que ainda possua vértices não descobertos vizinhos a ele
• Controle da Busca:
– BRANCO = vértice NÃO descoberto
– CINZA = vértice descoberto dentro da PILHA
– PRETO = vértice descoberto removido da PILHA

• Tempo de Execução: Θ(V+E)
11

Busca em Profundidade (Algoritmo)
1. Pintar todos os vértices