Estrutura de Dados
Grafos e Árvores
Prof. Pedro Luís Antonelli
Anhanguera Educacional
Conceitos Básicos
Grafo: conjunto de vértices ( nós) e arestas ( arcos).
Vértice: objeto simples que pode ter nome e outros atributos.
Aresta: conexão entre dois vértices.
Notação: G = (V,A), onde:
G: grafo
V: conjunto de vértices
A: conjunto de arestas
Um grafo é dito ponderado se possui pesos associados as suas arestas.
Grafos Direcionados ( Dígrafos )
Um grafo direcionado G é um par (V,A), onde V é um conjunto finito de vértices e A
é uma relação binária em V .
Uma aresta (u, v) sai do vértice u e entra no vértice v. O vértice v é adjacente ao
vértice u.
Podem existir arestas de um vértice para ele mesmo, chamadas de self-loops.
Grafos Não Direcionados
Um grafo não direcionado G é um par (V,A), onde o conjunto de arestas A é
constituído de pares de vértices não ordenados.
As arestas (u, v) e (v, u) são consideradas como uma única aresta. A relação de
adjacência é simétrica. Self-loops não são permitidos.
Grau de um vértice
Em grafos não direcionados o grau de um vértice é o número de arestas que
incidem nele.
Um vértice de grau zero é dito isolado ou não conectado.
Exemplo:
Os vértices 0, 1e 2 tem grau 2;
Os vértices 4 e 5 tem grau 1;
O vértice 3 é isolado.
Grau de um vértice
Em grafos direcionados o grau de um vértice é o número de arestas que saem dele
mais o número de arestas que chegam nele.
Exemplo:
Os vértices 0 e 1 tem grau 3;
Os vértice 2 e 3 tem grau 4;
Os vértices 4 e 5 tem grau 1.
Representação de um grafo: Matriz de Adjacência
A matriz de adjacência de um grafo não ponderado G = (V,A) contendo n vértices é
uma matriz n × n de bits, onde A[ i, j ] é 1 se existir um arco do vértice i para o
vértice j.
Representação de um grafo: Matriz de Adjacência
Para grafos ponderados a matriz de adjacência de um G = (V,A) contendo n vértices
é uma matriz n × n de valores, onde A[ i, j ] contém o rótulo ou peso associado com
a aresta se existir um arco do vértice i para o vértice j.
Se não existir uma aresta de i para j então é necessário utilizar um valor que não
possa ser usado como rótulo ou peso.
Representação de um grafo: Lista de Adjacência
Um grafo pode ser representado por uma lista onde cada elemento representa um
vértice e aponta para outra lista contendo os vértices adjacentes a ele.
Exemplo de grafo
Exemplo de grafo – representação em “C”
Exemplo de Lista de Adjacência
Grafos- Aplicações
Representação de sistemas de transporte e movimentação
Grafos- Aplicações
Representação de trajetos em sistemas de direcionamento
Grafos- Aplicações
Pesquisas de informações na Internet
Grafos- Aplicações
Construção de circuitos eletrônicos
Grafos- Aplicações
Representação das ligações entre átomos e moléculas
Grafos- Aplicações
Análise da compatibilidade entre impressões digitais
Grafos - Árvores
Um tipo de grafo acíclico, particularmente importante para a área de pesquisa de
dados á a Árvore.
Podemos definir um grafo do tipo Árvore, como sendo:
Conjunto de nós e conjunto de arestas ( ramos )que ligam pares de nós.
Um nó em particular é a raiz;
Com exceção da raiz, todo o nó está ligado por uma aresta a 1 e somente 1 só nó (o
pai );
Há um caminho único da raiz a cada nó;
O tamanho do caminho para um nó ( profundidade ) é o número de arestas a
percorrer.
Árvores – Representação Gráfica
RAIZ
ARESTA
NÓ
FOLHAS
Árvores - Características
Árvores Binárias
Uma árvore é dita binária quando em que cada nó tem zero, um ou dois filhos.
Quando uma árvore binária não possui filhos é dita vazia.
Uma árvore binária não vazia ou possui um nó chamado raiz e até mais duas
árvores binárias disjuntas chamadas sub-árvore esquerda e sub-árvore direita.
RAIZ
SUB-ÁRVORE
ESQUERDA
SUB-ÁRVORE
ESQUERDA
SUB-ÁRVORE
DIREITA
Árvores Binárias - Propriedades
Uma árvore binária não vazia com profundidade h tem no mínimo h+1, e no
máximo 2 (h+1 ) - 1 nós;
A profundidade de uma árvore com n elementos ( n>0 ) é no mínimo log2n, e no
máximo n-1.
Árvores Estritamente Binárias
Uma Árvore Estritamente Binária é aquela que tem nós que possuem 0 ou dois
filhos.
Nós interiores (nós que não são folhas)
possuem sempre 2 filhos.
Árvore Binária Completa
Uma Árvore Binária Completa é aquela que é estritamente binária de nível x e
com todos os nós-folhas no mesmo nível x.
Percorrer Árvores Binárias
Os elementos de uma árvore (binária) podem ser enumerados por quatro ordens
diferentes. As três primeiras definem-se recursivamente:
Pré-ordem: Primeiro a raiz, depois a sub-árvore esquerda, e finalmente a subárvore direita
Em-ordem: Primeiro a sub-árvore esquerda, depois a raiz, e finalmente a subárvore direita
Pós-ordem: Primeiro a sub-árvore esquerda, depois a sub-árvore direita, e
finalmente a raiz
Por nível: Os nós são processados por nível (profundidade) crescente, e dentro de
cada nível, da esquerda para a direita
Percorrer Árvores Binárias
Exemplos de passeios em árvores:
Árvore Binária – Representação Estática
Uma árvore binária pode ser representada por uma Lista Estática ( vetor ).
Essa representação é extremamente compacta., e permite caminhar pelos nós da
árvore facilmente.
Os filhos de um nó i estão nas posições 2i e 2i + 1 ( atenção ao primeiro emento!)
O pai de um nó i está na posição i div 2 ( divisão inteira por 2).
Árvore Binária – Representação Dinâmica
Uma árvore binária pode ser representada por uma Lista Dinâmica ( ponteiros).
Para implementar um árvore binária em “C”, devemos criar um estrutura que
contenhas as seguintes partes:
- Um ponteiro para o nó raiz, a informação propriamente dita;
- Um ponteiro para a sub-árvore à esquerda e um ponteiro para a sub-árvore à
direita.
BIBLIOGRAFIA
W. Celes, W. R. Cerqueira, J.L. Rangel. Introdução a Estruturas de Dados com técnicas de programação em C
Ed. Campus
TENENBAUM, Aaron M. Estrutura de Dados Usando C. 1ª ed. São Paulo:
PEARSON EDUCATION, 2005.
VELOSO, Paulo A. S.. Estrutura de Dados. 1ª ed. Rio de Janeiro: Campus,
1996.
PEREIRA, Silvio do Lago. Estrutura De Dados Fundamentais : Conceitos
E Aplicações. 12ª ed. São
Paulo: Érica, 2008
MANZANO, José Augusto N. Garcia. Algoritmos : Lógica para
desenvolvimento de programação de computadores. 21ª ed.São Paulo:
Érica, 2008.
FORBELLONE, A. L.. Lógica De Programação. 1ª ed. São Paulo: Pearson,
2008.
CORMEN, Thomas H.. Algoritmos : Teoria e Prática. 2ª ed. Rio de Janeiro:
Campus, 2002.
https://programacaodescomplicada.wordpress.com/
http://www.jacintomendes.eti.br/mackenzie/peii/aulas/
sandra/PEII_Aula12.pdf. Acesso em 02/02/2012
http://www.dainf.ct.utfpr.edu.br/~karla/ Acesso em 02/02/2012
http://www.rcosta62br.unifei.edu.br Acesso em 03/02/2012
http://gaveta-virtual.blogspot.com.br/2011/06/filas.html Acesso em 10/04/2012
http://www.cin.ufpe.br/~rv2/mprof/seminario-mprof-20150303.html#7
https://sites.google.com/site/andrenunosouto/coisas-de-matematica/teoria-de
http://www.scielo.br/scielo.php?script=sci_arttext&pid=S010174382002000100002#fig06
http://www.ebah.com.br/content/ABAAAe8rYAE/aula-grafos1
https://valdecircosta.wordpress.com/grafos/
Gulilherme, Ivan. R - Notas de aula do curso de IA – Unesp – RC