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
- Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência dos bairros…
- Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
- Em um grafo não direcionado representado por lista de adjacência, que variável e que operação um algoritmo deve usar…
- Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V vértices…
- Projete um algoritmo em linguagem descritiva que, dada uma lista de adjacência de um grafo qualquer, retorne uma lista…
- Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não…
🔎 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