Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — UFSM 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg621770
Banca
UFSM
Órgão
UFSM
Ano
2025
Nível
Superior
Cargo
Professor EBTT - Área: Ciências Exatas e da Terra/Ciência da Computação/ Metodologia e Técnicas da Computação
Considere um grafo dirigido G=(N, A) em que o conjunto N é composto por seis nós, numerados de 1 a 6. O conjunto de arcos A é o apresentado a seguir na forma de lista de adjacência:1 → 2, 4, 52 → 33 → 24 → 2, 35 → 46 → 1, 5Tendo em vista a estrutura desse grafo, considere as afirmativas a seguir.I → Trata-se de um grafo conexo, porém não fortemente conexo.II → A sequência de nós 6, 1, 5, 2, 4, 3 representa uma possível ordem de visita aos nós para um percurso em amplitude.III → A sequência de nós 6, 1, 2, 4, 3, 5 representa uma possível ordem de visita aos nós para um percurso em profundidade.IV → Existe um caminho ligando os nós 6 e 2 composto por uma sequência de 5 arcos distintos entre si.Estão corretas
Aapenas I e III.
Bapenas I e IV.
Capenas II e III.
Dapenas I, II e IV.
Eapenas II, III e IV.
Revelar gabarito e comentário▾
GabaritoD — apenas I, II e IV.
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”.
Grafo Dirigido: Análise de Conexidade e Percursos
Gabarito: letra D (apenas I, II e IV). O grafo é conexo mas não fortemente conexo; a sequência BFS 6,1,5,2,4,3 é válida; a sequência DFS sugerida é impossível; e existe um caminho de 6 a 2 com 5 arcos distintos.
O grafo dado possui seis nós (1 a 6) e as seguintes arestas:
1 → 2, 4, 5
2 → 3
3 → 2
4 → 2, 3
5 → 4
6 → 1, 5
A seguir, cada afirmativa é analisada.
Afirmativa
Análise
Conclusão
I – Grafo conexo, mas não fortemente conexo
O grafo subjacente é conexo, mas não há caminho dirigido de nenhum nó para o nó 6.
✅ Correta
II – BFS: 6, 1, 5, 2, 4, 3
Simulação a partir de 6: visita 6, enfileira 1 e 5; depois 1 (enfileira 2,4); depois 5; depois 2 (enfileira 3); depois 4; depois 3. Sequência válida.
✅ Correta
III – DFS: 6, 1, 2, 4, 3, 5
Após 2, o DFS deve ir para 3 (único vizinho), não para 4. A sequência fere a definição de profundidade.
❌ Incorreta
IV – Caminho de 6 a 2 com 5 arcos distintos
Caminho: 6→1→5→4→2 (4 arcos) ou 6→1→2 (2 arcos). Para 5 arcos: 6→1→5→4→3→2 (5 arcos distintos).
✅ Correta
Item I — ✅ Correto
O grafo subjacente (ignorando direções) é conexo: todos os nós estão ligados por arestas não direcionadas. Porém, para ser fortemente conexo, deve existir um caminho dirigido entre qualquer par de nós em ambos os sentidos. Note que o nó 6 é origem de arestas para 1 e 5, mas não recebe arestas de nenhum outro nó (ninguém aponta para 6). Assim, não há caminho dirigido de nenhum outro nó para o 6, logo o grafo não é fortemente conexo. Afirmativa correta.
Item II — ✅ Correto
Uma busca em amplitude (BFS) a partir do nó 6 pode produzir a sequência 6, 1, 5, 2, 4, 3. Simulemos:
Partindo de 6, visitamos 6 e enfileiramos seus vizinhos 1 e 5 (em qualquer ordem).
Supondo que 1 seja desenfileirado primeiro: visitamos 1 e enfileiramos seus vizinhos não visitados: 2 e 4 (5 já está na fila).
Em seguida desenfileiramos 5: visitamos 5 e seus vizinhos (4 já enfileirado, portanto nada novo).
Depois 2: visitamos 2 e enfileiramos 3.
Depois 4: visitamos 4 (seus vizinhos 2 e 3 já visitados/enfileirados).
Uma busca em profundidade (DFS) a partir de 6, seguindo a sequência 6, 1, 2, 4, 3, 5, é impossível. Vejamos: após visitar 6 e 1, o próximo passo é 2 (ok). No entanto, a partir de 2 a única aresta é para 3. Em DFS, uma vez em 2, o algoritmo deve seguir para 3 (aprofundar) antes de retroceder para explorar outros vizinhos de 1. Portanto, após 2, o próximo visitado deve ser 3, não 4. Qualquer ordem que coloque 4 antes de 3 (após 2) fere a definição de DFS. A sequência correta a partir de 6 (com ordenação alfabética ou escolha específica) seria algo como 6, 1, 2, 3, 4, 5 ou 6, 1, 4, 2, 3, 5. A sequência dada não corresponde a nenhuma DFS possível. Afirmativa falsa.
NÃO CAIA NESSA!
A banca explora a confusão entre BFS e DFS. No item III, a sequência parece razoável, mas o erro sutil é que após 2, o DFS deve ir para 3 (única aresta de 2). O candidato pode esquecer que o algoritmo sempre aprofunda antes de voltar. Nos itens, verifique sempre se a transição entre vértices consecutivos na sequência é uma aresta direta e se respeita o princípio da pilha.
Item IV — ✅ Correto
Existe um caminho dirigido do nó 6 ao nó 2 com exatamente 5 arcos distintos (cada aresta usada uma única vez): 6 → 1 → 5 → 4 → 3 → 2 Contagem de arcos:
6→1 (1)
1→5 (2)
5→4 (3)
4→3 (4)
3→2 (5)
São 5 arestas, todas distintas. Afirmativa correta.
Conclusão: Afirmativas corretas: I, II e IV. Portanto, a alternativa que as reúne é a letra D (apenas I, II e IV).