PAA-13-buscaEmGrafos

Prévia do material em texto

Profa. Thaís Alves Burity Rocha 
GRAFOS 
Agenda 
 Busca em grafos 
 
 Algoritmos de busca em grafos 
 Busca em largura 
 Busca em profundidade 
 
 Aplicações 
Ordenação topológica 
 Componentes fortemente conectados 
Busca em Grafos 
 Objetivo: Visitar sistematicamente todos os vértices 
de um grafo 
 
 Se um grafo contém ciclos, é preciso evitar que uma 
aresta seja visitada mais de uma vez 
3 7 
2 
5 
1 
4 
6 
Busca em grafos 
 Escolhendo um vértice inicial, é possível visitar os 
vértices seguindo uma determinada ordem 
 
 
 
 
 
 
 Algoritmo básico: 
 Tome vértice qualquer vértice s. Marque s. 
 Escolha uma aresta (x,y) não visitada, que parte de um 
vértice x já visitado e chegue a um vértice y não visitado. 
Marque a aresta (x,y) e o vértice y. 
 
0 
1 
2 
3 
4 
Vértices já 
visitados 
2 
Aresta 
escolhida 
Busca em grafos 
 Utilizando as arestas escolhidas na ordem da 
busca, é possível montar uma árvore de busca 
 
2 
4 
0 
3 
1 
6 
5 
Início 
0 
0 
0 
2 
4 
1 
3 
5 
1 
1 
2 
2 
6 
3 
3 
4 
4 
5 
5 
6 
6 
Busca em grafos 
 As buscas mais comuns são: 
 
 Busca em Largura (Breadth-First Search - BFS): Escolhe 
arestas que partem do vértice visitado mais antigo 
 
 Busca em Profundidade (Depth-First Search - DFS): 
Escolhe arestas que partem do vértice visitado mais 
recentemente 
 
BFS X DFS 
Busca em largura Busca em profundidade 
Busca em Largura 
 Ideia básica: 
 Dado um grafo G=(V,E), distinguir o vértice inicial s 
 Explorar sistematicamente as arestas de G até descobrir cada 
vértice acessível a partir de s 
 Descobrir todos os vértices com distância k a partir de s, antes 
de descobrir aqueles com distância k+1 
 
 A árvore gerada pelo caminho percorrido é uma árvore 
larga 
 Pouco profunda, mas com muitos filhos por nó 
 Também chamada de “Árvore primeiro na extensão” 
 
 Funciona para grafos orientados e também não orientados 
Busca em Largura: Exemplo 
Fila A 
0 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
∞ 
∞ 
∞ 
∞ ∞ 
∞ 
A 
B 
C 
D 
E 
F 
G 
0 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
Busca em Largura: Exemplo 
Fila B 
1 
C 
1 
1 
1 
∞ 
∞ ∞ 
∞ 
A 
B 
C 
D 
E 
F 
G 
0 
Busca em Largura: Exemplo 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
Fila C 
1 
E 
2 
1 
1 
∞ 
∞ 2 
∞ 
A 
B 
C 
D 
E 
F 
G 
0 
Busca em Largura: Exemplo 
Fila E 
2 
D 
2 
1 
1 
2 
∞ 2 
∞ 
A 
B 
C 
D 
E 
F 
G 
0 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
Busca em Largura: Exemplo 
Fila D 
2 
1 
1 
2 
∞ 2 
∞ 
A 
B 
C 
D 
E 
F 
G 
0 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
Busca em Largura: Exemplo 
Fila F 
3 
G 
3 
1 
1 
2 
3 2 
3 
A 
B 
C 
D 
E 
F 
G 
0 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
Busca em Largura: Exemplo 
Fila G 
0 
1 
1 
2 
3 2 
3 
A 
B 
C 
D 
E 
F 
G 
0 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
Busca em Largura: Exemplo 
Fila 
1 
1 
2 
3 2 
3 
A 
B 
C 
D 
E 
F 
G 
0 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice conhecido na fila 
 PRETO: Vértice conhecido que saiu da fila 
Busca em Largura: Exemplo 
 Caminho percorrido (árvore) 
B 
C 
D 
G E 
F A 
B C 
D 
G 
E 
F 
A 
ou 
Busca em Largura: Algoritmo 
 Grafo G = (V, E) representado como lista de 
