Escreva um pseudocódigo que, dado um grafo não orientado representado por lista de adjacência, retorne o…

Questão

Escreva um pseudocódigo que, dado um grafo não orientado representado por lista de adjacência, retorne o número de componentes conectados. Explique brevemente a lógica e a complexidade temporal.

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

Resposta esperada

Pseudocódigo (entrada: adj lista G): 1. visited ? conjunto vazio 2. componentes ? 0 3. para cada vértice v em G: 4. se v ? visited: 5. componentes ? componentes + 1 6. realizar DFS/ BFS a partir de v: fila/stack ? [v]; marcar v como visited 7. enquanto fila/stack não vazia: 8. u ? remover(fila/stack) 9. para cada w em G[u]: 10. se w ? visited: marcar w; inserir w em fila/stack 11. retornar componentes Lógica: percorre todos os vértices; a cada início de busca em vértice não visitado encontra uma nova componente. Complexidade: usando lista de adjacência, cada vértice e cada aresta são processados no máximo uma vez, logo O(n + m).

Explicação

O pseudocódigo utiliza uma abordagem de busca em profundidade (DFS) ou busca em largura (BFS) para explorar todos os vértices de um grafo, contando quantas vezes inicia uma nova busca a partir de um vértice não visitado, o que indica a descoberta de uma nova componente conectada. A complexidade O(n + m) reflete que cada vértice e cada aresta são analisados uma única vez, garantindo eficiência na contagem das componentes. Essa metodologia é fundamental para entender a estrutura de conexões em grafos não orientados.

Raio-X da questão

Questões parecidas com resolução

• Em um dia de trabalho, uma entregadora que usa um aplicativo recebe R$ 12 por entrega. Ela gasta R$ 3 por entrega com…
• Em uma gráfica, a quantidade de tinta adicional é registrada em função de uma medida-padrão q. Para um pedido, a…
• Em uma gráfica, uma máquina imprime livros a uma taxa constante. Se trabalha sozinha, produz 120 páginas por hora…
• — O desconto só incide sobre as oficinas, não sobre a entrada — explicou a atendente a um visitante. Na feira municipal…
• Uma associação de ambulantes realizou uma pesquisa sobre o gasto mensal com internet móvel. Os dados foram organizados…
• Uma secretaria municipal recebeu R$ 390 para inscrever dois agentes em um curso, ambos com o mesmo número de oficinas…

Todas as questões de Leitura e interpretação de tabelas e gráficos (de colunas ou barras simples ou múltiplas) referentes a variáveis categóricas e variáveis numéricas