Busca em Grafos
Katia S. Guimarães
[email protected]
1
Busca em Grafos
OBJETIVO:
Visitar todos os vértices e arestas do grafo
de forma sistemática, para evitar repetições e
conseqüente desperdício.
Se o grafo é uma árvore enraizada, isto é,
uma árvore na qual os vértices obedecem a
uma hierarquia, a tarefa é simples.
[email protected]
2
Busca em Árvores Enraizadas
1. Busca em pré-ordem
Raiz visitada antes
dos descendentes
A B C E F
D
[email protected]
3
Busca em Árvores Enraizadas
2. Busca em pós-ordem
Raiz visitada depois
dos descendentes
B E F C D
A
[email protected]
4
Busca em Árvores Enraizadas
3. Busca em in-ordem
Raiz é visitada entre os descendentes
Só faz sentido para árvores binárias ou
similares (2-3, B, etc.)
(Applet)
[email protected]
5
Algoritmo Pré-ordem
Algoritmo Pré-ordem(raiz)
Se raiz não nula então
Visite (raiz)
Pré-ordem (left.raiz)
Pré-ordem (right.raiz)
[email protected]
6
Algoritmo Pós-ordem
Algoritmo Pós-ordem(raiz)
Se raiz não nula então
Pós-ordem (left.raiz)
Pós-ordem (right.raiz)
Visite (raiz)
[email protected]
7
Algoritmo In-ordem
Algoritmo In-ordem(raiz)
Se raiz não nula então
In-ordem (left.raiz)
Visite (raiz)
In-ordem (right.raiz)
[email protected]
8
Busca em Grafos com Ciclos
Se o grafo contém ciclos, é preciso cuidar
para evitar que arestas sejam visitadas
mais de uma vez.
5
6
1
3
7
4
2
[email protected]
9
Busca em Grafos com Ciclos
Exemplo: A partir do grafo abaixo obtemos
5
6
1
1
3
7
4
6
4
2
2
3
7
[email protected]
5
10
Busca em Grafos com Ciclos
Se o grafo não é uma árvore, nós definimos
um subgrafo dele que é uma árvore, para
servir de “espinha dorsal”.
Algoritmo básico:
– Tome um vértice qualquer s. Marque s.
– Enquanto houver arestas não visitadas, tome uma
aresta (v, w) incidente a algum vértice já marcado.
Marque (v, w) (explorada) e v, w (visitados).
[email protected]
11
Busca em Grafos com Ciclos
Há duas técnicas principais para busca:
– Busca em Profundidade
Tomar a aresta não marcada incidente ao
vértice visitado mais recentemente.
– Busca em Largura
Tomar a aresta não marcada incidente ao
vértice visitado menos recentemente.
[email protected]
12
Busca em Profundidade
JAVA Applet para uma
Busca em Profundidade
JAVA Applet para Busca em
grafo direcionado com pilha
[email protected]
13
Controle para
Busca em Profundidade
Main Procedure
Inicialize pilha Q como vazia;
Desmarque todos os vértices e arestas;
Tome um vértice v qualquer;
Inclua v em Q;
P(v);
Remova v de Q.
14
Algoritmo para Busca em Profundidade
Procedimento P(v)
Marque v como visitado (cinza);
Para toda aresta (v, w) incidente a v faça:
Se w não marcado então
/* aresta de árvore */ {d[w] time; time++;
pred[w]  v; P(w)
fim[w] time; time++}
senão se w  pai(v)
então /* aresta de retorno */
senão /* aresta de árvore */
[email protected]
15
Árvore de Busca em Profundidade
A busca em profundidade biparticiona o
conjunto de arestas em:
1
5
6
4
6
1
3
4
2
7
2
- Arestas
de Árvore
- Arestas
de Retorno
3
7
5
16
Teorema 23.6 (Teorema dos parênteses)
Em qualquer busca em profundidade de um
grafo (direcionado ou não direcionado) G =
(V, E), para quaisquer dois vértices u e v,
exatamente uma das três condições vale:
- Os intervalos [d[u],f[u]] e [d[v], f[v]] são
disjuntos,
- O intervalo [d[u],f[u]] está contido no
intervalo [d[v],f[v]], e u é um descendente de v
na árvore de busca em profundidade, ou
- Vice-versa.
17
Corolário 23.7
(Nesting dos intervalos dos descendentes)
Vértice v é um descendente próprio do vértice
u na floresta de busca em profundidade de
um grafo G sse d[u] < d[v] < f[v] < f[u].
18
Variações de Busca em Profundidade
O algoritmo de Busca em Profundidade
é usado como controle para muitas
aplicações em tempo linear.
1
Ex. Componentes Biconexos
(Tolerância a falhas em redes)
4
6
Ex: No grafo ao lado, os seguintes subgrafos
gerados permanecem conexos se cair um
link qualquer:
G{1, 6}
G{3, 7}
G{1, 2, 3, 4, 5}
[email protected]
2
3
7
5
19
Busca em Largura
Cria um centro no vértice inicial e forma
“níveis” ou “camadas” a partir deste nó.
1
5
6
1
4
6
3
5
7
4
2
3
2
7
20
Vértices Brancos, Cinza e Pretos
- Brancos – Valor inicial
- Cinza – Após serem descobertos
- Pretos – Após a descoberta de todos os adjacentes.
s
1
1
4
6
2
5
3
7
s
1
6
4
6
2
5
3
7
6
s
4
2
5
3
7
21
Busca em Largura
Applet para Busca em Largura
22
Algoritmo para Busca em Largura
Tome um vértice qualquer v. Coloque v na fila F.
Enquanto F não for vazia faça
v  Primeiro elemento da fila F
Para toda aresta (v, w) incidente a v faça
Se w não marcado então
Inclua w em F /* aresta de árvore */
senão se v = pai (w)
então /* aresta de árvore */
senão /* aresta de cruzamento */
23
Ao término de Busca em Largura
A busca em largura biparticiona as arestas do
grafo em arestas de árvore e arestas de
cruzamento.
1
5
6
3
4
2
4
6
1
7
2
5
3
7
24
Correção de Busca em Largura (BL)
Teorema 23.4 (Correção de BL)
Seja G = (V, E) um grafo direcionado ou não
direcionado, e suponha que o algoritmo BL é
executado em G a partir de um dado vértive s
 V. Então, durante a sua execução, BL
descobre todo vértice v  V alcançável a partir
do nó fonte s, e ao término,
d[v] = distância (s, v) para todo v  V
...
25
Busca em Largura vs. Distâncias
Teorema 23.4 (Correção de Busca em Largura)
......
Além disso, para qualquer vértice v <> s
alcançável a partir de s, um dos menores
caminhos de compr. mínimo de s a v é o
caminho de s a pred(v) seguido pela aresta
(pred(v), v).
26
Variações de Busca em Largura
O algoritmo de Busca em Largura também
é largamente usado como controle para
aplicações em tempo linear.
Ex. Broadcast de mensagens em uma rede
27
Referência Bibliográfica
Leiam o Capítulo 23 do livro de Cormen,
Leiserson, Rivest (Págs. 465 a 497).
Não esqueçam os problemas.
28