Estruturas de Dados: Tabelas Hash e Teoria dos Grafos

Exploração (Probing)

Exploração Linear: O intervalo i entre amostras é uniforme (em geral 1): H(x, i) = (H(x) + i) (mod n), onde n é o tamanho da tabela.

Exploração Quadrática: O intervalo i entre amostras cresce uniformemente: H(x, i) = (H(x) + c1i + c2i²) (mod n), com c1 e c2 ≠ 0.

Hashing Duplo: O intervalo j entre amostras é uniforme e calculado através de uma função de Hash: H(k, j) = (Hj(k) + jH2(k)) (mod n).

Endereçamento Aberto em Tabelas Hash

• Caso mais favorável: Não existem colisões, O(1).
• Caso pior: Todas as chaves colidem no mesmo lugar na tabela de Hash. Ficamos com uma pesquisa sequencial, O(N).
• Em média: Depende do número de colisões (e da técnica usada para as ultrapassar), O(1) + k.

Conceitos de Grafos

Um grafo é uma coleção de vértices ou nós, que são elementos que contêm informação que se pretende armazenar, e de arestas ou arcos, que são os elementos que ligam os vértices. Cada aresta está associada a um par de vértices, designando-se estes vértices por vértices adjacentes.

• Um grafo diz-se conexo se existir um caminho de qualquer vértice para qualquer outro vértice do grafo.
• Um grafo diz-se completo quando entre cada par de vértices existe uma ligação/aresta. Um grafo com V vértices tem no máximo V(V-1)/2 arestas/ligações, quando o grafo é completo.
• Um caminho diz-se simples se não tiver arestas repetidas, e elementar se os seus vértices forem distintos.
• Chama-se grafo orientado (Directed Graph) a um grafo em que as arestas são orientadas, ou seja, as arestas especificam o sentido da ligação entre os dois vértices adjacentes.
• Um ciclo é um caminho em que o primeiro e o último vértice são os mesmos.
• Em algumas aplicações, existe a necessidade de associar custos, ou pesos, às arestas de um grafo orientado ou de um grafo; designa-se por grafo ponderado.
• Um grafo conexo sem ciclos (acyclic connected graph) é uma árvore. Um conjunto de árvores chama-se floresta.
• Uma árvore abrangente (spanning tree) de um grafo conexo é um subgrafo que contém todos os vértices do grafo e é uma árvore.

Implementação de um Grafo

• Matriz de Adjacência: Permite fácil acesso (e atualização — inserção e/ou eliminação) às ligações. Utiliza memória em excesso em grafos com muitos vértices e poucas ligações (Grafos densos).
• Lista de Adjacência: ....