adjacências 
 Para cada vértice u, estruturas auxiliares: 
 cor[u]: Mantém a informação da cor 
 π[u]: Mantém a informação do predecessor 
 Se não existe predecessor, valor é NIL 
 d[u]: Mantém a distância da origem ao vértice u 
 Uma fila Q com política FIFO para gerenciar os 
vértices de cor cinza 
Busca em Largura: Algoritmo 
 Linhas 2-9: Inicialização das 
estruturas auxiliares 
 
 Linhas 10-19: para cada 
vértice na fila, visitar 
adjacentes para descobrir 
novos vértices 
 
 Cada vértice é colocado na 
fila no máximo1 vez e sua 
lista de adjacências é 
percorrida no máximo uma 
vez: 
Tempo: O(V + E) 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
Busca em Profundidade 
 Sempre que um novo vértice v é descoberto, ele deve ser 
explorado por completo 
 
 Quando v é totalmente explorado, fazer backtracking 
para o seu predecessor (vértice que propiciou a descoberta 
de v) 
 
 Os caminhos percorridos formam várias árvores 
 
 Pode ser implementada com recursão ou pilha 
 
 Funciona para grafos orientados e também não orientados 
Busca em Profundidade 
A 
Pilha 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
1/ 
A B 
C D F 
E 
Busca em Profundidade 
B 
Pilha 
A 
2/ 1/ 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
D 
Pilha 
B 
A 
2/ 
3/ 
1/ 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
C 
Pilha 
D 
B 
A 4/ 
2/ 
3/ 
1/ 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
D 
Pilha 
B 
A 
4/5 
2/ 
3/ 
1/ 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
B 
Pilha 
A 
4/5 
2/ 
3/6 
1/ 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
A 
Pilha 
4/5 
2/7 
3/6 
1/ 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
Pilha 
4/5 
2/7 
3/6 
1/8 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
E 
Pilha 
4/5 
2/7 
3/6 
9/ 1/8 
A B 
C D F 
E 
Legenda 
 BRANCO:Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
F 
Pilha 
E 
4/5 
2/7 
10/ 3/6 
9/ 1/8 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
E 
Pilha 
4/5 
2/7 
10/11 3/6 
9/ 
A B 
C D F 
E 
1/8 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Busca em Profundidade 
Pilha 
4/5 
2/7 
10/11 3/6 
9/12 1/8 
A B 
C D F 
E 
Legenda 
 BRANCO: Vértice desconhecido 
 CINZA: Vértice primeiramente visitado 
 PRETO: Vértice totalmente explorado 
Caminhos percorridos 
 Floresta 
4/5 
2/7 
10/11 3/6 
9/12 1/8 
A B 
C D F 
E 
Busca em Profundidade: Algoritmo 
 Para cada vértice u, estruturas auxiliares: 
 cor[u]: Mantém a informação da cor 
 
π[u]: Mantém a informação do predecessor 
 Se não existe predecessor, valor é NIL 
 
 d[u] e f[u] são duas marcas de tempo (início e término 
da visita) 
 
Busca em Profundidade: Algoritmo 
Observe que os 
resultados podem 
depender da ordem 
em que os vértices 
são examinados 
na linha 5 
1 
2 
3 
4 
5 
6 
7 
Busca em Profundidade: Algoritmo 
Observe que os 
resultados podem 
depender da ordem 
em que os vértices 
são examinados 
na linha 3 
Tempo total: Θ(V + E) 
DFS percorre todos os vértices e Visita-DFS é chamado 1 vez 
para cada vértice, percorrendo sua lista de adjacências: 
1 
2 
3 
4 
5 
6 
7 
8 
Exercício 1 
 Observando o grafo a seguir, realize as buscas em 
profundidade e em largura 
Exercício 1: Solução 
 Busca em profundidade 
Exercício 1: Solução 
 Busca em largura 
Ordenação topológica 
 Utilizar busca em profundidade para executar 
ordenação topológica em grafos acíclicos orientados, 
também chamado de “gaos” 
 
 Uma ordenação topológica de um gao G(V, E) é uma 
ordenação linear de todos os seus vértices, tal que se G 
contém um arco (u, v), então u aparece antes de v na 
ordenação 
 
 Se o grafo não é acíclico, não é possível nenhuma 
ordenação linear 
Ordenação topológica 
 Em outras palavras 
 Uma ordenação topológica de um grafo pode ser vista 
como uma ordenação de seus vértices ao longo de uma 
linha horizontal, de tal forma que todas as arestas 
orientadas sigam da esquerda para a direita 
Ordenação topológica: Algoritmo 
 TOPOLOGICAL-SORT(G) 
