Projete um algoritmo em linguagem descritiva que, dada uma lista de adjacência de um grafo qualquer, retorne…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete um algoritmo em linguagem descritiva que, dada uma lista de adjacência de um grafo qualquer, retorne uma lista com todos os vértices isolados (grau 0). No enunciado use os termos 'algoritmo', 'lista de adjacência' e 'vértice'.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Algoritmo (lista de adjacência -> lista_isolados): 1) inicialize lista_isolados vazia; 2) para cada vértice v na lista de adjacência faça: 2.1) se a lista de vizinhos de v está vazia (ou comprimento 0) então adicione v a lista_isolados; 3) retorne lista_isolados. Complexidade: percorre todos os vértices e suas listas de vizinhos ? O(V + E).
Explicação
O algoritmo proposto identifica vértices isolados ao verificar se a lista de vizinhos de cada vértice está vazia, o que indica que o vértice não possui conexões. A adição dos vértices isolados a uma lista separada permite que todos sejam coletados de forma eficiente. A complexidade O(V + E) é adequada, pois considera o tempo necessário para percorrer todos os vértices e suas respectivas conexões.
Raio-X da questão
vértices isolados em grafos
avaliacao
listas de adjacência · grafo e vértices
Revisar conceitos de grafos e listas de adjacência.
O aluno pode confundir a definição de vértices isolados com vértices de grau 1, listando erroneamente vértices que possuem conexões.
ciencia_tecnologia
criatividade
abstrato
Questões parecidas com resolução
- Para organizar uma exposição escolar, a turma desenhou as ligações diretas entre quatro setores. Cada letra indica um…
- Técnicos instalam uma rede de comunicação por cabos entre os postos de uma reserva ambiental. Os postos são Riacho…
- Moradores acompanham a criação de um aplicativo para orientar deslocamentos durante a feira do bairro. No mapa…
- Durante os preparativos para uma feira de ciências no bairro, a organização desenhou um mapa digital dos caminhos…
- Por que uma rede de aviso precisa continuar funcionando mesmo quando um ponto para de operar? Em uma cidade litorânea, a…
- — Dá para passar por todas as ruas sem repetir nenhuma? — perguntou um morador, ao ver o triciclo do mutirão de coleta…
🔎 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