Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V…

Questão

Escreva um algoritmo em linguagem descritiva que, recebendo uma lista de arestas (edge list) de um grafo com V vértices, construa a lista de adjacência; indique estruturas usadas e apresente a complexidade temporal e de espaço.

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

Resposta esperada

Inicialize um vetor/array adjacency de tamanho V, cada posição contém lista vazia. 2) Para cada aresta (u,v[,peso,id]) na edge list: append (v[,peso,id]) em adjacency[u]; se o grafo for não direcionado, append (u[,peso,id]) em adjacency[v]. 3) Se rótulos de vértice não forem 0..V-1, use um dicionário/map de rótulos?índice. Estruturas: vetor de listas (ou map de listas) e, opcionalmente, IDs por aresta. Complexidade: tempo O(V + E) para inicializar e percorrer arestas; espaço O(V + E) para a lista de adjacência (mais O(V) para metadados).

Explicação

A explicação apresenta um passo a passo claro para a construção da lista de adjacência a partir da edge list, utilizando estruturas adequadas como vetores ou dicionários. A complexidade temporal e de espaço é bem justificada, levando em consideração o número de vértices e arestas, o que é essencial para entender a eficiência do algoritmo. Além disso, menciona a necessidade de adaptar o índice dos vértices caso não sejam sequenciais, o que demonstra uma compreensão abrangente do problema.

Raio-X da questão

Questões parecidas com resolução

• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Projete um algoritmo em alto nível (pseudocódigo) que converta um grafo simples não direcionado esparso dado por lista…
• Projete um algoritmo em alto nível que, dado um grafo simples não direcionado representado por lista de adjacência…
• Projete um algoritmo em linguagem descritiva que, dada uma lista de adjacência de um grafo qualquer, retorne uma lista…
• Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência…
• Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…

Todas as questões de Estratégias de solução de problemas - Decomposição