Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — CESPE / CEBRASPE 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
ce202055
Banca
CESPE / CEBRASPE
Órgão
EMBRAPA
Ano
2025
Nível
Superior
Cargo
Pesquisador – Área: Gestão da Informação – Subárea: Engenharia de Dados
Julgue o item que se segue, relativo às estruturas de dados em árvores.Para um dígrafo D (V, E) conexo, em que cada vértice possua pelo menos uma aresta de saída, ao se aplicar a busca em profundidade a partir de um vértice , todos os vértices de serão visitados.
CCerto
EErrado
Revelar gabarito e comentário▾
GabaritoE — Errado
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Busca em Profundidade (DFS) em dígrafos
❌ ERRADO. A afirmação está incorreta. Em um dígrafo, a busca em profundidade (DFS) a partir de um vértice visita apenas os vértices alcançáveis por caminhos direcionados a partir de . A condição de que todo vértice tenha pelo menos uma aresta de saída não garante que o digrafo seja fortemente conexo, nem que todos os vértices sejam alcançáveis a partir de um nó arbitrário.
Contraexemplo: Considere o dígrafo abaixo, que é fracamente conexo (vértices 1, 2 e 3 ligados na orientação) e cada vértice tem pelo menos uma aresta de saída (1→2, 2→3, 3→3 – laço próprio).
Aplicando DFS a partir do vértice 2, os vértices visitados são 2 e 3. O vértice 1 não é visitado, pois não há caminho direcionado de 2 para 1. Portanto, a afirmação de que "todos os vértices serão visitados" é falsa.
PEGA ESSA DICA!
Em grafos direcionados, o termo "conexo" geralmente se refere à conexidade fraca (o grafo subjacente não dirigido é conexo). Para que DFS a partir de qualquer nó visite todos os vértices, o grafo precisa ser fortemente conexo (existe caminho bidirecional entre qualquer par). A condição de out-degree ≥ 1 para todos os vértices não é suficiente para garantir forte conexidade.