Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência…

Questão

Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência dos bairros de uma cidade, calcule o grau médio dos vértices. Explique as variáveis usadas, a complexidade temporal e como adaptar o método se os dados vierem como matriz de adjacência.

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

Resposta esperada

Entrada: adj[1..V] onde adj[v] é lista de vizinhos. Variáveis: V = número de vértices; sumDeg = soma dos graus; i itera vértices. Pseudocódigo: sumDeg ? 0 for v from 1 to V do sumDeg ? sumDeg + len(adj[v]) end for avg ? sumDeg / V return avg Complexidade: percorrer todas as listas visita cada aresta duas vezes no caso não dirigido (uma por extremidade), custo O(V + E). Espaço adicional O(1). Adaptação para matriz A (V×V): calcular grau de v como sum(A[v][1..V]); então somar para todos v custa O(V^2) no total e retornar avg = (sum of row sums)/V. Observação: ao receber lista de adjacência, se desejar número de arestas E use E = sumDeg/2 para grafos não direcionados. Para grafos direcionados interpretar sumDeg como soma dos graus de saída e ajustar conforme necessidade.

Explicação

O pseudocódigo apresentado calcula o grau médio dos vértices de um grafo não dirigido ao somar os graus de cada vértice e dividir pelo número total de vértices, garantindo uma abordagem eficiente. A complexidade temporal é O(V + E) devido à necessidade de percorrer cada lista de adjacência, enquanto a adaptação para matriz de adjacência aumenta a complexidade para O(V²), pois é necessário acessar todos os elementos da matriz. Essa explicação abrange tanto a eficiência do algoritmo quanto a adaptação para diferentes representações do grafo.

Raio-X da questão

Questões parecidas com resolução

• Na inscrição para uma oficina de robótica, a escola registra: nome completo, idade, turno escolhido e autorização da…
• — A estação da Praça das Mangueiras está aberta, mas só restam 3 bicicletas — avisou uma moradora ao serviço municipal…
• — Onde estão as peças ásperas em forma de estrela? — perguntou uma criança durante a montagem de um jogo tátil. O…
• — O caminhão só consegue visitar vinte contêineres por noite — avisou a coordenadora da coleta seletiva. Durante a…
• — A tela do empréstimo mostra primeiro a cor e depois a figura — explicou Nora, responsável pela brinquedoteca…
• — A linha 206 passou com a rampa disponível hoje? — perguntou uma usuária no ponto de ônibus. Durante um teste fictício…

Todas as questões de Programação - Tipos de dados