Trie e Grafos em Python: Estruturas de Dados Avançadas

Modelagem orientada a objetos, invariantes, integração e análise de complexidade com método

Por Fábio Linhares • Instituto Infnet

Como usar esta página

Este material foca em raciocínio operacional: modelar corretamente, implementar de forma determinística e validar a resposta por comportamento observável. O objetivo é sair do código que apenas roda para um código que você consegue explicar com clareza técnica.

No bloco de Trie, a chave é separar conceitos que iniciantes costumam misturar: caminho de prefixo e palavra completa. Ao longo dos exercícios, isso aparece em insert, search, starts_with, collect_words, autocomplete e autocorrect.

No bloco de Grafos, o foco é comparar duas representações clássicas sem perder critério de engenharia: lista de adjacência e matriz de adjacência. Você implementa operações equivalentes, mede impacto estrutural e justifica escolha com base em |V| e |E|.

Fechando o ciclo, a integração Trie + Grafo mostra como índice textual e fonte de verdade convivem no mesmo fluxo. Esse é o passo que aproxima o conteúdo de um cenário real de produto.

Defina invariantes e use-os para validar corretude.
Priorize APIs pequenas, previsíveis e reprodutíveis.
Explique custo com variáveis relevantes, não com rótulos genéricos.
Mantenha linguagem técnica objetiva: condição, comportamento e justificativa.

▼

EXERCÍCIO 01

TrieNode, Trie e inserção com prefixos compartilhados

Objetivo: estruturar nó raiz, filhos e marcação de fim de palavra sem quebrar prefixos.

A estrutura base da Trie precisa separar estado de nó e operações de árvore. A marca is_end é o contrato que diferencia caminho existente de palavra concluída.

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

Validação rápida

1. Insira car, cart e carro.

2. Confirme que o nó de car continua com is_end=True.

▼

EXERCÍCIO 02

Busca exata com search(word)

Objetivo: retornar verdadeiro apenas quando o nó final representa palavra completa.

Aqui a regra de ouro é: caminho em children não basta. A resposta depende do estado do nó final.

class Trie(Trie):
    def search(self, word: str) -> bool:
        if word == "":
            return False
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end

Use os pares ("car", True), ("ca", False) e ("cars", False) para validar sem ambiguidade.

▼

EXERCÍCIO 03

Busca por prefixo com starts_with(prefix)

Objetivo: detectar existência de caminho de prefixo com custo linear no tamanho do prefixo.

class Trie(Trie):
    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

exemplos = ["c", "ca", "car", "carr", "x"]
resultados = [(p, trie.starts_with(p)) for p in exemplos]

Checklist técnico

1. Prefixo existente e prefixo inexistente devem aparecer no mesmo conjunto de exemplos.

2. Inclua um caso em que o prefixo também é palavra completa.

▼

EXERCÍCIO 04

Traversal com collect_words(node, prefix)

Objetivo: enumerar palavras sem perdas nem duplicações a partir de qualquer nó.

class Trie(Trie):
    def _collect_words(self, node: TrieNode, prefix: str, out: list) -> None:
        if node.is_end:
            out.append(prefix)
        for ch in sorted(node.children.keys()):
            self._collect_words(node.children[ch], prefix + ch, out)

    def collect_words_from_prefix(self, prefix: str) -> list[str]:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        out = []
        self._collect_words(node, prefix, out)
        return out

Valide com set(colecao) == set(origem) e len(colecao) == len(set(colecao)).

▼

EXERCÍCIO 05

autocomplete(prefix, k) com ordenação e limite

Objetivo: produzir sugestões ordenadas, com no máximo k itens e custo justificável.

class Trie(Trie):
    def autocomplete(self, prefix: str, k: int) -> list[str]:
        if k <= 0:
            return []
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        out = []
        def dfs(n: TrieNode, pref: str):
            if len(out) >= k:
                return
            if n.is_end:
                out.append(pref)
            for ch2 in sorted(n.children.keys()):
                if len(out) >= k:
                    break
                dfs(n.children[ch2], pref + ch2)
        dfs(node, prefix)
        return out

Complexidade de referência: O(P + Np) no pior caso, com parada antecipada quando k é atingido.

▼

EXERCÍCIO 06

autocorrect(word) por maior prefixo compartilhado

Objetivo: manter comportamento determinístico com critério explícito de desempate.

