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

• Descreva em pseudocódigo um algoritmo que, dada uma rede representada por um grafo com n nós e lista de arestas…
• Descreva um algoritmo em pseudocódigo que, dado um grafo dirigido acíclico e dois vértices s e t, encontra um caminho de…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Projete um algoritmo em pseudocódigo que, dado um grafo dirigido que modela rotas entre cidades (vértices), uma origem…
• Projete um algoritmo em pseudocódigo que, dada uma árvore enraizada representada por nós com referências a filhos e uma…
• Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…

Todas as questões de Decomposição