Projete uma solução computacional (estrutura de dados e algoritmo em alto nível) que, dado um grafo não…

Questão

Projete uma solução computacional (estrutura de dados e algoritmo em alto nível) que, dado um grafo não direcionado representado por lista de adjacência, um vértice fonte s e um inteiro k=0, retorne o conjunto de vértices alcançáveis a partir de s em no máximo k arestas. Descreva a ideia, a complexidade temporal e um exemplo de aplicação.

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

Resposta esperada

usar busca em largura (BFS) limitada por profundidade k. Estruturas: lista de adjacência, fila, vetor distancia inicializado com 8 e visited booleana. Passos: inicialize fila com s, distancia[s]=0; enquanto fila não vazia: v=dequeue; para cada w em adj[v]: se distancia[w]==8 e distancia[v]+1 = k então distancia[w]=distancia[v]+1; enqueue(w). Ao final, retornar {v | distancia[v] = k}. Complexidade: visita cada aresta no máximo uma vez entre vértices explorados até profundidade k; no pior caso explora todo o grafo: O(V+E). Memória: O(V+E) para lista e O(V) para estruturas auxiliares. Exemplo de aplicação: em rede social, encontrar todos os usuários a até k hops (amigos de amigos até k) para recomendações ou análise de alcance de uma publicação.

Explicação

A solução proposta utiliza a busca em largura, que é adequada para explorar grafos e identificar todos os vértices alcançáveis dentro de um limite de arestas. A complexidade temporal e espacial é eficiente, permitindo que a abordagem funcione bem mesmo em grafos grandes. O exemplo de aplicação em redes sociais ilustra a relevância prática da solução, demonstrando como ela pode ser usada para análise de conexões.

Raio-X da questão

Questões parecidas com resolução

• Na creche, a equipe organiza o lanche das salas Girassol e Nuvem. A tabela mostra o que já foi feito: | Tarefa | Sala…
• Em um canavial, um gráfico de barras descrito em palavras mostra os pontos secos encontrados em cada trecho: trecho A, 2…
• Durante uma atividade sobre vulcões, Bia precisa montar um aviso com três informações: presença de fumaça, tremores e…
• Antes da aula, Davi precisa arrumar sua mochila. Como Davi pode fazer isso em até três partes, uma de cada vez?
• — Não basta publicar as imagens das cartas — alertou a coordenadora do arquivo municipal ao planejar uma plataforma…
• Projete um algoritmo, em passos claros, para fragmentar um arquivo em pacotes, numerá-los, aplicar checksum e…

Todas as questões de Decomposição