Projete um algoritmo em alto nível (pseudocódigo) que converta um grafo simples não direcionado esparso dado…

Questão

Projete um algoritmo em alto nível (pseudocódigo) que converta um grafo simples não direcionado esparso dado por lista de adjacência em uma representação compacta usando duas arrays: head[v] (início) e edges[k] (vértices adjacentes concatenados). Inclua como calcular head e preencher edges e explique custo e como inserir uma nova aresta.

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

Resposta esperada

Resposta modelo (pseudocódigo resumido): 1) contar graus: for v in V: deg[v]=len(adj[v]) 2) prefixo: head[0]=0; for i=1..n-1: head[i]=head[i-1]+deg[i-1] 3) alocar edges[0..2E-1] e pos[]=head 4) for v in V: for u in adj[v]: edges[pos[v]] = u; pos[v] += 1 Inserção de aresta (x,y): append y em edges na posição pos[x] e x em edges em pos[y]; se arrays cheias, realocar (amortizado). Custo de construção O(V+E); inserção O(1) amortizado se usar buffer dinâmico; busca de vizinho explícita exige varredura da faixa head[v]..head[v+1]-1.

Explicação

O algoritmo proposto utiliza a contagem dos graus dos vértices para calcular os índices de início de cada lista de adjacência na array head, garantindo uma representação compacta e eficiente. A alocação da array edges permite armazenar os vértices adjacentes de forma sequencial, facilitando a inserção de novas arestas. O custo de construção é linear em relação ao número de vértices e arestas, e a inserção de arestas é otimizada para ser constante em média, utilizando um buffer dinâmico.

Raio-X da questão

Questões parecidas com resolução

• Lia vai arrumar a mochila para a escola. Como ela pode dividir essa tarefa em partes pequenas?
• O blecaute que interrompeu o funcionamento de um centro comunitário levou os responsáveis a organizar o empréstimo de…
• Uma turma vai criar um aplicativo para organizar tarefas escolares. O grupo percebeu que tentar fazer tudo de uma vez…
• Em um projeto de programação, a turma precisa criar uma solução para várias turmas da escola, com a mesma lógica, mas…
• Uma família quer organizar as despesas do mês em um aplicativo escolar. O processo envolve somar gastos, separar por…
• Ao testar um programa de cadastro, os alunos perceberam que o erro estava apenas na parte que validava o nome do…

Todas as questões de Decomposição