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

• 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 alto nível que, dado um grafo simples não direcionado representado por lista de adjacência…
• Explique como transformar um multigrafo (arestas paralelas e loops possíveis) em um grafo simples adequado para…
• Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…

Todas as questões de Decomposição