Em uma lista de adjacência que representa um grafo ponderado, como atualizar de forma consistente o campo…

Questão

Em uma lista de adjacência que representa um grafo ponderado, como atualizar de forma consistente o campo 'peso' da aresta entre dois vértices u e v para um novo valor w em um grafo não direcionado?

1. A) Remover a aresta e adicionar uma nova com o peso w.
2. B) Atualizar o peso apenas na lista de v, sem modificar a de u.
3. C) Atualizar apenas o peso da aresta em um dos vértices se o grafo for ponderado.
4. D) A atualização deve ser feita apenas se o grafo for conexo.
5. E) Localizar v na lista de adjacência de u e definir seu peso para w; e também atualizar u na lista de v para w.

✅ Resposta correta: alternativa E

Resolução passo a passo

1. Em um grafo não direcionado, cada aresta u-v aparece duas vezes na lista de adjacência: uma na lista de u (apontando para v) e outra na lista de v (apontando para u). Por isso, a atualização precisa alterar as duas entradas para que o grafo continue consistente.
2. Para atualizar, primeiro localiza-se v na lista de adjacência de u e define-se o peso dessa entrada como w.
3. Em seguida, localiza-se u na lista de adjacência de v e define-se também o peso dessa entrada como w. Assim, as duas representações da mesma aresta passam a ter o mesmo peso.
4. A alternativa E descreve exatamente esses dois passos, por isso é a correta, e coincide com o gabarito oficial.
5. A alternativa A não é a forma usual de atualizar o campo peso, pois remover e adicionar a aresta exige fazer as duas operações nas duas listas e custa mais, além de a descrição não garantir essa consistência. A alternativa B está errada porque atualizar só uma das listas deixa o grafo inconsistente, com pesos diferentes para a mesma aresta. A alternativa C está errada porque, em um grafo não direcionado, não se deve atualizar só um dos lados, e a condição 'se o grafo for ponderado' não faz sentido, já que o enunciado já diz que o grafo é ponderado. A alternativa D está errada porque a conectividade do grafo não influencia a atualização de uma aresta existente.

💡 Dica: Considere a estrutura da lista de adjacência ao atualizar o peso.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Ao representar um grafo ponderado com listas de adjacência, qual tipo de variável deve armazenar o peso de cada aresta e…
• Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
• Ao representar um grafo não direcionado, como a aresta que conecta dois vértices é geralmente considerada?
• Ao representar um grafo com listas de adjacência em um programa, que vantagem traz manter uma variável 'grau' para cada…
• Em um grafo ponderado que modela ruas de uma cidade, como representar na aresta tanto a distância quanto o tempo de…
• Em um algoritmo de Dijkstra implementado para um grafo ponderado com listas de adjacência, qual variável armazena a…

Todas as questões de Construir conhecimento usando técnicas e tecnologias computacionais, produzindo informação e/ou artefatos de forma criativa, com respeito às questões legais, que proporcionem experiências para si e os demais.