Árvores e grafos

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Árvores - definição

Imagem de uma árvore com nós.

  • Estruturas de dados baseadas em nós
  • Cada nó pode ter links para mais de um nó.
Estruturas de Dados e Algoritmos em Python

Árvores - terminologia

Imagem de uma árvore com nós. O nó raiz está em amarelo.

Estruturas de Dados e Algoritmos em Python

Árvores - terminologia

Imagem de uma árvore com nós. O nó raiz está em amarelo. Um nó pai está em laranja.

Estruturas de Dados e Algoritmos em Python

Árvores - terminologia

Imagem de uma árvore com nós. O nó raiz está em amarelo. Um nó pai está em laranja e seus filhos em verde.

Estruturas de Dados e Algoritmos em Python

Árvores - terminologia

Imagem de uma árvore com nós.

Estruturas de Dados e Algoritmos em Python

Árvores - terminologia

Imagem de uma árvore com nós e seus níveis.

Estruturas de Dados e Algoritmos em Python

Árvores - árvore binária

Representação gráfica de uma árvore binária.

  • Cada nó tem:
    • zero filhos
    • um filho
    • dois filhos
Estruturas de Dados e Algoritmos em Python

Árvores - implementação de árvore binária

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

Imagem de uma árvore com nós.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Estruturas de Dados e Algoritmos em Python

Árvores - usos reais

  • Armazenar relações hierárquicas
    • Sistema de arquivos do computador
    • Estrutura de um documento HTML

  • Xadrez: jogadas possíveis do oponente

  • Algoritmos de busca e ordenação

Estruturas de Dados e Algoritmos em Python

Grafos

Imagem de um grafo com nós.

  • Conjunto de:
    • nós/vértices
    • links/arestas
  • Árvores são um tipo de grafo
Estruturas de Dados e Algoritmos em Python

Grafos - tipos

  • Grafos direcionados:
    • direção específica

Imagem de um grafo direcionado.

Estruturas de Dados e Algoritmos em Python

Grafos - tipos

  • Grafos não direcionados:
    • Arestas sem direção
    • Relação é mútua

Imagem de um grafo não direcionado.

Estruturas de Dados e Algoritmos em Python

Grafos - tipos

  • Grafos ponderados:
    • valores numéricos nas arestas
    • podem ser direcionados ou não

Imagem de um grafo não direcionado com nomes de cidades e distâncias.

Estruturas de Dados e Algoritmos em Python

Grafos vs. árvores

Árvores

  • Não podem ter ciclos
  • Todos os nós devem estar conectados

Imagem de uma árvore com nós.

Grafos

  • Podem ter ciclos
  • Pode haver nós desconectados

Imagem de um grafo com nós.

Estruturas de Dados e Algoritmos em Python

Grafos vs. árvores

Árvores

  • Não podem ter ciclos
  • Todos os nós devem estar conectados

Imagem de uma árvore com nós.

Grafos

  • Podem ter ciclos
  • Pode haver nós desconectados

Imagem de um grafo com nós. Há um nó desconectado do resto.

Estruturas de Dados e Algoritmos em Python

Grafos - casos de uso reais

  • Relações de usuários em redes sociais
    • amizade
    • segue
    • curte
    • etc.
  • Localizações e distâncias
    • otimizar rotas
  • Bancos de dados de grafos
  • Algoritmos de busca e ordenação
Estruturas de Dados e Algoritmos em Python

Grafos - implementação

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

Imagem de um grafo direcionado.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}
Estruturas de Dados e Algoritmos em Python

Vamos praticar!

Estruturas de Dados e Algoritmos em Python

Preparing Video For Download...