Embed Size (px)
Citation preview
Busca em GrafosOBJETIVO: 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.
Busca em Árvores Enraizadas1. Busca em pré-
ordem
Raiz visitada antes dos descendentes
A B C E F D
Busca em Árvores Enraizadas2. Busca em pós-
ordem
Raiz visitada depois dos descendentes B E F C D A
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)
Algoritmo Pré-ordem
Algoritmo Pré-ordem(raiz) Se raiz não nula então Visite (raiz)
Pré-ordem (left.raiz)Pré-ordem (right.raiz)
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)
Algoritmo In-ordem
Algoritmo In-ordem(raiz) Se raiz não nula então In-ordem (left.raiz)
Visite (raiz)In-ordem (right.raiz)
Busca em Grafos com Ciclos Se o grafo contém ciclos, é preciso
cuidar para evitar que arestas sejam visitadas mais de uma vez.
3 7
2
51
4
6
Busca em Grafos com CiclosExemplo: A partir do grafo abaixo obtemos
3 7
2
51
4
6 1
6 4
2
3
7 5
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).
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.
Busca em Profundidade JAVA Applet para uma Busca em Profundidade
JAVA Applet para Busca em grafo direcionado com pilha
14
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.
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 */
16
Árvore de Busca em Profundidade
A busca em profundidade biparticiona o conjunto de arestas em:
3 7
2
51
4
6
- Arestasde Árvore
- Arestas de Retorno
1
6 4
2
3
7 5
17
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.
18
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].
Variações de Busca em Profundidade
O algoritmo de Busca em Profundidadeé usado como controle para muitas aplicações em tempo linear.Ex. Componentes Biconexos (Tolerância a falhas em redes)
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}
1
6 4
2
3
7 5
20
Busca em Largura Cria um centro no vértice inicial e forma
“níveis” ou “camadas” a partir deste nó.
3 7
2
51
4
61
6 4 5
2 3
7
6
21
Vértices Brancos, Cinza e Pretos - Brancos – Valor inicial - Cinza – Após serem descobertos - Pretos – Após a descoberta de todos os adjacentes.
1
6 4 5
2 3
7
1
6 4 5
2 3
7
4 5
2 3
7
1s ss
6
22
Busca em Largura
Applet para Busca em Largura
23
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 FPara 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 */
24
Ao término de Busca em Largura A busca em largura biparticiona as
arestas do grafo em arestas de árvore e arestas de cruzamento.
3 7
2
51
4
6
1
6 4 5
2 3
7
25
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 ...
26
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).
27
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
28
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.