1 chamar DFS(G) para calcular o tempo de término f[v] para 
cada vértice v 
2 à medida que cada vértice é terminado, inserir o vértice à 
frente de uma lista ligada 
3 return a lista ligada de vértices 
Tempo total: Θ(V + E) 
Linha 1: Θ(V + E) 
Linha 2: O(1) 
Ordenação topológica: Exemplo 
relógio sapatos 
meias cuecas 
calças 
cinto 
paletó 
gravata 
camisa 
Ordenação topológica: Exemplo 
 Busca em profundidade 
9/10 13/14 
17/18 11/16 
12/15 
6/7 
3/4 
2/5 
1/8 
cuecas meias 
relógio 
sapatos calças 
cinto 
camisa 
gravata 
paletó 
Ordenação topológica: Exemplo 
 Busca em profundidade 
17/18 
meias 
9/10 
relógio 
13/14 
11/16 
12/15 
cuecas 
sapatos 
calças 
6/7 
3/4 
2/5 
1/8 
cinto 
camisa 
gravata 
paletó 
Ordenação topológica: Exemplo 
 Ordenação 
paletó relógio 
sapatos 
meias 
cuecas 
calças cinto 
gravata camisa 
3/4 2/5 6/7 1/8 9/10 13/14 12/15 11/16 17/18 
Componentes fortemente conectados 
 Strongly Connected Components (SCC) 
 
 Um componente fortemente conectado de um grafo 
G = (V, E) é um subconjunto maximal de vértices C 
tal que, para todo par de vértices u e v em C, 
temos que os vértices u e v são acessíveis um a 
partir do outro 
Exemplo de SCC 
r s t u 
v w x y 
Grafo de componentes 
 GSCC = (VSCC, ESCC) 
 VSCC tem um vértice para cada SCC em G 
 ESCC tem um arco se existe um arco entre os 
correspondentes SCC em G 
y 
tu 
wx 
rsv 
Transposta de um grafo orientado 
 GT é transposta de um grafo dirigido 
GT = (V, ET), ET = {(u, v) : (v, u) ∈ E} 
GT é G com todos os arcos invertidos 
r s 
v w 
Grafo G 
r s 
v w 
Grafo GT 
SCC: Algoritmo 
 STRONGLY-CONNECTED-COMPONENT (G) 
1 chamar DFS(G) para calcular o tempo de término f[u] para 
cada vértice u 
2 calcular GT 
3 chamar DFS(GT) mas, no loop principal de DFS, considerar os 
vértices em ordem decrescente de f[u] (calculada na linha 1) 
4 dar saída aos vértices de cada árvore na floresta primeiro na 
profundidade formada na linha 3 como um componente 
fortemente conectado separado 
Linha 1: Θ(V + E) 
Linha 2: O(V+E) 
Linha 3: Θ(V + E) 
 
 
Tempo total: Θ(V + E) 
SCC: Algoritmo em passo-a-passo 
r s t u 
v w x y 
Algoritmo SCC: Passo 1 
 Chamar DFS(G) para achar os tempos f[u] de cada 
vértice 
13/14 1/10 
2/7 12/15 
11/16 
3/4 
r s 
v w x 
t 
5/6 
y 
8/9 
u 
Algoritmo SCC: Passo 2 
 Calcular GT 
r s 
v w x 
t 
y 
u 
Algoritmo SCC: Passo 3 
 Calcular DFS(GT) considerando os tempos f[u] de 
forma decrescente no loop principal 
14 10 
7 15 
16 
4 
r s 
v w x 
t 
6 
y 
9 
u 
Algoritmo SCC: Passo 3 
14 10 
7 15 
16 
4 
r s 
v w x 
t 
6 
y 
9 
u 
Algoritmo SCC: Passo 3 
14 10 
7 15 
16 
4 
r s 
v w x 
t 
6 
y 
9 
u 
Algoritmo SCC: Passo 3 
14 10 
7 15 
16 
4 
r s 
v w x 
t 
6 
y 
9 
u 
Algoritmo SCC: Passo 3 
14 10 
7 15 
16 
4 
r s 
v w x 
t 
6 
y 
9 
u 
Algoritmo SCC: Passo 4 
 Os vértices de cada árvore formada através do 
passo 3 se tornam SCC 
rsv 
wx 
tu 
y