5 Percurso em grafos

Prévia do material em texto

1
BCM-0506: Comunicação & Redes
Percurso em Grafos
2
Aviso!
Essa aula online será gravada para o 
acompanhamento assíncrono pelos alunos e ficará 
disponível em local privado no Moodle
A participação na aula com voz ou vídeo implica na 
aceitação dessa condição
Agradecemos os alunos que puderem participar 
com voz e vídeo, por tornar a aula mais dinâmica e 
interessante
3
Agenda
Conceitos relacionados com percurso em grafos
Busca em largura
Busca em profundidade
Algoritmos de menor caminho (Dijkstra)
4
Conceitos relacionados com 
percurso em grafos
5
Definições relevantes
Passeio (‘walk’): sequência alternante de vértices e arestas 
que começa e termina em vértices 
• Em um passeio de tamanho k, temos (v0, e1, v1, e2...ek, vk)
Trilha (‘trail’): passeio no qual todas as arestas são distintas
Caminho (‘path’): passeio na qual todos os vértices (exceto 
possivelmente o primeiro e o último) são distintos
e1
e2
e3
e4
e5
e6
e7
6
Caminhos (percursos) em Grafos
Um caminho em um grafo é uma sequência de 
vértices onde cada novo vértice é adjacente ao 
anterior (adjacente = conectado por um aresta)
Um caminho de uma origem (o) a um destino (d)
A origem é o primeiro vértice
O destino é o último vértice
Uma aresta v → w pertence ao caminho se o 
vértice w é o sucessor do vértice v no caminho 
7
Percurso (caminhos) em Grafos
O tamanho de um caminho é dado pelo número de 
arestas, ou seja, o total de vértices envolvidos 
menos um
Em grafos não 
direcionados, os 
caminhos são 
simétricos
Nesse caso, para quaisquer 
vértices o e d, existe um 
caminho entre o e d se e 
somente se existe um 
caminho entre d e o
8
Exemplo de caminho
Esse grafo é não direcionado e não ponderado
Do vértice 1 ao 3 há mais de um caminho
Caminho 1 a 3: 1 → 2 → 3
Caminho 3 a 1: 3 → 2 → 1
9
Exemplo de caminho
Em grafos direcionados, os caminhos de ida e 
volta podem ser diferentes
Caminho 1 a 3: 1 → 2 → 3
Caminho 3 a 1: 3 → 4 → 1
10
1) Suponha que eu queira 
viajar de carro, saindo de 
São Paulo (capital) para 
Bebedouro;
2) Cada estrada tem um 
pedágio, com mesmo valor, 
independentemente da 
distância;
3) Quero gastar o menor valor 
possível de pedágio
11
Busca (ou Percurso) em Grafos
Um algoritmo de busca visita (verifica ou atualiza) 
cada vértice e cada aresta no grafo
Cada aresta é visitada somente uma vez
O termo “busca” faz sentido porque o algoritmo 
atravessa o grafo buscando por todos os vértices 
que podem ser acessados a partir de um 
determinado vértice
12
Busca (ou Percurso) em Grafos
Existem maneiras diferentes de percorrer um 
grafo
Cada estratégia é caracterizada pela ordem na 
qual os vértices são visitados
A ordem de visita dos vértices é essencial para 
determinar como a busca é realizada
13
Busca (ou Percurso) em Grafos
Algoritmos de busca mais comuns
Busca em largura (Breadth-First Search, BFS)
Busca em profundidade (Depth-First Search, DFS)
Busca em Largura
15
Busca (ou Percurso) em Grafos
Um algoritmo de busca visita (verifica ou atualiza) cada 
vértice e cada aresta no grafo
O termo “busca” faz sentido porque o algoritmo 
atravessa o grafo buscando por todos os vértices que 
podem ser acessados a partir de um determinado 
vértice
Componentes conexas (disjuntas) Componentes fortemente conexas 
16
Busca (ou Percurso) em Grafos
Algoritmos de busca mais comuns
Busca em largura (Breadth-First Search, BFS)
Busca em profundidade (Depth-First Search, DFS)
17
Busca em Largura
O algoritmo de busca em largura visita os vértices 
usando uma estratégia FIFO (First-In, First-Out)
O próximo vértice é o que está há mais tempo na fila
O algoritmo marca todos os vértices que podem ser 
alcançados de um vértice de origem até o destino
A busca é influenciada pela distância a partir da origem
Suponha uma busca por um
caminho do vértice 1 ao 5
18
Exemplo: Busca em Largura
No início, todos os vértices são ‘brancos’
Vértice de origem 1
Largura = 0
Cor = cinza
Inserido na fila Q
Agora, seus vizinhos são obtidos (neste caso, somente o vértice 2)
Q = {1}
19
Exemplo: Busca em Largura
O vértice 1 é removido da fila Q e marcado “preto”
Vértice 2
Largura = 1
Cor = cinza
Inserido na fila Q
Agora, seus vizinhos são obtidos (1, 3 e 5)
Q = {2}
20
Exemplo: Busca em Largura
Vértice 1 não é inserido em Q porque já está preto
Vértice 2 é removido da fila Q e marcado “preto”
Vértices 3 e 5
Largura = 2
Cor = cinza
Inseridos na fila Q
Q = {3, 5}
21
Exemplo: Busca em Largura
Vértice 3 é removido de Q e marcado “preto”
Vértice 4
Largura = 3
Cor = cinza
Inserido em Q
Q = {5, 4}
22
Exemplo: Busca em Largura
Vértice 5 é removido de Q e marcado “preto”
Sua única conexão é com o vértice 2, que já está preto 
(ou seja, nada é feito)
Q = {4}
23
Exemplo: Busca em Largura
Vértice 4 é removido de Q e marcado “preto”
Está conectado com os vértices 1 e 5, que já estão pretos 
(ou seja, nada é feito)
Q está vazia (final do algoritmo)
Q = ∅
24
Exemplo: Busca em Largura
O caminho é obtido de trás para frente, iniciando com o 
destino e visitando seus predecessores até a origem
Então, inverte-se a lista
Para esse exemplo o caminho é 1 →2→5. 
Q = ∅
25
Visualização da busca em níveis
26
Busca em Largura: Aplicações
Encontrar o menor caminho entre dois vértices 
u e v, com o caminho medido pelo número de 
arestas
Testar se o grafo é bipartido
Coleta de lixo (garbage collection) em linguagens 
de programação
Busca em Profundidade
28
Busca (ou Percurso) em Grafos
Algoritmos de busca mais comuns
Busca em largura (Breadth-First Search, BFS)
Busca em profundidade (Depth-First Search, DFS)
29
Busca em Profundidade
O algoritmo de busca em profundidade visita os 
vértices usando uma estratégia LIFO (Last-In, 
First-Out)
Por essa estratégia, o algoritmo percorre o grafo 
indo cada vez mais ‘ao fundo’
As arestas são visitadas a partir de um vértice v
que ainda tem arestas não percorridas
Quando todas as arestas de um vértice de 
origem foram percorridas, a busca retorna para 
visitar as arestas do vértice anterior a v
(estratégia recursiva, “backtracking”)
30
Exemplo: Busca em Profundidade
No início, todos os vértices são marcados “branco”
Vértice de origem 1 
Cor = cinza
Distância = 0
Só uma aresta existe, que leva ao vértice 2
31
Vértice 1: cor = preto
Vértice 2
Cor: cinza
Distância: 1
Próximos vértices
A primeira aresta do vértice 2 conecta com o vértice 
1, que já é preto
A segunda aresta é considerada, que leva ao vértice 3
Exemplo: Busca em Profundidade
32
Vértice 3
Cor = cinza
Distância = 2
Sua única aresta é examinada, que leva ao vértice 4
Exemplo: Busca em Profundidade
33
Vértice 3: cor = preto
Vértice 4
Cor = cinza 
Distância = 3
Próximos vértices
A primeira aresta leva ao vértice 1, que já é preto
A segunda aresta leva ao vértice 5
Exemplo: Busca em Profundidade
34
Vértice 4: preto
Vértice 5
Cor = cinza
Distância = 4
Sua única aresta de saída é 
examinada, que leva ao vértice 
2, que já está cinza
Exemplo: Busca em Profundidade
35
Vértice 5: cor = preto
Sua única aresta de saída leva ao vértice 2, que já é cinza
Agora, como não existe maneira de continuar em 
profundidade, retorna ao vértice 4, que está na mesma 
condição, e retorna ao vértice 3 e finalmente para o 
vértice 2 de novo
Exemplo: Busca em Profundidade
36
A última aresta de saída do vértice 2 leva a um vértice 
que já é preto (vértice 5)
Vértice 2 é marcado preto e o algoritmo termina
O caminho em profundidade é: 1 → 2 → 3 → 4 →5
Ao contrário de em largura: 1 → 2 →5
Exemplo: Busca em Profundidade
37
Busca em Profundidade: 
Aplicações
Encontrar componentes conexas
Teste de planaridade de grafos
Resolver problemas com somente uma solução, 
como labirintos
A própria geração de labirintos pode usar uma 
busca em profundidade com decisões aleatórias
Algoritmos de menor caminho
39
Distância
P é o menor caminho se não existe outro caminhoQ
iniciando e terminando nos mesmos vértices de origem 
e destino, que seja menor que P
A distância entre s e t é o tamanho do caminho mais 
curto entre s e t
No caso do caminho não existir, ou ser desconhecido, a 
distância é infinita (∞)
Em grafos não direcionados, a distância de s para t e a 
distância de t para s são iguais
Em grafos direcionados, essa distância pode ser diferente
40
Exemplo: Menor Caminho
Para grafos ponderados, o peso das arestas deve ser 
somado nos caminhos
Caminho mais curto de 1 a 5 é 2 (path 1 → 2 → 5)
Existe o caminho 1 → 2 → 3 → 4 → 5, com distância 5
41
Algoritmos de Menor Caminho
Existem algoritmos específicos de encontrar o menor 
caminho em grafos
Para um vértice s de um grafo ponderado, encontrar, 
para todo vértice t que pode ser visitado a partir de s, 
o menor caminho de s para t
Propriedade triangular: explorada pelos algoritmos
Para quaisquer vértices x, y e z de um grafo ponderado com 
pesos não negativos
d(x,z) ≤ d(x,y) + d(y,z) , onde d(i,j) é a distância de i para j
42
Algoritmo de Dijkstra
Um algoritmo eficiente e bem conhecido para 
encontrar menores caminhos em grafos
Criado em 1956, publicado em 1959 “A Note on 
Two Problems in Connexion with Graphs” 
(acesso ao paper original disponível no Moodle)
Encontrar menor caminho entre
Dois vértices
Um vértice para todos os outros vértices 
no grafo
Recebe uma matriz de adjacências como 
entrada e gera um caminho como saída
Edsger W. Dijkstra
(1930-2002)
43
Algoritmo de Dijkstra
1. Atribua uma distância infinita para todos os pares de vértices, 
exceto aqueles conectados ao vértice de origem
2. Marque todos os vértices como não visitados
3. Defina o vértice de origem como o vértice atual
4. Para o vértice atual, analise todos os seus vizinhos que não foram 
visitados e compute a distância entre eles
• Se essa nova distância é menor do que a atual, atualize
5. Quando todos os vizinhos do vértice atual forem visitados, marque-
os como visitados, o que evitará com que sejam analisados 
novamente (sua distância é mínima e final)
6. Escolha o vértice não visitado com a menor distância da origem 
como sendo o atual e retorne ao passo 4
44
Exemplo: Algoritmo de Dijkstra
Vértice 1 é a origem
Distância para os outros vértices em vermelho
Distância infinita para 3, 4 e 5
Distância 1 para vértice 2
D = 1
D = ∞
D = ∞
D = ∞
D = 0
45
Exemplo: Algoritmo de Dijkstra
Vértice 2 é o atual
Vértice 2 leva a 3 e 5 e as distâncias são 
computadas para 3 e 5
D = 1
D = 2
D = 2
D = ∞
D = 0
D = 1
46
Exemplo: Algoritmo de Dijkstra
Vértice 3 é o atual
Vértice 3 conecta com 4 com distância 2
Agora, todos os vértices foram visitados e vetor 
com os menores caminhos de 1 é D = [0 1 2 4 2]
D = 1
D = 2
D = 2
D = 4
D = 0
D = 2
47
BCM-0506:Percurso em Grafos
FIM