Descreva em pseudocódigo um algoritmo que, dado um grafo não direcionado representado por listas de adjacência…

Questão

Descreva em pseudocódigo um algoritmo que, dado um grafo não direcionado representado por listas de adjacência e um limiar t, produza uma nova lista de adjacência contendo apenas as arestas com peso = t. Indique as variáveis-chave e analise a complexidade temporal em termos de n e m.

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

Resposta esperada

Variáveis-chave: adj_in (lista de adjacência de entrada), adj_out (lista de adjacência resultado), t (limiar), n (número de vértices), m (número de arestas), u,v,w (vértice e peso temporários), visitedEdgeSet (opcional para evitar duplicatas em grafos não direcionados). Pseudocódigo: 1. Inicialize adj_out como lista vazia para cada vértice 1..n. 2. Se desejar evitar duplicatas, inicialize visitedEdgeSet = vazio. 3. Para cada vértice u de 1 a n: 4. Para cada entrada (v, w) em adj_in[u]: 5. Se w = t então 6. Se grafo é não direcionado e (min(u,v),max(u,v)) em visitedEdgeSet então continue 7. Acrescente (v, w) em adj_out[u] 8. Se grafo é não direcionado então 9. Acrescente (u, w) em adj_out[v] 10. Adicione (min(u,v),max(u,v)) em visitedEdgeSet (se usado) Complexidade temporal: percorre-se cada lista de adjacência uma vez. Testar peso e inserir em adj_out é O(1) amortizado; com n vértices e m entradas nas listas totais, o tempo é O(n + m). Se usar visitedEdgeSet (uma tabela hash) para evitar duplicatas em grafos não direcionados, cada operação permanece O(1) amortizado, mantendo O(n + m) no total. Observações: para entrada onde cada aresta aparece duas vezes (não direcionado), o algoritmo percorre ambas as ocorrências; o uso de visitedEdgeSet permite garantir que a aresta seja adicionada uma vez em termos de lógica de construção, embora a iteração ainda examine O(m) entradas.

Explicação

O pseudocódigo apresentado aborda de forma clara a construção de uma nova lista de adjacência filtrando arestas com peso igual ao limiar t, considerando a estrutura de um grafo não direcionado. A análise da complexidade temporal é precisa, pois considera tanto o número de vértices quanto o número de arestas, garantindo que o algoritmo opere de maneira eficiente em relação ao tamanho do grafo. Além disso, a inclusão de uma estrutura para evitar duplicatas demonstra uma compreensão aprofundada das características dos grafos não direcionados.

Raio-X da questão

Questões parecidas com resolução

• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de adjacência…
• Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência dos bairros…
• Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V vértices…
• Projete um algoritmo (pseudocódigo) baseado em Kruskal ou Prim que, dado um grafo conectado ponderado (dados: lista de…
• Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.