review-graphs-and-trees
Voltar à Trilha

Revisão de Grafos e Árvores

--- id: 67f39e06b8a11b2de9ccd361 title: Revisão de Grafos e Árvores challengeType: 31 dashedName: review-graph-and-trees --- # --description--

Visão Geral dos Grafos

Um grafo é um conjunto de nós (vértices) conectados por arestas (conexões). Cada nó pode se conectar a vários outros nós, formando uma rede. Os diferentes tipos de grafos incluem:
  • Direcionado: as arestas têm uma direção (de um nó para outro), frequentemente representadas com linhas retas e setas.
  • Não direcionado: as arestas não têm direção, representadas por linhas simples.
  • Vértice: cada nó está associado a um rótulo ou identificador.
  • Cíclico: contém ciclos (um caminho que começa e termina no mesmo nó).
  • Acilíclico (DAG): não contém ciclos.
  • Aresta rotulada: cada aresta tem um rótulo geralmente desenhado próximo à aresta correspondente.
  • Ponderado: as arestas têm pesos (valores) associados a elas, que podem ser usados para realizar operações aritméticas.
  • Desconectado: contém dois ou mais nós que não estão conectados por nenhuma aresta.
Grafos são usados em várias aplicações como mapas, redes, sistemas de recomendação e resolução de dependências.

Percursos em Grafos

Isso envolve visitar todos os nós em um grafo. Os dois principais algoritmos são:
  • Busca em Largura (BFS)
  • Usa uma fila.
  • Explora nível por nível.
  • Encontra o caminho mais curto em grafos não ponderados.
  • Busca em Profundidade (DFS)
  • Usa uma pilha (ou recursão).
  • Explora completamente um branch antes de retroceder.
  • Útil para detecção de ciclos e busca de caminhos.

Representações de Grafos

Grafos podem ser representados de duas maneiras principais:
  • Lista de Adjacência
  • Cada nó tem uma lista de seus vizinhos.
  • Eficiente em espaço para grafos esparsos.
  • Fácil de iterar sobre vizinhos.
  • Matriz de Adjacência
  • Um array 2D onde linhas e colunas representam nós.
  • Intensivo em espaço para grafos grandes.
  • Rápido para verificar se existe uma aresta entre dois nós.

Árvores

Uma árvore é um tipo especial de grafo que é acíclico e conectado. Propriedades principais incluem:
  • Eles não têm loops ou ciclos (caminhos onde os nós inicial e final são os mesmos).
  • Eles devem estar conectados (cada nó pode ser alcançado a partir de qualquer outro nó).

Tipos comuns de árvores

Os tipos mais comuns de árvores são:
  • Árvores Binárias
  • Cada nó tem no máximo dois filhos, um filho esquerdo e um filho direito.
  • Árvores de Busca Binária (BST)
  • Uma árvore binária na qual todo filho à esquerda é menor que seu pai e todo filho à direita é maior que seu pai.

Tentativas

Também conhecidos como árvores de prefixo, eles são usados para armazenar conjuntos de strings, onde cada nó representa um caractere. Prefixos compartilhados são armazenados apenas uma vez, tornando-os eficientes para tarefas como autocomplete e verificação ortográfica. Operações de busca e inserção têm complexidade de tempo O(L), onde L é o comprimento da string.

Filas de Prioridade

Uma fila de prioridade é um tipo abstrato de dado onde cada elemento tem uma prioridade. Filas e pilhas consideram apenas a ordem de inserção, enquanto filas de prioridade consideram a prioridade dos elementos. Filas padrão seguem FIFO (First In First Out) e pilhas seguem LIFO (Last In First Out). No entanto, em uma fila de prioridade, elementos com maior prioridade são atendidos antes daqueles com menor prioridade, independentemente da ordem de inserção.

Heaps

É uma estrutura de dados especializada baseada em árvore com uma propriedade muito específica chamada heap property. A propriedade heap determina a relação entre os nós pai e filho. Existem dois tipos de heaps:
  • Max-Heap
  • O valor de cada nó pai é maior ou igual aos valores de seus filhos.
  • O maior elemento está na raiz.
  • Min-Heap
  • O valor de cada nó pai é menor ou igual aos valores de seus filhos.
  • O menor elemento está na raiz.

Exemplo do módulo Python heapq

import heapq

# Create empty heap
my_heap = []

# Insert elements
heapq.heappush(my_heap, 9)
heapq.heappush(my_heap, 3)
heapq.heappush(my_heap, 5)
print(my_heap) # [3, 9, 5]

# Remove smallest element
print(heapq.heappop(my_heap))  # 3
print(my_heap) # [5, 9]

# Push + Pop in one step
print(heapq.heappushpop(my_heap, 7)) # 5
print(my_heap) # [7, 9]

# Transform list into heap
nums = [5, 7, 3, 1]
heapq.heapify(nums)

Usando Prioridades

my_heap = []
heapq.heappush(my_heap, (3, "A"))
heapq.heappush(my_heap, (2, "B"))
heapq.heappush(my_heap, (1, "C"))

# Removes lowest number = highest priority
print(heapq.heappop(my_heap))  # (1, "C")
# --assignment-- Revise os tópicos e conceitos de Graphs e Trees.