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

• Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de adjacência…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
• Escreva um algoritmo em linguagem descritiva que, recebendo a matriz de adjacência de um grafo não direcionado com V…

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