Texto: dada uma matriz de adjacência com valores 0/1 (dado fornecido), qual procedimento aplicável usando uma…

Questão

Texto: dada uma matriz de adjacência com valores 0/1 (dado fornecido), qual procedimento aplicável usando uma variável 'fila' em um algoritmo BFS permite verificar se o grafo é conectado?

1. A) Enfileirar todos os vértices de uma vez e contar visitas.
2. B) Usar apenas uma variável contador para somar graus e comparar com número de vértices.
3. C) Aplicar algoritmo de caminho mínimo de Dijkstra com fila e confirmar distâncias finitas.
4. D) Iniciar em um vértice, usar fila: enfileirar, marcar visitado, processar vizinhos até fila vazia; checar se todos visitados.
5. E) Executar BFS em paralelo em vértices não conectados e comparar resultados.

✅ Resposta correta: alternativa D

Resolução passo a passo

1. O grafo é conectado quando existe caminho entre qualquer par de vértices. Um BFS (busca em largura) a partir de um vértice alcança exatamente os vértices de sua componente conexa.
2. O procedimento com fila funciona assim: escolhe-se um vértice inicial, ele é enfileirado e marcado como visitado; enquanto a fila não estiver vazia, retira-se o primeiro vértice, percorre-se a linha correspondente da matriz de adjacência (valores 1 indicam vizinhos), e cada vizinho ainda não visitado é marcado e enfileirado.
3. Ao terminar (fila vazia), basta verificar se todos os vértices foram marcados como visitados. Se sim, o grafo é conectado; se algum ficou sem marca, ele não é conectado.
4. Por que as outras estão erradas: A) enfileirar todos de uma vez não percorre arestas, então não testa alcançabilidade; B) somar graus não garante conectividade, pois um grafo pode ter graus altos e ainda ser desconexo; C) Dijkstra é algoritmo de caminho mínimo com pesos, não é o procedimento de BFS para conectividade; E) BFS em vértices não conectados não faz sentido, pois a busca a partir deles não alcança o restante do grafo e não gera uma verificação global.
5. Conclusão: a alternativa D descreve corretamente o uso da fila no BFS para testar conectividade, em concordância com o gabarito oficial.

💡 Dica: Considere a inicialização da fila e a verificação de todos os vértices.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em uma rede…
• Descreva em pseudocódigo um algoritmo que, dada uma rede representada por um grafo com n nós e lista de arestas…
• Na tabela de arestas: A-B, B-C, C-D, E-F, aplique o algoritmo de busca em largura (BFS) para determinar quantos nós…
• Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…
• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado conectado e um vértice raiz, construa a…
• Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…

Todas as questões de Programação - Programação usando grafos e árvores