Projete um algoritmo em linguagem descritiva que, dada uma lista de adjacência de um grafo qualquer, retorne…

Questão

Projete um algoritmo em linguagem descritiva que, dada uma lista de adjacência de um grafo qualquer, retorne uma lista com todos os vértices isolados (grau 0). No enunciado use os termos 'algoritmo', 'lista de adjacência' e 'vértice'.

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

Resposta esperada

Algoritmo (lista de adjacência -> lista_isolados): 1) inicialize lista_isolados vazia; 2) para cada vértice v na lista de adjacência faça: 2.1) se a lista de vizinhos de v está vazia (ou comprimento 0) então adicione v a lista_isolados; 3) retorne lista_isolados. Complexidade: percorre todos os vértices e suas listas de vizinhos ? O(V + E).

Explicação

O algoritmo proposto identifica vértices isolados ao verificar se a lista de vizinhos de cada vértice está vazia, o que indica que o vértice não possui conexões. A adição dos vértices isolados a uma lista separada permite que todos sejam coletados de forma eficiente. A complexidade O(V + E) é adequada, pois considera o tempo necessário para percorrer todos os vértices e suas respectivas conexões.

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…
• Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não…
• Em um grafo simples não direcionado representado por lista de adjacência, o que caracteriza um vértice isolado e como…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
• Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
• 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 Programação - Propriedades de grafos