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

• Descreva como um grafo pode ser utilizado para modelar um sistema de transporte público em uma cidade.
• Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
• Ao modelar rotas de ônibus de uma cidade em um algoritmo, qual estrutura de dados (registro, matriz, lista ou grafo) é…
• Um programador precisa representar um sistema de transporte público como um grafo. Cada ponto de ônibus é um nó e as…
• Escolha um exemplo do cotidiano (por exemplo: contatos em um aplicativo da escola ou paradas de ônibus) e descreva como…
• Em um cenário de transporte público, como você poderia utilizar grafos para otimizar as rotas de ônibus em uma cidade?

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