ESTRUTURA DE DADOS II
Autor: Sílvia António 1
Área: DET
AULA 25_26 2
Sumário
➢ Grafos
▪ Árvore de expansão mínima
▪ Caminho mais curto
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS - MST 3
Árvore de Expansão Mínima ou Geradora Mínima (MST – minimun spanning tree)
• Imagine que para ligar um conjuntos de N pinos de um circuito eléctrico, usamos um conjunto
de N-1 fios em que cada fio conecta 2 pinos. Entre várias possibilidades, a mais desejada será a
que conseguir fazer o mesmo trabalho com a menor quantidade de fio possível.
• Podemos modelar este problema usando um grafo conectado, não direccionado G=(V, E),
onde V é o conjunto de pinos e E o conjunto de ligações possíveis, sendo que para cada
ligação existe um custo associado.
• Precisaremos encontrar um subgrafo T acíclico, conectado e que tenha o mesmo conjunto
de vértices do grafo original com o menor peso associado. T será chamada de árvore de expa
nsão mínima.
• Chamamos o problema de determinar a árvore T de problema da árvore de expansão mínima.
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS - MST 4
Definição
• A árvore de expansão mínima de um grafo:
➢ É um subgrafo ponderado, conectado e sem ciclos
➢ Inclui todos os vértices do grafo original
➢ A soma dos pesos das suas arestas, tem o menos valor possível
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS- MST 5
Aplicações do MST
• Transporte aéreo - Ligações de vôo
• Infra-estrutura rodoviárias ou ferroviárias com o menor uso de material;
• Redes de computadores – ligação com a menor quantidade de fibra óptica possível;
• Redes eléctricas e telefônicas com o menor custo;
• Circuitos integrados
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 24_25 – GRAFOS - MST 6
Exemplo - MST
A MST deste grafo, está marcado a
azul.
Liga todos os vértices do grafo
original, usando o menor custo
possível = 37.
Como criar a MST ?
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS - MST 7
Resolução usando o Algoritmo de Kruskal
• Considera cada vértice do grafo original como uma árvore independente e vai gerando
uma floresta F de G
• A cada iteração, o algoritmo adiciona a F uma aresta de G. O algoritmo escolhe uma
aresta de peso mínimo dentre as que são externas a floresta F;
• O processo continua até que todos os vértices façam parte da floresta;
• O algoritmo é resumido assim:
➢ Enquanto existem arestas externas
Escolhe uma aresta externa de peso míinimo
Acrescenta a aresta escolhida a F
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS - MST 8
Resolução usando o Algoritmo de Prim
• Comece por um vértice qualquer para ser o primeiro da árvore
• A cada iteração, o algoritmo procura a aresta de menor peso
que conecte um vértice da árvore a outro vértice que ainda não esteja na árvore;
• Esse vértice é adicionado a árvore e o processo repete-se até que todos os vértices
façam parte da árvore.
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS - MST 9
Exercícios
1.Uma empresa de televisão por cabo,
precisa de fazer a instalação num
condomínio com 9 casas. Terão de fazer
escavações de modo a passar os cabos por
todas as casas. O grafo representa o
condomínio, onde as casas são os vértices e
as arestas são todas as ligações possíveis
entre as casas. Os valores das arestas,
representam a distância em metros.
a) Represente o grafo, usando um método
à sua escolha (lista ou matriz).
b) Desenhe a árvore geradora
mínima (MST), que represente o custo
mínimo para passar o cabeamento por
todas as casas. Indique também o valor
obtido em metros.
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS 10
Algoritmo do Caminho mais curto
• Dado um grafo ponderado ou rede e dois vértices S e T, o caminho mais curto entre
os dois vértices S e T numa rede é o caminho direccionado de S até T com menor peso.
• Na procura do menor caminho podem ser verificadas as seguintes propriedades:
1. Nem todos os vértices necessitam de ser acessíveis a partir do vértice inicial;
2. O caminho mais curto não é necessáriamente o único;
3. O caminho deve respeitar a direcção das arestas.
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS 11
Exemplo - Algoritmo do Caminho mais curto
A) Grofo original B) Caminho mais c) Outro caminho
com os caminhos a curto entre s –z e s-x. mais curto entre s-z
partir de s.
Autor: Sílvia António
Ano Académico: 2024/2025
AULA 25_26 – GRAFOS 12
Algoritmo de Dijkstra para encontrar o caminho mais curto
Autor: Sílvia António
Ano Académico: 2024/2025
BIBLIOGRAFIA 13
• TENENBAUM, A. M.; LANGSAM, Y.; AUGMENTSTEIN, M. J. Estruturas de
Dados Usando C. 3. ed. São Paulo: Pearson Education, 2008.
• CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Algoritmos:
Teoria e Prática. 4. ed. Rio de Janeiro: Elsevier, 2024.
• SEDGEWICK, R. Algorithms in C. 4. ed. Boston: Addison-Wesley, 2011.
Autor: Sílvia António
Ano Académico: 2024/2025
MUITO OBRIGADO PELA ATENÇÃO!
14
Volenti Nihil Difficili -“A quem quer, nada é difícil”
