No algoritmo de Kruskal para computar uma árvore geradora mínima de um grafo, qual variável na estrutura…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
No algoritmo de Kruskal para computar uma árvore geradora mínima de um grafo, qual variável na estrutura union-find registra o representante (root) de cada conjunto durante as operações find/union?
- A) O vetor 'pai' (parent) que aponta para o representante de cada elemento.
- B) O vetor 'caminho' (path)
- C) Vetor 'tamanho' (size)
- D) Vetor 'peso' (weight)
- E) Vetor 'marcado' (marked)
✅ Resposta correta: alternativa A
Resolução passo a passo
- Na estrutura union-find (conjuntos disjuntos), cada elemento do universo é representado por um índice em um vetor, normalmente chamado 'pai' (parent). Para cada elemento i, pai[i] guarda o elemento pai na árvore interna do conjunto. O representante (root) é o elemento cujo pai é ele mesmo, isto é, pai[r] = r.
- A operação find(x) percorre pai[x], pai[pai[x]] e assim por diante até encontrar a raiz, que é o representante do conjunto. A operação union(x, y) acha as raízes de x e de y e faz uma delas apontar para a outra, alterando o vetor 'pai'. Logo, é exatamente o vetor 'pai' que registra o representante durante find/union.
- Por que as outras estão erradas: B) o vetor 'caminho' não existe como componente padrão do union-find; se referir à compressão de caminho, é uma técnica que altera 'pai', não um registro de representantes. C) o vetor 'tamanho' guarda o número de elementos de cada conjunto e serve para a união por tamanho, não para identificar a raiz. D) o vetor 'peso' armazena os pesos das arestas do grafo, que são dados de entrada, não da estrutura union-find. E) o vetor 'marcado' indica se um vértice já foi visitado, útil em buscas como DFS ou BFS, mas não no union-find.
- Conclusão: a alternativa correta é A, coincidindo com o gabarito oficial.
💡 Dica: Lembre-se da estrutura de dados utilizada no algoritmo.
Alternativa por alternativa
A estrutura union-find mantém parent[x] apontando para o pai de x; a operação find segue esses ponteiros até o representante (root); path compression atualiza parent para otimizar buscas.
O aluno confunde a técnica de compressão de caminho, que aparece no nome 'caminho', com uma estrutura de dados própria que armazenaria os representantes. Acredita que existe um vetor separado dedicado a registrar caminhos até a raiz.
Por que engana: Confundir a função do vetor 'pai' com a função dos outros vetores, como 'tamanho' ou 'peso', que têm propósitos diferentes na estrutura union-find.
O aluno associa a estrutura union-find ao vetor de tamanhos usado na união por tamanho e supõe que ele guarda a raiz de cada conjunto. Não percebe que o tamanho é um atributo auxiliar e que a raiz continua sendo identificada pelo vetor 'pai'.
O aluno pensa que, como Kruskal ordena arestas por peso, o vetor de pesos é a estrutura que controla os conjuntos. Confunde os dados de entrada do grafo com a estrutura auxiliar de conjuntos disjuntos.
O aluno lembra que Kruskal precisa marcar vértices visitados, como em uma busca, e supõe que essa marcação define os representantes. Mistura a lógica de visitação de grafos com a de conjuntos disjuntos.
Raio-X da questão
algoritmo de Kruskal
avaliacao
estrutura de dados · algoritmos de grafos
Revisar a estrutura union-find e suas operações.
Confundir a função do vetor 'pai' com a função dos outros vetores, como 'tamanho' ou 'peso', que têm propósitos diferentes na estrutura union-find.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 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