Projete um algoritmo (pseudocódigo) baseado em Kruskal ou Prim que, dado um grafo conectado ponderado (dados…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Reconhecer objetos do mundo real e digital que podem ser representados através de grafos que estabelecem uma organização com uma quantidade variável de vértices conectados por arestas, fazendo manipulações simples sobre estas representações.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete um algoritmo (pseudocódigo) baseado em Kruskal ou Prim que, dado um grafo conectado ponderado (dados: lista de arestas com pesos), construa uma árvore geradora mínima. Explique as variáveis, a operação chave e a complexidade temporal.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Resposta modelo (Kruskal): Entrada: lista de arestas E com pesos, número de vértices V. Variáveis: parent[1..V], rank[1..V] (Union-Find), MST := ø, total := 0. Pseudocódigo: ordenar E por peso crescente para v em 1..V: parent[v]=v, rank[v]=0 para cada aresta (u,v,w) em E ordenada: if Find(u) ? Find(v): Union(u,v) adicionar (u,v,w) a MST total += w retornar MST, total Operação-chave: consultas e uniões no Union-Find (Find/Union) que evitam formar ciclos. Complexidade: ordenar arestas O(E log E) domina; operações Union-Find amortizadas quase constantes (a(V)), total O(E log E). Observação: usar Prim com heap binário dá complexidade O(E log V) e pode ser preferível em grafos densos; variáveis em Prim: chave[v], pai[v], heap de prioridades.
Explicação
O algoritmo de Kruskal é eficaz para construir uma árvore geradora mínima, pois utiliza a abordagem de unir componentes conectados sem criar ciclos, garantindo assim a minimização do peso total. A complexidade temporal é dominada pela ordenação das arestas, o que é adequado para grafos esparsos, enquanto as operações de união e busca são otimizadas pelo uso da estrutura Union-Find. Essa combinação de técnicas assegura que o algoritmo seja eficiente e funcional para o problema proposto.
Raio-X da questão
árvore geradora mínima
avaliacao
algoritmos de grafos · pseudocódigo
Revisar os algoritmos de Kruskal e Prim e suas complexidades.
O aluno pode confundir os algoritmos de Kruskal e Prim, aplicando a lógica de um no outro, resultando em uma árvore geradora mínima incorreta.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
- Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…
- Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
- Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
- Descreva em pseudocódigo um algoritmo que, dado um grafo não direcionado representado por listas de adjacência e um…
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog