Guia passo a passo para algoritmos Traversais em árvores e gráficos com cálculos de exemplo

Algoritmos de Traversal são essenciais para explorar árvores e gráficos na ciência da computação. Eles ajudam a visitar todos os nós sistematicamente para executar operações como pesquisar, ordenar ou analisar estruturas. Este guia fornece uma visão geral passo a passo de métodos de travessia comuns com cálculos de exemplo.

Algoritmos Traversais de Árvore

Algoritmos de viagem em árvore visitam nós em uma ordem específica. Os métodos mais comuns são em ordem, pré-ordem e pós-ordem de travessia. Cada um serve diferentes propósitos e segue uma sequência única de visitas.

Traversal em pedido

A viagem em ordem visita a sub- árvore esquerda, o nó atual, e depois a sub- árvore direita. É frequentemente usada para recuperar dados em ordem ordenada de árvores de pesquisa binária.

Exemplo: Para uma árvore binária com nós 4, 2, 5, 1, 3, a sequência de travessia em ordem é 1, 2, 3, 4, 5.

Traversal pré-ordenado

A viagem de pré- ordem visita primeiro o nó actual, depois a sub- árvore esquerda, seguida da sub- árvore direita. É útil para copiar árvores ou criar expressões de prefixos.

Exemplo: Usando a mesma árvore, a sequência pré-encomenda é 4, 2, 1, 3, 5.

Traversal pós-ordenado

A travessia pós- ordem visita a sub- árvore esquerda, a sub- árvore direita, depois o nó actual. É frequentemente usado para apagar árvores ou avaliar expressões pós- fixas.

Exemplo: Para a mesma árvore, a sequência pós-ordem é 1, 3, 2, 5, 4.

Algoritmos de Traversal Gráfico

Algoritmos de Traversal de Gráfico exploram nós em um gráfico. Os dois métodos principais são a pesquisa de Primeiros Graus (BFS) e a pesquisa de Primeiros Graus (DFS). Eles são usados em análise de rede, pathfiding, e muito mais.

Primeira Pesquisa de Ampla (BFS)

O BFS explora os vizinhos nível por nível, começando a partir de um nó de origem. Ele usa uma fila para manter o controle dos nós para visitar a seguir.

Exemplo: A partir do nó A em um gráfico, o BFS visita nós em ordem: A, B, C, D, E, com base na sua proximidade.

Pesquisa de Profundidade (DFS)

O DFS explora tanto quanto possível ao longo de cada ramo antes de retroceder. Ele usa uma pilha ou recursão para gerenciar a travessia.

Exemplo: A partir do nó A, DFS pode visitar nós em ordem: A, B, D, E, C.