Um mapa de linhas de ônibus pode ser representado por um grafo em que vértices são pontos de parada e arestas…

Questão

Um mapa de linhas de ônibus pode ser representado por um grafo em que vértices são pontos de parada e arestas são trechos entre paradas. Descreva passo a passo como converter esse mapa em uma lista de adjacência, como identificar componentes desconexas e como atualizar a lista quando uma parada é fechada temporariamente, justificando escolhas de modelagem.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Modelagem: cada parada = vértice; cada trecho = aresta; decida se arestas são orientadas (sentidos separados) ou ponderadas (tempo/distância). 2) Conversão: percorra todas as arestas; para cada aresta (u,v) adicione v à lista de u e u à lista de v (ou somente na direção, se orientado). 3) Componentes: use busca em largura (BFS) ou profundidade (DFS) a partir de vértices não visitados para marcar cada componente; cada execução identifica um componente desconexo. 4) Atualização ao fechar parada p: remova o vértice p da estrutura e elimine todas as ocorrências de p nas listas de adjacência dos vizinhos; registre arestas removidas e, se necessário, atualize pesos alternativos. 5) Decisões de modelagem: para rotas com sentido único use grafo orientado; para horários e capacidades inclua pesos ou atributos nas arestas; ao fechar temporariamente, mantenha histórico para restaurar facilmente. Explique impacto na conectividade e como recomputar componentes se a remoção separar subgrafos.

Explicação

A explicação aborda de forma clara e sequencial o processo de conversão de um mapa de linhas de ônibus em uma lista de adjacência, detalhando a modelagem necessária e os passos para identificar componentes desconexas. Além disso, inclui a atualização da estrutura ao fechar paradas, enfatizando a importância de manter a integridade dos dados e a conectividade do grafo. A justificativa das escolhas de modelagem demonstra uma compreensão das implicações práticas na representação do sistema de transporte.

Raio-X da questão

Questões parecidas com resolução

• — Se dois voluntários entregarem o mesmo aparelho, como saberemos onde ele está? — perguntou uma visitante ao chegar à…
• Monitores de um centro esportivo estão testando um placar digital para partidas de futsal, vôlei e basquete. Antes de…
• Por que duas pessoas que leem uma história na tela podem chegar a trechos diferentes? Para uma mostra comunitária…
• Caminhões recolhem livros em uma campanha fictícia para renovar bibliotecas de bairro. Em cada ponto de coleta…
• — Se chegarem novos tipos de objetos, vou precisar copiar tudo outra vez? — perguntou Joana, que ajuda no ponto de…
• — Se enviarmos as caixas sem organização, um abrigo poderá receber itens que não pediu e outro ficará sem produtos…

Todas as questões de Estratégias de solução de problemas - Decomposição