Abordo aqui uma questão de concurso, da banca UFV-MG, prova UFV – 2017 – UFV-MG – Técnico de Tecnologia da Informação.
É uma questão que confunde por ter uma “pegadinha” com uma possível resposta incorreta.
Considere o grafo abaixo de uma instância da estrutura de dados do tipo árvore binária:
Aplicando o algoritmo de busca em profundidade nessa árvore e considerando o cruzamento de árvore em in-ordem, a alternativa que apresenta CORRETAMENTE a sequência de visitas desse algoritmo é:
Escolha uma opção:
- a) 1, 2, 3, 4, 5, 6, 7, 8
- b) 4, 2, 8, 5, 1, 6, 3, 7
- c) 1, 2, 4, 5, 8, 3, 6, 7
- d) 4, 8, 5, 2, 6, 7, 3, 1
Questão sobre busca em profundidade
Quando falamos apenas em Busca em Profundidade (DFS) sem especificar o caminhamento (in-ordem, pós-ordem, etc.), o padrão mais comum em algoritmos de computação é o Pré-Ordem (Pre-order).
Nesse caso, a regra é: Raiz -> Esquerda -> Direita. Ou seja, você visita o nó no momento em que visita ele pela primeira vez, antes de explorar seus filhos. Isso remete a resposta para a alternativa “c”.
Bom, como eu disse que existia uma “pegadinha” para a resposta, além de indicar que existe possível diferença entre o caminho pré-ordem e in-ordem (o caminho in-ordem é o pedido na questão), já deve ter ficado entendido que a alternativa “c” não é correta. Mesmo assim, vejamos como seria percorrida a árvore.
Passo-a-Passo (Pré-Ordem):
- Visita a Raiz (1).
- Desce para a esquerda: Visita (2).
- Desce para a esquerda de 2: Visita (4). (Fim da linha, volta para 2).
- Desce para a direita de 2: Visita (5).
- Desce para a esquerda de 5: Visita (8). (Fim da linha, volta para 1).
- Desce para a direita da raiz (1): Visita (3).
- Desce para a esquerda de 3: Visita (6).
- Desce para a direita de 3: Visita (7).
A sequência de visitação da DFS (Pré-ordem) é: 1 – 2 – 4 – 5 – 8 – 3 – 6 – 7
Questão sobre busca em profundidade
Para encontrar a sequência de visitas em in-ordem (in-order) de uma árvore binária, seguimos a regra: Esquerda -> Raiz -> Direita. No caso de uma busca em profundidade (DFS) com esse percurso, visitamos recursivamente a subárvore esquerda, depois o nó atual (raiz local) e, por fim, a subárvore direita.
Passo a Passo do Percurso:
- Partindo da Raiz (1): Vamos para a esquerda (2).
- No nó (2): Vamos para a esquerda (4).
- No nó (4): Não há filhos à esquerda. Visita: 4. Não há filhos à direita. Volta para (2).
- De volta ao nó (2): Visita: 2. Agora vamos para a direita (5).
- No nó (5): Vamos para a esquerda (8).
- No nó (8): Não há filhos. Visita: 8. Volta para (5).
- De volta ao nó (5): Visita: 5. Não há filhos à direita de (5). Volta para (1).
- De volta ao nó (1): Visita: 1. Agora vamos para a direita (3).
- No nó (3): Vamos para a esquerda (6).
- No nó (6): Não há filhos. Visita: 6. Volta para (3).
- De volta ao nó (3): Visita: 3. Agora vamos para a direita (7).
- No nó (7): Não há filhos. Visita: 7.
A sequência de visitação da DFS (in-ordem) é: 4 – 2 – 8 – 5 – 1 – 6 – 3 – 7. Ou seja, a alternativa “b”.