Escreva um algoritmo em linguagem descritiva que, recebendo a matriz de adjacência de um grafo não direcionado…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Elaborar algoritmos que envolvam instruções sequenciais, de repetição e de seleção usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Escreva um algoritmo em linguagem descritiva que, recebendo a matriz de adjacência de um grafo não direcionado com V vértices, calcule o grau de cada vértice e retorne o índice do vértice com maior grau. Use apenas vetores e loops.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Inicialize vetor grau[0..V-1] com zeros. Para i de 0 até V-1: Para j de 0 até V-1: Se matriz[i][j] != 0 então grau[i] ? grau[i] + 1 (maxIdx ? 0) Para i de 1 até V-1: Se grau[i] > grau[maxIdx] então maxIdx ? i Retorne maxIdx (Complexidade O(V^2); para grafo não direcionado a soma da linha i dá o grau de i.)
Explicação
O algoritmo percorre a matriz de adjacência, contando as conexões de cada vértice para calcular seu grau, o que é essencial para identificar o vértice com maior grau. A comparação entre os graus dos vértices é feita em um loop separado, garantindo que o índice do vértice com maior grau seja encontrado de forma eficiente. A complexidade O(V^2) é adequada para esse tipo de problema, pois envolve a análise de cada elemento da matriz para determinar as conexões.
Raio-X da questão
grafo não direcionado
avaliacao
matriz de adjacência · grafo não direcionado
Revisar conceitos de grafos e matrizes de adjacência.
O aluno pode confundir o conceito de grau de um vértice, somando os elementos da matriz de forma incorreta ou não considerando a simetria da matriz.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em uma usina, cada estado de uma turbina é registrado com um código de dois bits: | Estado | Código | |---|---| | Parada…
- No controle de um satélite, um gráfico de barras descrito pela equipe registra: com o sistema operacional iniciado, o…
- O clube de jogos da escola vai usar um programa simples para registrar cada participante. Em cada cadastro, a pessoa…
- Na horta da escola, uma estação simples registra a temperatura informada por um sensor. O programa deve mostrar essa…
- Pesquisadores acompanham o funcionamento de um robô que cuida de seis placas solares em uma estação de pesquisa. O robô…
- Por que alguns tablets de um centro cultural aparecem como disponíveis, embora estejam guardados para conserto? Para…
🔎 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