Disciplina: Técnicas de programação
Curso: Engenharia da computação
Aula 15 – Árvore de espalhamento
mínimo e algoritmo de Dijkstra
[email protected]
P R O F. R A FA E L S TO F FA L E T T E J O Ã O Atendimento: sala ADM113
Qua 13h00 às 14h00
DATA : 2 9 / 0 5 / 2 0 1 9 Qui 18h30 às 20h30
Campus Birigui
Na ultima aula
29/05/2019 2
Busca em profundidade (DFS)
depth-first search
É próximo ao algoritmo de busca da existência de caminhos;
Objetivo: visitar todos os vértices e numerá-los na ordem em que são descobertos.
Relacionada a teorias como backtracking e pré-ordem;
29/05/2019 3
Busca em profundidade (DFS)
Origem: v
A partir de v, encontrando um primeiro vértice adjacente (t) chama-se a função recursivamente
tentando encontrar TODOS os vértices a partir de t.
O vetor “listaVisitados” serve para garantir uma só visita a cada vértice.
29/05/2019 4
Busca em profundidade (DFS)
A partir do vértice 0;
Visitado: 1 0 0 0 0
3
0 1 0 0 0 0 1 4
0 0 1 1 0
0 0 0 0 1
1 0 0 0 1 2
0 1 0 0 0
29/05/2019 5
Busca em profundidade (DFS)
Contador de visita: 1
A partir do vértice 0;
Visitado: 1 0 0 0 0
3
Adjacentes ao vértice 0: {1}
0 1 0 0 0 0 1 4
0 0 1 1 0
0 0 0 0 1
1 0 0 0 1 2
0 1 0 0 0
29/05/2019 6
Busca em profundidade (DFS)
Contador de visita: 2
A partir do vértice 1;
Visitado: 1 2 0 0 0
3
Adjacentes ao vértice 1: {2,3}
0 1 0 0 0 0 1 4
0 0 1 1 0
0 0 0 0 1
1 0 0 0 1 2
0 1 0 0 0
29/05/2019 7
Busca em largura (BFS)
Marcar todos os vértices como não visitados:
Utiliza-se uma fila como auxiliar para marcar a ordem das visitas;
◦ Nos lembra o percurso em nível das árvores.
Verificar TODOS os vizinhos do vértice atual
Se não foi visitado:
Colocar ele na fila e marca como visitado
O algoritmo enumera os vértices, em sequência, na ordem em que eles são descobertos
29/05/2019 8
Busca em largura(BFS)
Contador: 1
Vértice atual:
Visitados: 1 0 0 0 0
3
Fila auxiliar 0
0 1 0 0 0 0 1 4
0 0 1 1 0
0 0 0 0 1
1 0 0 0 1 2
0 1 0 0 0
29/05/2019 9
Busca em largura(BFS)
Contador: 1
Vértice atual: 0
Visitados: 1 0 0 0 0
3
Fila auxiliar 0
0 1 0 0 0 0 1 4
Processa a fila: 0 0 1 1 0
Remove o elemento mais antigo: 0 0 0 0 0 1
1 0 0 0 1 2
Por na fila os adjacentes do vértice processado
0 1 0 0 0
29/05/2019 10
Busca em largura(BFS)
Contador: 2
Vértice atual: 0
Visitados: 1 2 0 0 0
3
Fila auxiliar 1
0 1 0 0 0 0 1 4
0 0 1 1 0
0 0 0 0 1
1 0 0 0 1 2
0 1 0 0 0
29/05/2019 11
Busca em largura(BFS)
Contador: 2
Vértice atual: 1
Visitados: 1 2 0 0 0
3
Fila auxiliar 1
0 1 0 0 0 0 1 4
Processa a fila: 0 0 1 1 0
Remove o elemento mais antigo: 1 0 0 0 0 1
1 0 0 0 1 2
Por na fila os adjacentes do vértice processado
0 1 0 0 0
29/05/2019 12
Busca em largura(BFS)
Contador: 3
Vértice atual: 1
Visitados: 1 2 3 3 0
3
Fila auxiliar 3 2
0 1 0 0 0 0 1 4
0 0 1 1 0
0 0 0 0 1
1 0 0 0 1 2
0 1 0 0 0
29/05/2019 13
Busca em largura(BFS)
Contador: 3
Vértice atual: 1
Visitados: 1 2 3 3 0
3
Fila auxiliar 3 2
0 1 0 0 0 0 1 4
Processa a fila: 0 0 1 1 0
Remove o elemento mais antigo: 2 0 0 0 0 1
1 0 0 0 1 2
Por na fila os adjacentes do vértice processado
0 1 0 0 0
29/05/2019 14
Busca em largura(BFS)
Contador: 4
Vértice atual: 2
Visitados: 1 2 3 3 4
3
Fila auxiliar 4 3
0 1 0 0 0 0 1 4
0 0 1 1 0
0 0 0 0 1
1 0 0 0 1 2
0 1 0 0 0
29/05/2019 15
Caminho Hamiltoniano
Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de
um grafo G, não repetindo nenhum à caminho entre u e v que passa por TODOS os vértices;
Caso esse caminho seja possível descrever um ciclo, este é denominado ciclo hamiltoniano;
Um grafo que possua tal circuito é chamado de grafo hamiltoniano.
29/05/2019 16
Prática checkpoint (vale: 4)
1. Implementar uma função que verifica o grau de um dado vértice;
2. Implementar uma função que verifica se um grafo é regular. Se sim informar o grau;
3. Implementar uma função que verifica se um grafo é completo;
4. Imprimir o grafo em formato de parênteses;
5. Implementar uma função que verifica a existência de um CAMINHO, por meio da busca em largura;
6. Implementar uma função que verifica a existência de CICLOS em um grafo;
7. Implementar uma função que verifica a existência de um CAMINHO HAMILTONIANO em um grafo;
29/05/2019 17
Algoritmo de Dijkistra
Calcula o caminho de custo mínimo entre vértices de um grafo.
Proposto em 1959
Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para
todos os demais vértices do grafo.
Considerado simples e de alta performance.
Não lida bem com arestas com valores negativos.
Parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa.
29/05/2019 18
Algoritmo de Dijkistra
Atribua valor zero à estimativa do custo mínimo do vértice s (a raiz da busca) e infinito às demais
estimativas;
Atribua um valor qualquer aos precedentes (o precedente de um vértice t é o vértice
que precede t no caminho de custo mínimo de s para t);
Enquanto houver vértice aberto:
◦ seja k um vértice ainda aberto cuja estimativa seja a menor dentre todos os vértices abertos;
◦ feche o vértice k
◦ Para todo vértice j ainda aberto que seja sucessor de k faça:
◦ some a estimativa do vértice k com o custo do arco que une k a j;
◦ caso esta soma seja melhor que a estimativa anterior para o vértice j, substitua-a e anote k como precedente de j.
29/05/2019 19
Algoritmo de Dijkistra
Um vértice é fechado se já foi obtido um caminho de custo mínimo do vértice raiz até ele;
Caso contrário ele dito estar aberto.
u v
Vértices s u v x y
estimativas s
precedente
x Y
29/05/2019 20
Algoritmo de Dijkistra
u v
Vértices s u v x y
estimativas 0 ∞ ∞ ∞ ∞ s
precedente - - - - -
x Y
29/05/2019 21
Algoritmo de Dijkistra
10
u v
Vértices s u v x y
estimativas 0 10 ∞ 5 ∞ s
precedente s s - s -
x Y
Seleciona vértice aberto s
Fecha s 5
Novas estimativas de u e x
29/05/2019 22
Algoritmo de Dijkistra
X é o menor caminho, portanto segue por ele
10
u v
Vértices s u v x y
estimativas 0 10 ∞ 5 ∞ s
precedente s s - s -
x Y
Seleciona vértice aberto s
Fecha s 5
Novas estimativas de u e x
29/05/2019 23
Algoritmo de Dijkistra
8
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 5 7 s
precedente s s x x s x
x Y
Seleciona vértice aberto x
Fecha x 5 7
Novas estimativas de u, v e y
29/05/2019 24
Algoritmo de Dijkistra
Y é o menor caminho, portanto segue por ele
8
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 5 7 s
precedente s s x x s x
x Y
5 7
29/05/2019 25
Algoritmo de Dijkistra
8
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 5 7 s
precedente s s x x s x
x Y
5 7
29/05/2019 26
Algoritmo de Dijkistra
8 13
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 13 5 7 s
precedente s s x x y s x
x Y
Seleciona vértice aberto y
Fecha y 5 7
Novas estimativas de v (s ja está fechado)
29/05/2019 27
Algoritmo de Dijkistra
U é o vértice aberto de estimativa mínima
8 13
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 13 5 7 s
precedente s s x x y s x
x Y
5 7
29/05/2019 28
Algoritmo de Dijkistra
8 13
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 13 5 7 s
precedente s s x x y s x
x Y
5 7
29/05/2019 29
Algoritmo de Dijkistra
v é o vértice aberto de estimativa mínima 9
8 13
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 13 9 5 7 s
precedente s s x x yu s x
x Y
Seleciona vértice aberto u
Fecha u 5 7
Novas estimativas de v (x ja está fechado)
29/05/2019 30
Algoritmo de Dijkistra
9
8 13
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 13 9 5 7 s
precedente s s x x y u s x
x Y
5 7
29/05/2019 31
Algoritmo de Dijkistra
9
8 13
10 14
u v
Vértices s u v x y
estimativas 0 10 8 14 13 9 5 7 s
precedente s s x x y u s x
x Y
Seleciona vértice aberto v
Fecha v 5 7
Novas estimativas de nada (todos ja está fechados)
29/05/2019 32
Algoritmo de Dijkistra
8 9
u v
Vértices s u v x y
estimativas 0 8 9 5 7 s
precedente s x u s x
x Y
5 7
29/05/2019 33
Algoritmo de Dijkistra
• De s até v, o custo é 9 e passa por u 9
8
u v
Vértices s u v x y
estimativas 0 8 9 5 7 s
precedente s x u s x
x Y
5 7
29/05/2019 34
Algoritmo de Dijkistra
• De s até v, o custo é 9 e passa por u 9
• De s até u o custo é 8 e passa por x 8
u v
Vértices s u v x y
estimativas 0 8 9 5 7 s
precedente s x u s x
x Y
5 7
29/05/2019 35
Algoritmo de Dijkistra
• De s até v, o custo é 9 e passa por u 9
• De s até u o custo é 8 e passa por x 8
• De s até x o custo é 5 u v
Vértices s u v x y
estimativas 0 8 9 5 7 s
precedente s x u s x
x Y
5 7
29/05/2019 36
MST – minimum spaning tree
Também conhecido como problema das Árvores geradoras de custo mínimo
◦ Problema fundamental sobre grafos não-dirigidos com custos nas arestas.
◦ Encontrar um subgrafo ACÍCLICO que engloba TODOS os vértices do grafo original.
29/05/2019 37
MST – minimum spaning tree
Considere o grafo descrito pelo conjunto de arestas
A={4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4}
Com custos respectivos = {35 37 28 16 32 38 17 19 26 36 29 34 40 52 58 93}
Como encontrar uma MST?
29/05/2019 38
MST – minimum spaning tree
Considere o grafo descrito pelo conjunto de arestas
A={4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4}
Com custos respectivos = {35 37 28 16 32 38 17 19 26 36 29 34 40 52 58 93}
Como encontrar uma MST?
O conjunto de arestas 4-5 5-7 0-7 2-3 1-7 0-2 6-2 pode ser uma árvore geradora do grafo.
O custo dessa árvore é 35 + 28 + 16 + 17 + 19 + 26 + 40 = 181.
29/05/2019 39
MST – minimum spaning tree
Portanto,
Pode-se dizer que o algoritmo para encontrar uma MST é o mesmo algoritmo para encontrar um
caminho que passa por TODOS os vértices sem repetição;
O menor caminho é uma MST
29/05/2019 40
MST – minimum spaning tree
Exemplo extraído do livro do Sedgewick
Nem sempre existe apenas uma MST;
Tudo depende dos pontos de partida e
chegada
29/05/2019 41
29/05/2019 42
MST – minimum spaning tree
Uma MST de um grafo orientado com pesos nas arestas é uma coleção de arestas que conectam
TODOS os vértices e que a soma dos valores das arestas selecionadas é a menor soma de arestas
que conectam TODOS os vértices.
Ideia básica:
29/05/2019 43
MST – minimum spaning tree
A primeira estratégia para encontrar uma árvore geradora mínima MST é datada em 1926 por
Otakar Borüvka;
Inspirada no problema de fornecer uma cobertura elétrica eficiente na área rural da cidade de
Morávia do Sul;
29/05/2019 44
MST – minimum spaning tree
Algoritmo PRIM A diferença entre os dois está na forma como cada um escolhe
uma aresta para compor MST
Algorimto Kruskal
De forma genérica:
29/05/2019 45
Algoritmo Kruskal - MST – minimum spaning tree
Simplesmente adiciona arestas (uma por uma) ao conjunto MST que tem o menor custo e não
formam um ciclo;
Assume que no início existe uma floresta composta por APENAS 1 árvore, o vértice inicial;
A cada passo incrementa a quantidade de árvores na floresta.
29/05/2019 46
Algoritmo Kruskal - MST – minimum spaning tree
Inicia com uma floresta de árvores com apenas um vértice (INICIAL);
◦ Busca a cada passo, uma aresta que, além de conectar duas árvores distintas da floresta, possua peso
mínimo;
Ordena as arestas por seus pesos;
Uma a uma, as arestas são analisadas (em ordem):
◦ Executa uma função FIND-SET(u) para cada vértice adjacente a ela.
Se os vértices pertencerem a um mesmo conjunto -> fecha um ciclo
Senão: Inclui a aresta ao conjunto MST
29/05/2019 47
Algoritmo Kruskal
29/05/2019 48
Algoritmo Kruskal
29/05/2019 49
Algoritmo Kruskal
29/05/2019 50
Algoritmo Kruskal
29/05/2019 51
29/05/2019 52
Algoritmo Kruskal - MST
29/05/2019 53
Algoritmo Kruskal - MST – minimum spaning tree
Se for preciso implementar a estratégia, a ideia principal se concentra em:
29/05/2019 54
Algoritmo PRIM - MST – minimum spaning tree
Ao contrário do Kruskal, o algoritmo PRIM não constrói árvores disjuntas, mas sim uma árvore
só.
A árvore cresce a cada iteração pelo caminho menos custoso ------ Algoritmo guloso;
◦ A cada iteração, abocanha a aresta mais curta sem se preocupar com o efeito global dessa escolha.
O algoritmo de Prim faz crescer uma subárvore até que ela se torne geradora.
29/05/2019 55
Algoritmo PRIM - MST – minimum spaning tree
O algoritmo assume uma ”franja” (fringe) que nada mais é que o leque de possibilidades das
bordas do grafo MST;
3
3 e 2 são a franja da MST ={01]
0 1 4
29/05/2019 56
Algoritmo PRIM - MST – minimum spaning tree
O algoritmo assume uma ”franja” (fringe) que nada mais é que o leque de possibilidades das
bordas do grafo MST;
3
3 e 2 são a franja da MST ={01]
0 1 4
Para todos os vértices na franja:
◦ Analisar a aresta de menor custo;
◦ Incluir essa aresta no MST;
2
29/05/2019 57
Algoritmo PRIM - MST – minimum spaning tree
29/05/2019 58
Algoritmo PRIM - MST
29/05/2019 59
Algoritmo PRIM - MST
29/05/2019 60
Algoritmo PRIM - MST
29/05/2019 61
Algoritmo PRIM - MST
29/05/2019 62
29/05/2019 63
Algoritmo PRIM - MST
29/05/2019 64
MST
MST - PRIM
MST - Kruskal
29/05/2019 65
Checkpoint [vale 1]
[Sedgewick]
Qual o custo de uma MST do grafo não-dirigido com custos descrito a seguir?
A={0-6 0-1 0-2 4-3 5-3 7-4 5-4 0-5 6-4 7-0 7-6 7-1}
Custos respectivos = {51 32 29 34 18 46 40 60 51 31 25 21}
29/05/2019 66
Checkpoint [vale 1]
Implementar o algoritmo de Dijkstra com caminhos REAIS (ver km no google maps).
Incluir as arestas:
Bauru, Jau
Birigui, SJRioPreto
Jau, SaoCarlos,
SJRioPreto, SaoCarlos
Jau, RioClaro
Birigui, Marilia
SaoCarlos, RioClaro,
Birigui, Lins
Lins, Marilia RioClaro, Campinas
Lins, Bauru Campinas, SaoPaulo
Marilia, Bauru Bauru, Botucatu
Jau, Botucatu Botucatu, SaoPaulo
29/05/2019 67