class Trie(Trie):
    def autocorrect(self, word: str) -> str | None:
        if self.search(word):
            return word
        node = self.root
        prefix = ""
        for ch in word:
            if ch not in node.children:
                break
            node = node.children[ch]
            prefix += ch
        if not self.root.children:
            return None
        sug = self.autocomplete(prefix, 1)
        return sug[0] if sug else None

Sem regra de desempate, o resultado fica instável entre execuções e dificulta depuração.

▼

EXERCÍCIO 07

Grafo por lista de adjacência

Objetivo: modelar vértices e arestas com estado compacto e sem duplicatas.

class GraphAdjList:
    def __init__(self):
        self.adj = {}

    def add_vertex(self, v: str) -> None:
        if v not in self.adj:
            self.adj[v] = set()

    def add_edge(self, u: str, v: str, directed: bool = False) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj[u].add(v)
        if not directed:
            self.adj[v].add(u)

    def has_edge(self, u: str, v: str) -> bool:
        return u in self.adj and v in self.adj[u]

Use set em adjacência para evitar aresta duplicada e manter consulta eficiente.

▼

EXERCÍCIO 08

Grafo por matriz de adjacência

Objetivo: implementar índice de vértice e tabela NxN com consulta direta.

class GraphAdjMatrix:
    def __init__(self):
        self.index = {}
        self.mat = []

    def add_vertex(self, v: str) -> None:
        if v in self.index:
            return
        n = len(self.mat)
        self.index[v] = n
        for row in self.mat:
            row.append(0)
        self.mat.append([0] * (n + 1))

    def add_edge(self, u: str, v: str, directed: bool = False) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        i, j = self.index[u], self.index[v]
        self.mat[i][j] = 1
        if not directed:
            self.mat[j][i] = 1

Matriz privilegia has_edge em O(1), mas cresce em memória como O(|V|²).

▼

EXERCÍCIO 09

Definições operacionais e consistência entre representações

Objetivo: ancorar conceito em implementação e validar em ambas as estruturas.

Vértice é chave no estado interno do grafo; aresta é relação entre duas chaves. Na lista, essa relação fica em adj[u]. Na matriz, fica em mat[index[u]][index[v]].

print("AdjList:", g.has_edge("alpha", "amazon"))
print("AdjMatrix:", gm.has_edge("alpha", "amazon"))

assert g.has_edge("alpha", "amazon") is True
assert gm.has_edge("alpha", "amazon") is True

Interpretação técnica

1. Mesma pergunta, duas implementações.

2. A resposta deve ser igual para preservar consistência de domínio.

▼

EXERCÍCIO 10

Exportação Mermaid sem duplicar arestas

Objetivo: gerar visualização reprodutível e manter regra canônica no modo não direcionado.

class GraphAdjList(GraphAdjList):
    def to_mermaid(self, directed: bool = False) -> str:
        arrow = "-->" if directed else "---"
        lines = ["graph LR"]
        emitted = set()
        for u in self.adj:
            for v in self.adj[u]:
                key = (u, v) if directed else tuple(sorted([u, v]))
                if key in emitted:
                    continue
                emitted.add(key)
                lines.append(f"  {key[0]} {arrow} {key[1]}")
        return "\n".join(lines)

No modo não direcionado, use par ordenado para eliminar duplicação sem perder arestas válidas.

▼

EXERCÍCIO 11

Integração Trie + Grafo por prefixo

Objetivo: usar Trie como índice textual sem perder a fonte de verdade do grafo.

def find_vertices_by_prefix(trie: Trie, graph: GraphAdjList, prefix: str, k: int) -> list[str]:
    candidates = trie.autocomplete(prefix, k)
    return [c for c in candidates if c in graph.adj]

r1 = find_vertices_by_prefix(tr, g, "al", 10)
r2 = find_vertices_by_prefix(tr, g, "a", 3)
r3 = find_vertices_by_prefix(tr, g, "do", 10)

Índice sem filtro de domínio vira fonte de falso positivo quando há termo na Trie fora do conjunto de vértices.

▼

EXERCÍCIO 12

Decisões de projeto e complexidade

Objetivo: justificar estrutura escolhida em função de custo e previsibilidade.

Tabela base de referência

Trie: insert/search/starts_with lineares em |word| ou |prefix|.

Autocomplete: O(P + Np) no pior caso, com parada por k.

Lista de adjacência: memória O(|V| + |E|).

Matriz de adjacência: memória O(|V|²), consulta direta em O(1).

Cenário esparso grande: lista de adjacência. Cenário denso pequeno: matriz. A decisão é estrutural, não estética.