Sobre a exploração de estruturas de árvore e estruturas de grafo

Introdução

Neste artigo, explicaremos detalhadamente desde os conceitos básicos até os algoritmos de busca para a estrutura de árvore (Tree) e a estrutura de grafo (Graph), que são estruturas de dados que desempenham um papel extremamente importante na ciência da computação.

Na área de estruturas de dados e algoritmos, esses são temas inevitáveis. Em particular, a busca em profundidade (DFS), a busca em largura (BFS) e o algoritmo de Dijkstra (Dijkstra’s Algorithm) para resolver o problema do caminho mais curto aparecem com frequência em concursos de programação e na prática profissional.

1. O básico da estrutura de árvore (Tree)

A estrutura de árvore é uma estrutura de dados adequada para representar dados que têm relações hierárquicas. Ela é usada em várias situações, como sistemas de arquivos, organogramas e árvores DOM HTML.

Uma estrutura de árvore consiste nos seguintes elementos:

• Nó (Node): Elemento que armazena os dados
• Aresta (Edge): Linha que conecta os nós
• Nó raiz (Root Node): O nó que está no topo da árvore. É um nó que não possui um pai.
• Nó folha (Leaf Node): É um nó que não possui filhos.

  graph TD
  "Root" --> "NodeA"
  "Root" --> "NodeB"
  "NodeA" --> "Leaf1"
  "NodeA" --> "Leaf2"
  "NodeB" --> "Leaf3"

Como base para a exploração em uma estrutura de árvore, temos a busca em profundidade (DFS) e a busca em largura (BFS).

2. Busca em Profundidade (DFS: Depth-First Search)

A busca em profundidade é um algoritmo que parte de um certo nó, avança o mais fundo possível e, ao chegar a um beco sem saída, retorna ao nó anterior para continuar a exploração. Usando funções recursivas, pode ser implementado de forma muito simples. Uma estrutura de dados chamada pilha (Stack) também pode ser utilizada.

Exemplo de implementação em Python de DFS em uma estrutura de árvore

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

def dfs_tree(node):
    if node is None:
        return
    print(f"Visitando {node.value}")
    for child in node.children:
        dfs_tree(child)

# Construção da árvore
root = TreeNode("Root")
node_a = TreeNode("A")
node_b = TreeNode("B")
root.children.extend([node_a, node_b])
node_a.children.extend([TreeNode("C"), TreeNode("D")])

print("Travessia DFS:")
dfs_tree(root)

3. Busca em Largura (BFS: Breadth-First Search)

A busca em largura é um algoritmo que parte do nó raiz, explora todos os nós na mesma profundidade e, em seguida, avança para os nós da próxima profundidade. Ele utiliza uma estrutura de dados chamada fila (Queue). É frequentemente usado ao procurar o caminho mais curto.

Exemplo de implementação em Python de BFS em uma estrutura de árvore

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from collections import deque

def bfs_tree(root):
    if root is None:
        return
    queue = deque([root])
    while queue:
        current = queue.popleft()
        print(f"Visitando {current.value}")
        for child in current.children:
            queue.append(child)

print("Travessia BFS:")
bfs_tree(root)

4. O básico da estrutura de grafo (Graph)

A estrutura de grafo consiste em um conjunto de nós (vértices: Vertex) e arestas (bordas: Edge). Uma estrutura de árvore também é um tipo de grafo (um grafo não direcionado sem ciclos, ou um grafo direcionado), mas um grafo geral pode ter ciclos (Cycle) e também é possível ter múltiplos pais.

Existem os seguintes tipos de grafos:

• Grafo não direcionado (Undirected Graph): Um grafo onde as arestas não têm direção
• Grafo direcionado (Directed Graph): Um grafo onde as arestas têm direção
• Grafo ponderado (Weighted Graph): Um grafo onde as arestas têm um peso (custo) configurado

  graph LR
  "A" -- "5" --> "B"
  "A" -- "2" --> "C"
  "B" -- "1" --> "D"
  "C" -- "8" --> "D"
  "C" -- "4" --> "E"
  "D" -- "3" --> "E"

5. Algoritmo de Dijkstra (Dijkstra’s Algorithm)

O algoritmo de Dijkstra é um algoritmo para encontrar o caminho mais curto de um ponto de partida para todos os outros vértices em um grafo ponderado. No entanto, o peso da aresta deve ser não negativo (0 ou mais).

O uso de uma fila de prioridade (Priority Queue) permite que a busca seja realizada de forma eficiente. Como representação matemática, se $ d(v) $ for a distância mais curta do ponto de partida ao vértice $ v $, atualizamos para $ d(v) = \min(d(v), d(u) + w(u, v)) $ em relação ao peso $ w(u, v) $ da aresta $ (u, v) $. Matematicamente, isso satisfaz a propriedade $ d(v) \le d(u) + w(u, v) $. Aqui, escolhemos o caminho em que o $ \text{custo} $ é mínimo.

Exemplo de implementação em Python do algoritmo de Dijkstra

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import heapq

def dijkstra(graph, start):
    # Inicializa as distâncias mais curtas como infinito
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Definição do grafo (formato de lista de adjacência)
graph = {
    'A': {'B': 5, 'C': 2},
    'B': {'D': 1},
    'C': {'D': 8, 'E': 4},
    'D': {'E': 3},
    'E': {}
}

start_node = 'A'
shortest_paths = dijkstra(graph, start_node)
print(f"Caminhos mais curtos de {start_node}: {shortest_paths}")

Adicionaremos mais descrições abaixo sobre explicações detalhadas do algoritmo e notas suplementares. Estes são extremamente importantes.