Em um algoritmo que identifica componentes conexas em um grafo não direcionado usando DFS, qual variável (tipo…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um algoritmo que identifica componentes conexas em um grafo não direcionado usando DFS, qual variável (tipo de dado) costuma armazenar a identificação do componente a que pertence cada vértice?
- A) Uma matriz booleana que indica se um vértice é visitado ou não.
- B) Uma lista ligada de strings que armazena nomes dos vértices.
- C) Uma lista de objetos que contém propriedades de cada vértice, mas não seus IDs.
- D) Um vetor inteiro component_id[v] que armazena o id do componente para cada vértice v.
- E) Um vetor de caracteres que armazena letras correspondentes a cada vértice.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Em um algoritmo de componentes conexas com DFS, percorremos o grafo a partir de cada vértice ainda não visitado. Cada chamada da DFS a partir de um novo vértice inicia um novo componente, e todos os vértices alcançados nessa busca pertencem ao mesmo componente.
- Para registrar a qual componente cada vértice pertence, precisamos de uma estrutura que associe cada vértice v a um número identificador do componente. Um vetor de inteiros indexado pelo vértice, como component_id[v], faz exatamente isso: o índice é o vértice e o valor é o número do componente.
- Por que as outras estão erradas: A) a matriz booleana só diz se o vértice foi visitado, não a qual componente ele pertence; B) uma lista de strings guarda nomes, não identificadores de componente; C) a lista de objetos sem IDs não atende ao objetivo de identificar o componente; E) um vetor de caracteres não é adequado, pois o número de componentes pode ser grande e a identificação deve ser numérica.
- Conclusão: a alternativa correta é a D, que coincide com o gabarito oficial.
💡 Dica: Considere as estruturas de dados utilizadas em algoritmos de grafos.
Alternativa por alternativa
Confunde o controle de visitas da DFS com a identificação do componente. A matriz booleana indica apenas se o vértice já foi visitado, o que é necessário para o algoritmo, mas não informa a qual componente o vértice pertence.
Por que engana: Confundir a função de uma matriz booleana com a identificação de componentes, pensando que ela armazena informações sobre os IDs dos vértices.
Acredita que o armazenamento deve guardar nomes ou rótulos textuais dos vértices. A identificação do componente é um número, e a lista ligada de strings não associa vértices a componentes.
Entende que os objetos de vértice podem ser suficientes sem um campo de identificação. Sem um ID de componente armazenado, não há como saber a qual componente cada vértice pertence.
Durante a DFS atribui-se um identificador (inteiro) a cada vértice quando a nova componente é explorada; um array inteiro permite acesso e comparação O(1).
Imagina que letras servem como rótulos de componentes, o que limita o número de componentes a poucas letras e não é a forma usual de representar identificadores numéricos em algoritmos.
Raio-X da questão
componentes conexas em grafos
avaliacao
estruturas de dados · algoritmos de busca
Revisar o uso de estruturas de dados em algoritmos de grafos.
Confundir a função de uma matriz booleana com a identificação de componentes, pensando que ela armazena informações sobre os IDs dos vértices.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
- Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em uma rede…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada…
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
- Descreva um algoritmo baseado em DFS para identificar vértices de articulação (cut vertices) em um grafo não direcionado…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog