Questão sobre busca em profundidade

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):

1. Visita a Raiz (1).
2. Desce para a esquerda: Visita (2).
3. Desce para a esquerda de 2: Visita (4). (Fim da linha, volta para 2).
4. Desce para a direita de 2: Visita (5).
5. Desce para a esquerda de 5: Visita (8). (Fim da linha, volta para 1).
6. Desce para a direita da raiz (1): Visita (3).
7. Desce para a esquerda de 3: Visita (6).
8. 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:

1. Partindo da Raiz (1): Vamos para a esquerda (2).
2. No nó (2): Vamos para a esquerda (4).
3. No nó (4): Não há filhos à esquerda. Visita: 4. Não há filhos à direita. Volta para (2).
4. De volta ao nó (2): Visita: 2. Agora vamos para a direita (5).
5. No nó (5): Vamos para a esquerda (8).
6. No nó (8): Não há filhos. Visita: 8. Volta para (5).
7. De volta ao nó (5): Visita: 5. Não há filhos à direita de (5). Volta para (1).
8. De volta ao nó (1): Visita: 1. Agora vamos para a direita (3).
9. No nó (3): Vamos para a esquerda (6).
10. No nó (6): Não há filhos. Visita: 6. Volta para (3).
11. De volta ao nó (3): Visita: 3. Agora vamos para a direita (7).
12. 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”.