2019730_154632_Apostila+de+Algoritmos+3

Prévia do material em texto

Universidade Regional Integrada do
Alto Uruguai e das Missões
URI – Campus de Erechim
Curso de Graduação em
Ciência da Computação
Algoritmos e Estrutura de Dados III
Utilizando o Portal
URI Online Judge
www.urionlinejudge.edu.br
Neilor Tonin
Algoritmos e Estrutura de Dados III
Árvores
Além das filas e pilhas vistas no semestre anterior, que eram estruturas lineares, existem outras formas
usadas para representar os dados, que são chamadas genericamente de “não-lineares”. Essa
representação permite que sejam feitos outros tipos de relações entre os dados, como por exemplo,
relação de hierarquia.
Um dos exemplos mais significativos de estruturas não lineares que representam as relações de
hierarquia é a Árvore.
 Uma árvore pode ser definida como um conjunto de nós (ou nodos), tais que:
 existe um nó denominado raíz da árvore
 os demais nós formam subconjuntos distintos S1,S2,...Sm, onde cada subconjunto desses é uma
árvore. Esses subconjuntos recebem a denominação de subárvores.
Um exemplo bem conhecido de relação de estruturação em árvore é a estruturação de um livro, que é
subdividido em capítulos, onde cada capítulo é subdividido em seções, que por sua vez, possuem
tópicos.
Considere agora o seguinte exemplo de árvore genealógica
Analisando essa árvore, podemos concluir:
 Essa árvore possui 10 nós distribuídos aleatoriamente. O nodo Pedro é a raiz da árvore, que tem 3
subárvores com Maria, André e Marcelo como raízes.
 O número de subárvores de um nó determina o grau desse nó. Dessa forma, Pedro e Maria têm
grau 3, enquanto André tem grau 2 e Marcelo tem grau zero. Nodos que tem grau zero são
denomidados terminais ou folhas.
 prof. Neilor Tonin 2
Árvores
Introdução Árvores
Binárias
Árvores
PercursoConceito Balanceamento
Pedro
Maria André Marcelo
VivianeMárciaRodrigo Cézar Aide
Cláudio
Algoritmos e Estrutura de Dados III
Pergunta: Qual é o grau do nodo Viviane?
 Considerando que cada nó tem um grau máximo (número de subárvores das quais esse nó é raiz) e
que todos os nós possuem o mesmo grau máximo, definimos esse grau como o grau da árvore.
 Uma árvore é homogênea quando todos os seus nodos possuem as mesmas características de
conteúdo, ou seja, o mesmo tipo de informação; caso contrário ela é então chamada de árvore
heterogênea. 
 Para identificar os nós da estrutura, usamos as denominações da relação de hierarquia existente em
uma árvore genealógica. Dessa forma, Pedro é pai de Maria, André e Marcelo que são irmãos entre
si. No sentido inverso, Rodrigo, Márcia e Viviane são filhos de Maria e netos de Pedro. Para
conhecermos os antepassados de um nodo, basta identificarmos todos os nodos ao longo do
caminho entre a raíz e este nodo. Ex: os antepassados de Cláudio são, na ordem: Pedro, Maria e
Viviane. 
 Um conceito importante no estudo de árvores é o conceito de nível, que representa a distância do
nodo até a raiz. Por definição, a raiz da árvore tem nível 0. Na figura anterior, os nodos Maria,
André e Marcelo têm nível 1, os nodos Rodrigo, Márcia, Viviane, Cézar e Aide tem nível 2, assim
por diante. O nodo de maior nível nos fornece a altura (ou profundidade) da árvore.
Pergunta: No exemplo que estamos usando, a árvore tem altura (???)?
 
Exercício 1: Construa uma árvore com base nas informações abaixo:
- O nodo C tem grau 3.
- O nodo X é neto de C e filho de B.
- O avô de B é A.
- O nodo A tem altura 0 e T tem altura 1.
- Os antepassados de P são A,T e K, que são também antepassados de H.
- T tem grau 2, e um dos seus filhos é o nodo S.
- O nodo G tem 2 subárvores que são netos de C.
- D é irmão de G, e é uma folha.
- E e F tem graus 0 e 1, respectivamente, e são também netos do nodo C.
- O nodo N está no nível 4.
Exercício 2: Construa uma árvore com base nas informações abaixo:
- O nodo B tem grau 3.
- O nodo K é neto de B e o nodo F é um de seus 2 filhos.
- O avô de S é A.
- O nodo K tem um irmão.
- O nodo Pai de T é o nodo U.
- O filho de A, que é nodo irmão de B, tem dois filhos, sendo que um deles é o nodo P.
- O nodo T tem altura 3, mas não é neto de B, tampouco filho de P.
- Os nodos T e C estão no mesmo nível.
- O nodo A tem altura 0, e o nodo D tem altura 1.
- A árvore tem altura 4,
- Os nodos X e Y tem grau 0.
- O nodo E está no nível 4
 prof. Neilor Tonin 3
Algoritmos e Estrutura de Dados III
Árvores Binárias e variantes
Definição: uma árvore binária se caracteriza pelo fato de todos os seus nodos terem no máximo duas
subárvores, ou seja, é uma árvore de grau 2. As duas subárvores de cada nó são denominadas subárvore
esquerda e subárvore direita.
 
Na figura abaixo, temos duas árvores binárias, sendo a da esquerda, incompleta e a da direita completa:
No segundo caso, cada nodo possui dois descendentes, exceto as folhas, que por definição não tem
filhos. Geralmente nos referimos aos filhos de um nodo numa árvore binária como sendo da esquerda
ou da direita, de acordo com o posicionamento dele.
Representações das árvores (no computador):
Existem duas maneiras alternativas de representarmos árvores binárias no computador:
- em listas lineares e
- em listas encadeadas.
a) Árvores binárias em listas lineares:
Uma maneira de representar uma árvore binária numa lista linear consiste em declarar um vetor com
tamanho máximo igual ao número máximo de nós da árvore binária.
A representação de árvores binárias na forma de listas lineares é especialmente indicada quando as
árvores são completas, pois resulta na utilização máxima do espaço alocado. 
A representação na forma de uma lista linear não é indicada em duas situações:
- quando for necessário efetuar operações de inserção e retirada de nodos, pois potencialmente
exigirá uma grande movimentação dos dados para conseguir o efeito desejado; e 
- quando a árvore afasta-se mais e mais da condição de completa, ou seja, não é indicada em
situações onde a estrutura de dados é frequentemente alterada. 
Árvore binária com raiz na posição zero. Árvore binária incompleta alocada sequencialmente
Nesse tipo de representação, fica difícil saber qual é o ascendente de um átomo e embora é geralmente
adequada para algumas aplicações, sempre poderá haver desperdício de espaço. 
Na alocação encadeada subdividimos o espaço de um nó em três campos, como mostrado abaixo:
nodo Pos subárvore esquerda Pos subárvore direita
 prof. Neilor Tonin 4
A A
CB CB
D F D E F G
Algoritmos e Estrutura de Dados III
Outra forma de representar a árvores seria no seguinte formato
Link esquerdo Nodo Link direito
A árvore então, seria apresentada da seguinte forma:
Operadores para árvores binárias:
Donald E. Knuth popularizou três ordens de percurso em árvores binárias: Pré-ordem ou prefixa,
simétrica ou infixa e Pós-ordem ou pós-fixa.
Prefixa: 
- visita a raiz
- visita a subárvore à esquerda
- visita a subárvore à direita
Infixa: 
- visita a subárvore à esquerda
- visita a raiz
- visita a subárvore à direita
Posfixa: 
- visita a subárvore à esquerda
- visita a subárvore à direita
- visita a raiz
Considerando a árvore apresentada ao lado, veja a seqüência de nodos visitados de acordo com cada
ordem de visitação:
Visitação prefixa: A,B,D,E,C,F,G 
Visitação infixa: D,B,E,A,F,C,G
Visitação posfixa: D,E,B,F,G,C,A
Exercícios:
1) Dada as seguintes árvores, faça para cada uma delas a visitação dos nodos utilizando a ordem prefixa, infixa e pósfixa
 prof. Neilor Tonin 5
A
CB
E F GD
A
BC
E F G
IH
D
a)
J
A
BC
E F
GIH
D
c)
K
ML
b) A
BC
E G
IH
D F
K LJ
M
Algoritmos e Estrutura de Dados III
URI Online Judge | 1191 
Recuperação da Árvore
Por Sebastião Alves Brasil
Timelimit: 1 
A pequena Valentina gostava muito de brincar com árvores binárias. Seu jogo favorito era contruir árvores binárias 
aleatóriascom letras em maiúsculo nos nodos. Este é um exemplo de uma de suas criações:
Para salvar suas árvores para uso futuro, ela escreveu duas strings para cada árvore: o percurso prefixo (raíz, subárvore
esquerda, subárvore direita) e o percurso infixo (subárvore esquerda, raíz, subárvore direita).
Para o desenho acima o percurso prefixo é DBACEGF e o infixo é ABCDEFG.
Agora, anos depois, olhando para as strings, ela notou que reconstruir as árvores era realmente possível, mas só porque ela
não havia usado a mesma letra duas vezes na mesma árvore. Recontruir a árvore a mão tornou-se chato.
Então agora ela pede que você escreva um programa que faça o trabalho por ela!
Entrada
A entrada irá conter um ou mais casos de teste. Cada caso de teste consiste em uma linha contendo duas strings 
representando o percurso prefixo e infixo de uma árvore binária. Ambas as strings consistem de letras maiúsculas, sem 
repetir. (Então elas não são maiores de 26 caracteres.) A entrada termina com EOF (fim de arquivo).
Saída
Para cada caso de teste, imprima uma linha com o percurso posfixo (subárvore esquerda, subárvore direita, raíz).
Exemplo de Entrada Exemplo de Saída
DBACEGF ABCDEFG
BCAD CBAD
ACBFGED
CDAB
 prof. Neilor Tonin 6
A C
D
B
G
E
F
PRE IN POS
Algoritmos e Estrutura de Dados III
Árvores de Expressões
Uma expressão aritmética pode ser armazenada sob a forma de uma árvore binária, onde as raízes armazenariam as
operações a serem efetuadas, e as subárvores à esquerda e direita armazenariam os operandos a serem usados.
Por exemplo, a expressão a+b deveria então ser apresentada com a seguinte forma:
Já no caso da expressão a + b * c, a prioridade dos operadores e a ordem de ocorrência, ambos, devem ser
respeitados
ou seja, ao se percorrer as árvores na forma infixa e posfixa respectivamente teremos: a,+,b,*,c e a,b,c,*,+,
que é diferente da expressão b * c + a, que seria representada assim:
Após estas análises, a expressão ((A+B)/C)*(D-E), então, seria representada assim:
Como dica para resolver uma árvore completa, procure sempre resolver as expressões do centro para fora. No
caso anterior, por exemplo, represente:
 A + B
 / C 
 D - E
 *
Exercícios:
Transforme as seguintes expressões para posfixa utilizando árvores binárias para fazer a transformação:
a) (a+b) * (c-d)
b) (a+b*c)*a + (c-d)*3
c) (a+b*c)*a – 4*(5-6+1) + (c-d)*3
d) (a+b-c) – (3-4)*(5-6+1) + (c-d*3)
e) a + b * c – d + e * f – d * h / i - j
 prof. Neilor Tonin 7
BA
+
B C
A
+
*
B C
A
+
*
*
-/
C+ D E
BA
Algoritmos e Estrutura de Dados III
Árvore binária de pesquisa
Uma árvore binária, cuja raiz armazena o elemento R, é denominada árvore binária de pesquisa se:
 todo elemento armazenado na subárvore à esquerda é menor do que R,
 todo elemento armazenado na subárvore à direita é maior do que R.
Uma árvore binária de pesquisa, visitada em ordem simétrica/infixa (E,R,D), resulta em uma lista de dados em ordem
crescente. Veja os casos abaixo: na árvore Y, todos os elementos da subárvore esquerda (a,b,c) são menores que a raiz, e
nenhum elemento da subárvore direita (e,f,g) é menor que a raiz. Entretanto, ela não é uma árvore binária de pesquisa, pois
na subárvore da direita, cuja raiz é G, tem uma subárvore direita que armazena uma informação menor que a raiz.
X) Ordenada (binária de pesquisa) Y) Não ordenada
 
A árvore abaixo, é binária de pesquisa?
a) Inserção em uma A. B. P.:
Inserir um elemento X em uma Árvore Binária de Pesquisa vazia é trivial. Se a árvore não se encontra vazia deve-se fazer o
seguinte: Compara-se o elemento a inserir com o elemento raiz da árvore. Se o elemento for menor, o inserimos na
subárvore esquerda, senão, o inserimos na subárvore direita.
Insere (nodo *T , char inform) 
início
 se T = NULO então
 novo(T)
 T->esq = NULO
 T->info = inform
 T->dir = NULO
 senão
 se inform < T->info então
 Insere(T->esq,inform)
 senão
 Insere(T->dir,inform)
 fim_se 
 fim_se
fim
Para entendermos o funcionamento do algoritmo de inserção, veja o exemplo de construção de uma árvore binária de
pesquisa com o conjunto de números
{17,99,13,1,3,100,400}
raiz nulo
raiz 17
 prof. Neilor Tonin 8
D
EB
C D FA
D
GB
C E FA
D
E
C
A
G
FB
Representação interna de uma árvore binária
?
17
9913
17
99
17
Algoritmos e Estrutura de Dados III
Análise DETALHADA do procedimento de inserção:
Considere como exemplo a árvore B abaixo, que foi inserida através das linhas de programa
apresentadas ao lado dela. Note que para criar a árvore, os nodos devem ser inseridos sempre por nível,
do nível 0 ao nível n ou na ordem prefixa, pois para inserir o “C”, por exemplo, já deve ter sido
inserido anteriormente o nodo “E”. Para inserir o “F”, já deve ter sido inserido anteriormente o nodo
“H”, e assim por diante
 
Só para recordar, consideramos um programa que cria e atribui um ponteiro, por exemplo:
char *x;
*x='a';
FFF0 “X”
FFF4
FFF4
a
Neste caso: x = FFF4 &x=FFF0 e *x = 'a' 
Com a análise da estrutura da árvore na memória do computador, após a inserção de todos os
nodos, obtém-se uma tabela que é apresentada abaixo. 
Para gerar tal tabela, basta incluir a seguinte linha na rotina infixa():
cout << (*T) << " " << (*T)->esq << " " << (*T)->info << " " << (*T)->dir << endl; 
T 
(& de quem aponta para
o nodo)
*T (*T)->esq
que informação tenho
no cpo “esq”
(*T)->dir
que informação
tenho no cpo “dir”
(*T)->info
que informação tenho
no cpo “info”
FFF4 09FE 0A08 0A12 E
09FE 0A08 0A1C ----- (NULL) C
0A08 0A1C ----- ----- A
0A01 0A12 0A26 0A30 H
0A12 0A26 ----- 0A3A F
0A29 0A3A ----- ----- G
0A15 0A30 ----- ----- I
 prof. Neilor Tonin 9
nodo *T; 
T = NULL;
 
 T->ins (&T, 'e');
 T->ins (&T, 'c');
 T->ins (&T, 'a');
 T->ins (&T, 'h');
 T->ins (&T, 'f');
 T->ins (&T, 'i');
 T->ins (&T, 'g');
09FE
0A08
09FF 0A00
E 
0A01
0A12
FFF4 &(*T)
09FE *T
0A08
0A1C0A1C
0A09 0A0A
C 
0A0B
-
0A12
0A26
0A13 0A14
H 
0A15
0A30
0A1C0A1C 0A1D 0A1E
A 
0A1F
-
0A26
-
0A27 0A28
F 
0A29
0A3A
0A30
-
0A31 0A32
I 
0A33
-
0A3A
-
0A3B 0A3C
G 
0A3D
-
E
H13C
A IF
G
(*T)->esq (*T)->info (*T)->dir
Estrutura do Nodo:
1 byte 2 bytes 1 byte
? T
FFF4
09FE
0A08
09FF 0A00
E 
0A01
0A12
FFF4 &(*T)
09FE *T
0A08
0A1C0A1C
0A09 0A0A
C 
0A0B
-
0A12
0A26
0A13 0A14
H 
0A15
0A30
0A1C0A1C 0A1D 0A1E
A 
0A1F
-
0A26
-
0A27 0A28
F 
0A29
0A3A
0A30
-
0A31 0A32
I 
0A33
-
0A3A
-
0A3B 0A3C
G 
0A3D
-
E
H13C
A IF
G
(*T)->esq (*T)->info (*T)->dir
Estrutura do Nodo:
1 byte 2 bytes 1 byte
? T
FFF4
Algoritmos e Estrutura de Dados III
b) Pesquisa em uma árvore binária
Se a árvore for nula, nada a fazer, caso contrário, o processo de busca é o mesmo utilizado para inserção.
Void procura (...){
 if (*T ==NULL)
 cout << “Nodo não existe!”
 else {
 if( informacao < (*T)->info)
 procura ( usando subárvore esquerda) // procura para a esquerda
 else {
 if (informacao > (*T)->info) 
 procura ( usando subárvore direita) // procura para a direita 
 else
 // encontrou
 }
 }
}
c) Retirada em uma A. B. P.:
Se o nodo a ser retirado de uma árvore for uma folha, basta atualizar o link do seu pai para que não aponte mais para o nó a
ser retirado.
No caso de retirada de um nodo que é raiz, deve-se adotar o seguinte procedimento:
- se a raiz não tem filho esquerdo, o filho direito passa a ser a raiz, e vice-versa
-se a raiz tem ambos os filhos, pode-se optar por buscar a > chave esquerda ou a < chave
direita para ser a nova raiz:
Exercício: Remover o D:
Análise do procedimento de retirada
Considere como exemplo a árvore Babaixo (a mesma que foi
utilizada para explicar o procedimento de inserção)
São quatro as possibilidades existentes para retirada. Considere que o nodo a ser retirado pode ser:
a) Um nodo sem descendentes
b) Um nodo sem descendentes na direita mas com descendentes na esquerda.
c) Um nodo sem descendentes na esquerda mas com descendentes na direita. 
d) Um nodo com 2 filhos.
No programa, isso pode ser representado por 4 testes de seleção (if)
if ((*T)-> esq != NULL) && ((*T)-> dir ==NULL){ //somente descendentes na esq.
 ... (1 linha)
}
if ((*T)-> esq == NULL) && ((*T)-> dir !=NULL){ //somente descendentes na dir.
 ... (1 linha)
}
if ((*T)-> esq == NULL) && ((*T)-> dir ==NULL){ //nodo sem descendentes.
 ... (1 linha)
}
if ((*T)-> esq != NULL) && ((*T)-> dir != NULL){ //nodo com 2 filhos
 ... (algumas linhas)
}
 prof. Neilor Tonin 10
D
FB
C E GA
E
H13C
A IF
G
Algoritmos e Estrutura de Dados III
No caso da retirada de uma folha (A, G ou I), (item a) o procedimento a ser realizado é muito simples:
Simplesmente atribui nulo (NULL) para o ponteiro que está apontando para o nodo a ser retirado e
libera-se a memória ocupada anteriormente pelo nodo.
No caso da retirada de um nodo com um filho (item b ou c), simplesmente o nodo pai passa a apontar 
para o neto. Exemplos:
No caso da retirada de um nodo com um ambos os filhos (item d), deve-se criar uma rotina aqui 
chamada de pega_maior ou Get_max, que deverá pegar o maior elemento da subárvore que está sendo 
excluída:
 prof. Neilor Tonin 11
E
H13C
A IF
G
E
H13C
IF
G
E
H13C
A IF
G
E
H13A
IF
G
E
H13C
A IF
G
E
H13C
A IG
E
H13C
A IF
G
E
13C
A IF
G
G
E
H13C
A IF
G
Neste caso, como o Get_max deve ser aplicado sobre a sub-árvore 
esquerda do H, o valor a retornar pela função será o G E
13C G
A IF
Algoritmos e Estrutura de Dados III
Se, por exemplo, tivesse um F2 “pendurado” na esquerda do “G”, após a retirada do G ele deveria 
aparecer “pendurado” na direita do “F”
Abaixo é apresentado o algoritmo para exclusão:
Procedure exclusao(...)
início
 se (*T ==NULL)
 exit; // elemento não foi encontrado
 se (informacao == T->info) // elemento encontrado na raiz
 P=t;
 se (T->esq == NULL) 
 T=T->dir // A raiz não tem filho esquerdo
senão
 se (T->dir=NULL) 
 T=T->esq 
 senão
 P = PegaMaior(T->esq); 
 T->info = P->info;
 fim_se
 libera(P);
 fim_se
 senão
 se (informacao < T->info) então // elemento encontrado numa das subárvores
 exclusao(T->esq,informacao)
 senão
 exclusao(T->dir,informacao)
 fim_se
 fim_se
fim
d) Listagem em uma Árvore Binária
Conforme visto anteriormente, podemos percorrer uma árvore passando por todos os nodos dela. Existem 4 formas de
atravessamento (listagem) de uma árvore:
- Prefixa (?) - Posfixa (?)
Infixa(...);
início
 se (T != nil) 
 infixa(t->esq);
 escreve(T->.info,','); 
 infixa(t->.dir);
 fim_se
fim
Rotina para pegar o maior elemento de uma árvore ( Pega_maior):
O maior elemento de uma árvore binária ordenada encontra-se sempre no nodo que estiver mais à direita possível na árvore.
 prof. Neilor Tonin 12
E
E
13C H 13C G
A IF A IF
G F2
F2
Algoritmos e Estrutura de Dados III
#include <iostream> #include <cstdlib> #define TIPO int
 
using namespace std;
struct nodo {
 nodo *esquerda;
 TIPO informacao;
 nodo *direita;
 nodo ( TIPO info ) : 
 informacao (info),
 esquerda (0),
 direita (0) {}
};
 
nodo *P;
struct nodo *insere ( nodo *tree, TIPO informacao ) {
 if ( tree == NULL )
 tree = new nodo (informacao);
 else if ( informacao < tree->informacao )
 tree->esquerda = insere(tree->esquerda, informacao);
 else if ( informacao > tree->informacao )
 tree->direita = insere(tree->direita, informacao);
 return tree;
}
 
struct nodo *GetMax(nodo *tree) {
 if (tree->direita == NULL) {
 P=tree;
 tree = tree->esquerda;
 } else {
 tree->direita = GetMax(tree->direita);
 }
 return tree;
}
 
struct nodo *retira(nodo *tree, TIPO informacao) {//Preencha
 if (tree==NULL) {
 cout << _______________________________ << endl;
 } else {
 if (informacao==tree->informacao) {
 if (tree->esquerda==NULL) {
 tree = ________________________;
 } else {
 if (tree->direita==NULL) {
 tree = _________________________;
 } else {
 tree->esquerda = GetMax(tree->esquerda);
 tree->informacao = P->informacao;
 }
 free(P);
 }
 } else {
 if ( informacao < tree->informacao) {
 ___________________________________________
 } else {
 ______________________________________
 }
 }
 }
 return tree;
}
 
void infixa ( nodo *tree ) {
 if ( tree != NULL ) {
 infixa(tree->esquerda ); ///perc sub-arvore esquerda
 cout << tree->informacao << " ";
 infixa(tree->direita); ///perc rec. sub-arv direita
 }
}
int main() { //freopen("arvore.in","r",stdin);
 nodo *raiz = 0;
 TIPO valor;
 int elementos;
 cin >> elementos;
 while (elementos--){
 cin >> valor; 
 raiz = insere ( raiz, valor );
 }
 infixa (raiz); 
 cout << endl;
 return 0;
} 
 prof. Neilor Tonin 13
Exercício 1
Complete a rotina retira (ao lado)
Exercício 2
Problema 1195 do portal URI Online Judge
Exercício 3
Fazer a rotina de busca de um nodo, 
informando:
M nao existe
 Ou
M existe. Caminho: FZT
Exercício 4
Problema 1200 do portal URI Online Judge
Exercício 5
Problema 1201 do portal URI Online Judge
Exercício 6
Problema 1215 do portal URI Online Judge
Exercício 7
Fazer um menu principal com as opções: 
 Digite a opcao desejada na arvore:
 "1 - Insercao"
 "2 - Busca"
 "3 - Retirada"
 "4 - Listagem Prefixa"
 "5 - Listagem Infixa"
 "6 - Listagem Posfixa"
 "Outro Numero - Sair";
Utilize a opção switch / case:
 cin >> opcao;
 switch (opcao) {
 case 1:
 …
Exercícios
Algoritmos e Estrutura de Dados III
Árvore AVL
A árvore AVL é uma árvore binária de busca balanceada dinamicamente, ou seja, ao inserir qualquer 
nodo, a diferença entre o nível de suas folhas é de no máximo 1 nível. Contudo, para garantir essa 
propriedade em aplicações dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada 
operação sobre seus nós (inclusão ou exclusão). Um aspecto muito interessante é a eficiência deste tipo
de estrutura, pois na pior das hipóteses o tempo gasto para uma operação é O(nlog2n).
O nome AVL vem de seus criadores soviéticos Adelson Velsky e Landis, e sua primeira referência 
encontra-se no documento "Algoritmos para organização da informação" de 1962.
Ao inserir qualquer nodo há uma rotação de parte da árvore para garantir o equilíbrio. Ao considerar 
um nodo com duas sub-árvores (esquerda e direita), se a sub-árvore esquerda for maior em um nível, o 
peso do nodo em questão é -1 e caso contrário, o peso é +1. Resumindo, o peso de cada um dos nodos 
da árvore é -1, +1 ou 0 (zero), conforme desenho abaixo:
 Intependente dos nodos que forem inseridos, a árvore permanece sempre balanceada. Isso pode ser 
conferido ao inserir os nodos abaixo em ordem:
→ 14, 5, 20, 22, 40, 76, 60, 3, 12, 30
 prof. Neilor Tonin 14
Algoritmos e Estrutura de Dados III
Exercícios:
1) POSCOMP 2005 - Em uma estrutura de árvore binaria de busca, foram inseridos os elementos “h”,“a”,“b”,“c”,“i”,“j”,nesta sequência. O tamanho do caminho entre um no qualquer da árvore e a raiz e dado pelo numero de arestas neste
caminho. Qual o tamanho do maior caminho na árvore, apos a inserção dos dados acima?
(a) 2 (b) 6 (c) 4 (d) 5 (e) 3
2) POSCOMP 2009 - Considere uma árvore binária de busca T com n nós e altura h. A altura de uma árvore é o número
máximo de nós de um caminho entre a raiz e as folhas. Analise as afirmativas a seguir:
I. h < 1 + log2 n ;
II. Todo nó que pertence à subárvore esquerda de um nó x tem valor maior que o
pai de x.
III. Uma busca em ordem simétrica (in-order) em T produz uma ordenação
crescente dos elementos de T.
Assinale a alternativa CORRETA:
A) Apenas a afirmativa I está correta;
B) Apenas a afirmativa II está correta;
C) Apenas a afirmativa III está correta;
D) Apenas as afirmativas I e II estão corretas;
E) Apenas as afirmativas I e III estão corretas.
3) CESPE - 2012 - Banco da Amazônia - Técnico Científico - Administração de Dados (/questoes-de-concurso/pr
DiscipIina: AIgoritmos e Estrutura de Dados (TI) Assunto: Árvores 
As operações de busca em uma árvore binária não a aIteram, enquanto operações de inserção e remoção de nós
provocam mudanças sistemáticas na árvore.
a) Certo b) Errado
4)4)
5)5)
 prof. Neilor Tonin 15
Algoritmos e Estrutura de Dados III
 prof. Neilor Tonin 16
6)
7)
Algoritmos e Estrutura de Dados III
Trabalho – Utilização de árvores como indexador de arquivo de dados
As árvores são ótimas para implementar indexação, pois aceleram o processo de pesquisa de informações. Acesso em disco é sempre
mais lento do que acesso em memória. Exclusões e inclusões mantendo os dados de um arquivo ordenado, por exemplo, implicariam na
movimentação de uma grande quantidade de dados, sendo um processo excessivamente lento para ser utilizado em aplicações práticas.
A utilização de índices tem por objetivos:
 rapidez no processo de inclusão de novos registros
 rapidez no processo de pesquisa do arquivo
 rapidez no processo de atualização do arquivo
A inclusão em um arquivo de dados será sempre efetuada no final do arquivo, sendo então um procedimento fácil de implementar. Para
garantir então rapidez de pesquisa, uma estrutura de indexação reduziria em muito os acessos a disco. O índice seria um mapeamento que
associa cada chave da árvore de índice a uma chave no arquivo de dados.
A atualização utilizando índices também é muito eficiente. Se um registro deve ser alterado, podemos encontrá-lo rapidamente. Se um
registro deve ser removido basta remover a sua referência no índice (remoção lógica). A remoção definitiva do registro do arquivo pode
ser feita em um processo de reorganização posterior, realizado esporadicamente.
Uma base de dados indexada é então composta por duas partes básicas: um arquivo de dados e uma estrutura de índice associada.
Segue exemplo de uma estrutura de índice utilizando ABP, onde a chave de índice é o campo nome: 
 
A estrutura do arquivo de dados é apresentada a seguir:
 
Registro E# Código Nome Telefone Endereço Cidade UF
0 12 Elisa 9999-2222 R. Goiás, 14 Erechim RS
1 4 Caio 520-9091 Av. P. P. de Souza, 124, Ap 301 Erechim RS
 ... ... ... ... ... ... ... ...
11 26 Gilda 321-3675 Erechim RS
A estrutura da árvore de indexação:
class nodo {
 private:
 nodo *esq;
 string nome;
 int pos;
 nodo *dir;
 public:
...
A Implementar:
Implemente o programa agenda que é a manipulação de um arquivo de dados 
binário com a estrutura apresentada acima e índice por nome. O programa deve
abrir um aquivo de dados binário existente em alguma pasta especificada e 
apresentar as seguintes opções:
• Incluir um cliente da agenda (inclui registro no arquivo de dados 
(agenda.dat) e inclui referência correspondente na árvore de índice.
• Excluir (Marca como excluído no arquivo de dados e exclui referência da 
árvore de índice.
• Consultar dados pelo Nome da pessoa (busca código nome telefone end, 
etc... no arquivo de dados através da árvore de índice)
• Listar em ordem Alfabética (faz percurso na arvore na forma infixa, 
buscando para cada referência o registro correspondente no arquivo de 
dados: código, nome, telefone, etc...
Data Limites:
 prof. Neilor Tonin 17
T (ponteiro)
Elisa 0
Gilda 11Caio 1
Ana Denis Fábio 12 Valdo 109 4
Bia 8 João 14
Hélio 19
Algoritmos e Estrutura de Dados III
Árvores de busca Multidirecionais
Uma ABP não é viável para implementação em disco, pois a busca de cada nodo requer um acesso a disco. Se agruparmos
várias chaves em cada nodo, reduzimos o tempo de pesquisa. Esse agrupamento reduz a altura da árvore. Ex:
 ABP
 
A implementação com agrupamento de chaves é chamada Árvore de busca Multidirecional ou Árvore de busca M-vias,
e é uma árvore de grau M. 
Em uma árvore de ORDEM M, cada nodo tem M ou menos subárvores.
--> Um nodo com 2 chaves = 3 subárvores (Ordem 3)
--> Um nodo com 3 chaves = 4 subárvores (Ordem 4)
--> Um nodo com 4 chaves = 5 subárvores (Ordem 5)
Alguns aspectos das árvores multidirecionais abaixo:
- Na árvore (a), os nodos A,D,E,G são completos e B, C, F e H são incompletos.
- Um nodo com pelo menos uma subárvore vazia é denominado semifolha: (a): b até h. (b): B até G e I até R.
- A árvore (a) e a árvore (b) não são balanceadas, porque diferentemente das ABPs, que podem ter folhas em níveis
diferentes, uma Árvore multidirecional só será balanceada se todas as folhas se encontrarem no mesmo nível.
 prof. Neilor Tonin 18
500
420 800
720480180 980
150 300 455 499 850798515 995
112 190 987536
110
245 670
Ordem:
Balanceada(s/n):
Ordem:
Balanceada(s/n):
Algoritmos e Estrutura de Dados III
Inserção em uma árvore multidirecional balanceada de ordem 3
Árvores B
Devido ao pouco desperdício, as árvores B (ou variações dela) são utilizadas com muita freqüência em sistemas de arquivos
reais. Uma árvore B de ordem M é uma árvore de busca multidirecional balanceada que:
- cada nodo tem no máximo M-1 chaves e a raiz tem no mínimo 1 chave 
- cada nodo não-raiz tem no mínimo (M-1)/2 chaves ( ordem 11 tem no mínimo 5 chaves /nodo; ordem 4: mínimo 1)
- todas as folhas devem estar no mesmo nível
* Alguns autores consideram que uma árvore de ordem 4 possa ter 4 chaves e 5 filhos em cada nodo. Outros ainda
consideram a ordem como n/2, ou seja, uma árvore de ordem 2 possa ter 4 chaves por nodo e 5 filhos.
-> Como em Tenembaum 95, de forma coerente, consideraremos Ordem como sendo o Grau máximo da árvore
(número máximo de filhos por nodo).
Nível Mínimo Máximo
Nodos Chave Nodos Chaves
0
1
2
...
1
2
2* (q+1)
1
2*q
2*q*(q+1)
1
m
m2
m-1
(m-1)*m
(m-1)*m2
sendo que q = (m-1)/2
 prof. Neilor Tonin 19
Ordem:
Balanceada(s/n):
Algoritmos e Estrutura de Dados III
Por exemplo, considerando uma árvore de Ordem 4, qual o número mínimo e máximo de nodos que ela pode ter nos níveis
0, 1 e 2 respectivamente? E no total? Mostre graficamente.
Comparando com uma árvore binária qualquer de 3 níveis (0-2), qual é o número máximo de chaves que ela poderia ter?
Inserção em uma árvore B
A seguir, são mostrados alguns passos para inserção em árvores B. Deve-se observar a divisão que ocorre em um nodo
quando o número de chaves ultrapassa o número de nodos permitidos. Se a ordem da árvore for par, as n-1 chaves,
excluindo a chave do meio devem ser divididas em 2 grupos de tamanhos diferentes: um grupo com tamanho n/2 e outro
grupo com tamanho (n-1)/2.O segundo grupo é sempre de tamanho (n-1)/2 independentemente do fato de n ser ímpar ou
par, pois quando n é impar, (n-1)/2 será igual a n/2. Como exemplo, considere duas árvores, de ordem 4 e 5
respectivamente.
Veja abaixo, na figura da esquerda, o procedimento de inserção emuma árvore de ordem 5.
Inserção em uma árvore B de ordem 3:
Tente inserir o nodo 10:
Cada nodo pode ter no máximo 
3 filhos
https://www.cs.usfca.edu/~galles/visualization/BTree.html
 prof. Neilor Tonin 20
3 6
1 2 4 5 7 8
Algoritmos e Estrutura de Dados III
Compactação (compressão) de Dados 
1. Para que comprimir?
Ao contrário do que possa parecer, comprimir não é somente reduzir o tamanho de um arquivo: além da compressão
utilizada em arquivos para reduzir o espaço físico utilizado por eles, há também a compressão que é utilizada para
melhorar a performance em uma trasmissão de dados. 
A redução do espaço físico é mais comumente utilizada em bancos de dados que, incorporando a compressão no projeto de
seus registros, permite um significativo ganho em termos de ocupação em disco e velocidade de acesso.
Exemplos (bancos de dados): Dbase, Interbase, Paradox, Postgress
Exemplos (arquivos): Openoffice, Word
Como foi mencionado anteriormente, a utilização mais conhecida da compressão de dados é a redução do espaço ocupado
por arquivos. De fato, esta é aplicação mais comum e mais difundida comercialmente. Afinal, dado um dispositivo restrito
de armazenamento que é um disquete, e um grande depositório de arquivos que é o disco rígido, é evidente a necessidade
de muitas vezes realizar-se a redução do tamanho de arquivos para transportá-los ou simplesmente armazená-los.
A compressão também é utilizada para agilizar a transmissão de dados alterando a taxa de transmissão. Se possuímos um
modem que opera a 9600 bps (bits por segundo), é possível que ele transmita como se estivesse a 14400 bps? Sim! Basta
que ele permita a compressão de dados transmitidos, ampliando sua capacidade de transferência de informação. Na
verdade, o modem continuará transmitindo a uma taxa de transmissão de 9600 bps, mas a taxa de transferência de
informação estará ampliada para 14400 bps. A compressão de dados permite, portanto, o aumento na velocidade de
transmissão de dados.
2. Tipos de Compressão 
1.1. Compressão Lógica 
A compressão lógica refere-se ao projeto de representação otimizada de dados. Um exemplo clássico é o projeto de um
banco de dados utilizando seqüências de bits para a representação de campos de dados. No lugar de seqüências de
caracteres ou inteiros, utiliza-se bits, reduzindo significativamente o espaço de utilização do banco de dados.
Este tipo de compressão é possível de ser efetivada em campos projetados para representar dados constantes, como datas,
códigos e quaisquer outros campos formados por números. A característica lógica da compressão encontra-se no fato dos
dados já serem comprimidos no momento do armazenamento, não ocorrendo sua transformação de dados estendidos para
comprimidos. Ex.: Representação de “01 de Abril de 2003” : 15 bytes
“01 Abr 2002” : 9 bytes
“01042002” : 8 bytes
Tem como reduzir ainda mais?????
A razão da compressão é dada por: tamanhodos dadosoriginais
tamanhoda cadeia de dadoscomprimido
2.1. Compressão Física 
A compressão física é aquela realizada sobre dados existentes, a partir dos quais é verificada a repetição de caracteres para
efetivar a redução do número de elementos de dados. Existem dois tipos de técnicas para sinalizar a ocorrência de
caracteres repetidos: 
1. um deles indica o caracter (ou conjunto de caracteres) repetido através da substituição por um caracter especial; 
2. outras técnicas indicam a freqüência de repetição de caracteres e representam isto através de seqüências de bits. 
 prof. Neilor Tonin 21
Algoritmos e Estrutura de Dados III
3. Compressão Orientada a Caracter 
As técnicas de compressão orientadas a caracter não são as mais eficientes ou as mais sofisticadas. Pelo contrário, em geral
elas são utilizadas num primeiro nível de compressão multinível, onde os demais níveis podem ser técnicas estatísticas de
compressão.
Aqui serão analisados 8 técnicas de compressão orientada a caracter, de modo a dar uma noção das possíveis aplicações
deste tipo de compressão.
a) Supressão de Caracteres Nulos ou brancos 
Nesta técnica, temos como objetivo comprimir apenas os caracteres nulos ou brancos. Para a compressão, utiliza-se a
seguinte seleção de caracteres indicadores: Ce N onde Ce é um caracter especial (poderia ser o $, por exemplo) e N é o
número (em binário) de caracteres brancos repetidos seqüencialmente. 
Então, por exemplo, uma seqüência do tipo: 
... vazio. Exatamente o que... 
pode ser comprimida como sendo: 
... vazio.$8Exatamente o que... 
o que demonstra uma redução de 6 bytes no trecho de texto apresentado.
Esta técnica pode ser extendida aos números nulos (zero). Ex.: A seqüência “000053João Silva 890000”
ficaria:
 “#453João Silva$2789#4”
Outras formas de indicação de compressão podem ser utilizadas, com visto na seção anterior. Como trata-se de uma
compressão de brancos, não há a necessidade de explicitação do caracter comprimido.
O algoritmo para a técnica apresentada é muito simples: 
1. inicializa-se um contador para o cálculo do número de repetições de brancos;
2. lê-se o caracter do arquivo a comprimir;
3. verifica-se se o caracter é um branco;
4. se for, incrementa-se o contador e verifica-se se o número de caracteres ultrapassou a 255 (limite binário); se
verdadeiro, colocam-se os caracteres indicadores no arquivo comprimido e volta-se ao passo 1, caso contrário,
volta-se ao passo 2;
5. se não for, verifica-se se o contador é maior que 2, valendo a pena comprimir; se é, colocam-se os caracteres
indicadores no arquivo comprimido, e volta-se ao passo 1, se não é, copiam-se os caracteres lidos no arquivo
comprimido e volta-se ao passo 1. 
O fluxograma para o algoritmo apresentado é mostrado a seguir: 
No caso de haver 350 caracteres brancos seguidos, utilizaria-se $255$95 
 prof. Neilor Tonin 22
Algoritmos e Estrutura de Dados III
b) Comprimento de Fileira 
Também chamada de Run-length, esta técnica utiliza sempre uma combinação de 3 bytes para representar uma
compactação. o formato é Ce X N onde Ce é o caracter especial, X é o caracter repetido e N é o número (binário) de
repetições.
No caso de um caracter ser repetido mais do que 255 vezes, basta repetir a combinação Ce X N, onde n será o número de
repetições que ainda faltam para comprimir corretamente a cadeia original.
Funcionamento do algoritmo:
1. inicializa-se um contador de caracteres, destinado ao controle de cada caracter, buscando a verificação de existência de
repetição;
2. inicializa-se um contador de repetições do caracter procurado;faz-se a leitura do caracter no arquivo a comprimir;
3. incrementa-se o contador de caracteres;
4. se o contador de caracteres for igual a 1, o caracter é armazenado e volta-se ao passo 3 para verificação de repetição;
5. verifica-se se o caracter armazenado é o que procuramos; se for, incrementa-se o contador de repetições;
6. verifica-se se o contador de repetição é maior ou igual a 4; se for menor, gravam-se os caracteres lidos no arquivo
comprimido e volta-se ao passo 1;
7. realiza-se a gravação dos caracteres indicadores no arquivo comprimido e volta-se ao passo 1. 
 
c) Mapeamento de Bit 
Quando é sabida a existência de múltiplas ocorrências não consecutivas de determinado caracter no arquivo a comprimir,
utiliza-se a compressão por mapeamento de bit. Esta técnica utiliza-se de um byte no arquivo comprimido para indicar,
através dos bits, a ocorrência do caractere repetido.
Desta forma, caso desejarmos comprimir todos os caracteres a de um texto, devemos indicá-lo no mapa de bits. Cada mapa
descreve 8 bytes, um por bit do arquivo manipulado. Portanto, para letra encontrada a cada trecho de 8 bytes, será
assinalada no mapa de bits. Por exemplo: 
... abacate... será descrito como: ... Mbbcte... 
onde Mb é o mapa de bits correspondente à compressão do caracter a . Este mapa é composto, para o exemplo, dos bits: 
onde o primeiro zero indica a presença de um caracter a na primeira posição, valor um em seguida indica um caracter
diferente, e assim por diante, até completar o mapa. Convenciona-se, portanto, que o bit 0 indica a presença do caracter a
comprimir e o bit 1 a sua ausência.
O algoritmo para esta técnica necessita do controle do mapa de bits:
 prof. Neilor Tonin 23
contcar = 0
contrep = 1
buffer = ''
Lê caracter
coloca caracter no buffercontcar = 1?
contcar = contcar +1
caracter = 
procurado?
contrep = contrep + 1
contrep>= 4 saida = saida + '@' + procurado + chr(contrep)
procurado = caracter
sim
não
sim
não
sim
não
saida = saida + '@' + buffer*contrep
Ao terminar a leitura, joga-se o
que restou no buffer para a saída
buffer = caracter
contcar = contrep = 1
Algoritmos e Estrutura de Dados III
1. inicializa-se o mapa de bits colocando todos os bits em zero;
2. inicializa-se o contador;
3. realiza-se a leitura do caracter no arquivo a comprimir;
4. compara-se o caracter lido com o caracter procurado; se forem o mesmo, então vai-se para o passo 6;
5. troca-se para 1 o bit da posição atual;
6. incrementa-se o contador;
7. verifica-se se o contador chegou a 8; se verdadeiro, então grava-se o mapa de bits e os caracteres diferentes do
comprimido, e volta-se para o passo 1; senão, volta-se ao passo 3. 
A seguir é apresentado o fluxograma que descreve o algoritmo: 
d) Compactação de Meio Byte 
Este tipo de compactação é utilizado quando encontramos uma seqüência de bits em comum nos caracteres de
determinado arquivo. Um tipo de repetição de bits de grande ocorrência é a que acontece em caracteres numéricos.
Por exemplo, se observarmos o conjunto binário da tabela ASCII para os caracteres numéricos, teremos:
ou seja, se isolarmos os primeiros 4 bits de cada byte de caracter numérico, veremos que há uma constância de valores.
Estes valores constantes são um exemplo de objetos de compactação de meio byte. A compactação de meio byte
propriamente dita consiste na seguinte seqüência de caracteres indicadores: 
onde Ce é o caracter especial, N é o número (binário) de caracteres comprimidos e Cn é a metade do caracter comprimido.
Na seqüência de caracteres indicadores apresentada são apresentados 5 caracteres porque este é o mínimo para que a
compressão seja válida, uma vez que até 4 caracteres ela necessita um número de byte igual ou maior. Observe também que
o número de repetições está ocupando apenas meio byte. Isso significa que ele pode indicar apenas até 16 caracteres, ou
seja, este formato permite a compactação de uma seqüência de, no máximo, 16 caracteres. 
Mas então surge a pergunta: não há como estender este formato para permitir a compactação de uma seqüência maior de
caracteres? A resposta é sim, existe a compactação de byte inteiro , onde o número N ocupa 1 byte, ao invés de meio.
Neste formato estendido, o restante dos caracteres indicadores permanecem os mesmos, sendo alterado apenas a
 prof. Neilor Tonin 24
Algoritmos e Estrutura de Dados III
representação do número de caracteres. Com a representação de byte inteiro, a capacidade de compressão aumenta para 256
caracteres, o que permite um ganho expressivo em se tratando de longas seqüências de caracteres. 
O algoritmo para implementação da compactação de meio byte é o seguinte:
1. inicializa-se um contador de caracteres;
2. procede-se a leitura do caracter;
3. verifica-se se o caracter possui a seqüência de bits a comprimir;
4. caso esteja dentro do grupo a comprimir, incrementa-se o contador e volta-se ao passo 2;
5. verifica-se se o contador é maior que 4;
6. se não for, gravam-se os caracteres lidos no arquivo comprimido e volta-se ao passo 1, reiniciando o processo;
7. colocam-se os caracteres indicadores no arquivo comprimido e volta-se ao passo 1. 
O fluxograma para a representação do algoritmo é apresentado a seguir.
e) Codificação Diatômica 
Esta técnica de compressão permite a representação de um par de caracteres em apenas um caracter especial. Normalmente
utilizam-se tabelas com pares de caracteres e sua freqüência de ocorrência em determinado tipo de arquivo. Obviamente
procura-se substituir os caracteres de maior freqüência, associando a cada dupla um caracter especial.
Em texto da língua portuguesa, por exemplo, duplas de ocorrência freqüente são a letra a acentuada com til seguido da letra
o (ão) e a letra e com acento agudo seguido de um espaço em branco (é ). A cada uma dessas seqüência deve-se atribuir um
caracter especial para nos permitir a compactação através da codificação diatômica. Obviamente, estes são apenas dois
exemplos de duplas de caracteres, numa tabela normal para compactação utilizam-se mais de 20 duplas para que seja obtida
uma compressão razoável.
Para a implementação da codificação diatômica segue-se o seguinte algoritmo:
1. lê-se um par de caracteres;
2. verifica-se sua existência na tabela de pares;
3. se exitente, coloca-se o caracter especial correspondente no arquivo comprimido e volta-se ao passo 1;
4. coloca-se apenas o primeiro caracter no arquivo comprimido;
5. desloca-se o segundo caracter para a primeira posição;
6. lê-se o próximo caracter e volta-se ao passo 2. 
O fluxograma correspondente é o seguinte: 
 prof. Neilor Tonin 25
Algoritmos e Estrutura de Dados III
f) Substituição de Padrões 
A substituição de padrões é semelhante à codificação diatômica, pois também ocorre a substituição de um conjunto de
caracteres por um caracter especial. PALAVRA => Ce 
A utilização mais comum para este tipo de compressão é a de arquivos de programas de linguagens de programação. Uma
vez que as linguagens contém diversas palavras que se repetem freqüentemente em programas, utiliza-se esta característica
para a sua compressão.
Uma variante da substituição de padrões para permitir a codificação de um maior número de palavras é a utilização de dois
caracteres para indicação da ocorrência de determinada palavra: 
C N 
onde C é um caracter escolhido para indicar a compressão e N é o número (binário) da palavra a substituir. Isso permite a
codificação de até 256 palavras reservadas, o que anteriormente era limitado ao número de caracteres especiais que
poderíamos utilizar.
Por exemplo, as palavras reservadas begin e end da linguagem Pascal poderiam ser, por exemplo, substituídas pelos
códigos $1 e $2 . As demais palavras reservadas da linguagem também poderiam ser codificadas desta maneira, permitindo
uma compressão considerável de um arquivo de programa.
Como esta técnica assemelha-se muito à da codificação diatômica, deve tomar como base para a programação o algoritmo e
o fluxograma apresentados para aquela técnica. Desta forma não serão apresentados formas distintas de programação.
4. Compressão Estatística 
A idéia da compressão estatística é realizar uma representação otimizada de caracteres ou grupos de caracteres. Caracteres
de maior freqüência de utilização são representados por códigos binários pequenos, e os de menor freqüência são
representados por códigos proporcionalmente maiores.
Neste tipo de compressão portanto, não necessitamos saber qual caracter vai ser comprimido, mas é necessário, porém, ter o
conhecimento da probabilidade de ocorrência de todos os caracteres sujeitos à compressão. Caso não seja possível a
tabulação de todos os caracteres sujeitos à compressão, utiliza-se uma técnica adequada para levantamento estatístico dos
dados a comprimir, formando tabelas de probabilidades.
Para sabermos como foi concebido este tipo de compressão, veremos na seção seguinte a Teoria da Harmonia, a partir da
qual teremos uma noção de como se processa a compressãoestatística.
4.1. Teoria da Harmonia 
Esta Teoria baseia-se no princípio físico da Entropia. A Entropia é a propriedade de distribuição de energia entre os átomos,
tendendo ao equilíbrio. Sempre que um sistema físico possui mais ou menos quantidade de energia que outro sistema físico
em contato direto, há troca de energia entre ambos até que atinjam a entropia, ou seja, o equilíbrio da quantidade de energia
existente nos sistemas. Ao atingir o estado de equilíbrio, sabe-se que estes sistemas estão utilizando o mínimo de energia
possível para sua manutenção, e assim se manterão até que outro sistema interaja sobre eles.
Aplicada à informação, a Teoria da Entropia permite a concepção de uma teoria da Harmonia, ou seja, um ponto de
equilíbrio onde a informação pode ser representada por uma quantidade mínima de símbolos. Para chegarmos a esta
representação ideal, basta que tenhamos a quantidade de símbolos utilizada e a probabilidade de ocorrência deles. Com
base nisso, é possível calcular a quantidade média de bits por intervalo de símbolo:
havendo n símbolos, cada qual com uma probabilidade p . A representação de quantidades em binário é dada pela base 2 do
logaritmo. Foi utilizado um valor n log n por sua proporcionalidade entre quantidade de informação e tempo (para mais
detalhes, veja bibliografia indicada no capítulo A). Por outro lado, a fórmula apresentada é semelhante à utilizada para
verificação da energia de um sistema físico, utilizada na Teoria da Entropia.
Na prática, a fórmula anteriormente apresentada permite-nos verificar se é possível a otimização da quantidade de bits
utilizados para representação de determinado conjunto de símbolos. Duas representações podem ser comparadas para a
verificação de qual ocupa menos bits em média. Isso nos permite concluir que é possível a criação de um método de
compactação construído a partir da probabilidade de ocorrência de símbolos.
 prof. Neilor Tonin 26
Algoritmos e Estrutura de Dados III
De fato, existem técnicas que utilizam a análise da probabilidade para compactação de dados. Estas são chamadas de
estatísticas e serão analisadas nas seções seguintes.
4.2. Codificação Huffman 
Esta técnica de compressão permite a representação em binário de caracteres a partir de sua probabilidade de ocorrência.
Esta representação é gerada por um sistema de decodificação em árvore binária, o que impede a ambigüidade na análise do
código.
A ambigüidade, neste caso, refere-se a uma decodificação que permite a confusão com outros caracteres. Por exemplo,
determinado caracter C1 tem o código binário 01 e outro caracter C2 tem o código 0100, isto implica que, ao verificarmos a
seqüência binária para C2 poderemos estar interpretando como C1, ao serem lidos apenas os bits 01. Por isso, a codificação
Huffman utiliza o projeto em árvore binária para projeto dos bits que representam os caracteres, de forma que permitam
uma decodificação única para cada caracter.
A codificação Huffman necessita de que cada caracter tenha um valor de probabilidade de ocorrência. A partir dos
caracteres de menor valor, começa a construção da árvore binária.
Suponha que após a análise estatística de um arquivo texto a ser compactado verificou-se que 91% dos dados contidos no
arquivo sejam os caracteres IHFBDEGCA. Um configuração possível para a árvore de huffman então seria:
A probabilidade do ramo é a soma das probabilidades das folhas (GC) 13% = 6% + 7% . Os valores binários serão
membros do código formado. Para a codificação dos próximos caracteres, basta continuarmos a construção da árvore. 
A probabilidade final da árvore é sempre 1,0, uma vez que necessariamente deve-se atingir 100% das ocorrências de
caracteres, permitindo uma codificação total. Uma vez terminada a árvore, basta a formalização da codificação, que é feita
com a leitura dos valores binários, da raiz para as folhas. Os valores binários lidos serão o código do percurso da raiz até a
folha correspondente ao caracter que se deseja o código. A tabela de códigos fica a seguinte:
 Tabela dos símbolos e freqüência:
Símbolo Freqüência Código
A 15 111
B 6 101
C 7 1101
D 12 011
E 25 10
F 4 01001
G 6 1100
H 1 01000
T 15 00
Desta forma, estão codificados os caracteres através da técnica de Huffman. Observe que o caracter de maior freqüência
possui o menor valor. Isso é exatamente o objetivo da compressão estatística, uma vez que permite a substituição do
 prof. Neilor Tonin 27
91 %IHFBD | EGCA [Tene 95]
53 %38 %I | HFBD E | GCA
HFB | D GC | AE, 25% 28 %I, 15% 
13 %
D, 12% A, 15%HF | B G | C
H | F
C, 7%B, 6% G, 6%
H, 1% F, 4%
Algoritmos e Estrutura de Dados III
caracter de maior ocorrência por apenas um bit. Assim acontece com os demais caracteres, em ordem crescente do número
de bits, conforme a prioridade. 
Cabe salientar, por fim, que a codificação Huffman manteve a propriedade de permitir a decodificação direta, não
permitindo que os bits da codificação de um caracter confundisse com a de outro. 
4.3. Codificação Shannon-Fano 
A forma desta técnica tem muitas semelhanças com a de Huffman. Necessita-se de uma tabela com a probabilidade de
ocorrência de cada caracter, e de um procedimento para a codificação em binário. Por outro lado, o procedimento para a
codificação, diferentemente de Huffman, baseia-se na divisão de conjuntos de probabilidades para a obtenção do código
binário.
Para a codificação, devemos ter os caracteres com suas probabilidades de ocorrência:
 
O passo seguinte é ordenar colocando os caracteres de maior probabilidade no topo da tabela, até o menor, na base: 
 
Uma vez feito isso, divide-se a tabela em dois grupos cuja soma de probabilidades seja igual ou semelhante. No caso da
tabela acima, serão obtidos dois grupos, um composto pelo caracter C1 e outro pelos demais. O primeiro grupo recebe
como primeiro valor de código o binário 0 e o segundo recebe 1:
 
Como para o primeiro grupo não há ambigüidade em termos apenas um bit, vamos resolver o problema do segundo grupo.
Para isso, repetimos o procedimento anterior, dividindo em dois subgrupos de probabilidades equivalentes. O caracter C2
forma o primeiro subgrupo e os demais formam o segundo. Mais uma vez vamos colocar 0 para distinguir o primeiro e 1
para o segundo: 
Finalmente, para resolução da última duplicidade, repete-se o processo, inserindo o binário 0 na seqüência do código de C1
e 1 para C3:
 
 prof. Neilor Tonin 28
Algoritmos e Estrutura de Dados III
Trabalho __ – Compactador
Neste trabalho existe a possibilidade de escolha (implementando o compactador Run-length para caracteres repetidos vale como um 
trabalho normal). Implementando Huffman baseado na tabela de shannon-fano, vale 2, ou seja, dá a possibilidade de não entregar um dos
próximos trabalhos. Para qualquer um dos métodos escolhidos, a entrada será um texto (txt) com cerca de 8 KB de tamanho.
Versão 1: Exemplo para compactação utilizando Run-length:
Arquivo de entrada:
aaaa1111111222
xxxxxxxxx222222@
Saída:
@a♦@1•222@
x◙@2♠@@☺
Datas Limites:
Peso 10: _______________ Peso 8: _______________________ Peso 6: _________________________
Versão 2: Exemplo para compactação utilizando Huffman:
Arquivo de entrada:
aaaa1111111222
xxxxxxxxx222222@
Tabela (somente como ilhstração)
x 10 0 0 
2 9 0 1 
1 7 1 0 
a 4 1 1 0 
@ 1 1 1 1
Montando:
110 110 110 110 10 10 10 10 10 10 10 01 01 01 
00 00 00 00 00 00 00 00 00 00 01 01 01 01 01 01
Saída:
█j¬ò caracteres equivalentes à 11011011 01101010 10101010 10010101
chr(0)chr(0)♣U caracteres equivalentes à 00000000 00000000 00000101 01010101 
Datas Limites:
Peso 10: _______________ Peso 8: _______________________ Peso 6: _________________________
Exercícios
Nos próximos exercícios utilize a tabela abaixo ou indique, por exemplo CHR(3) se não quiseres desenhar ocaracter “♥”
Caracter ☺ ☻ ♥ ♦ ♣ ♠ • ◘ ○ ◙ ♂ ♀ ♪ ♫ ☼ ► ◄ ↕ ‼ ¶ § ▬ ↨ ↑ ↓ → ← ∟ ↔
Valor
ASCII
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
Sendo Texto1: 000200AC0000000000bbbbbbbbbbbb2100000000070000000X
 Texto2: 00020011000001254576000 Texto3: o rato roeu a roupa do rei rebelde
1) Utilize a supressão de zeros e brancos para comprimir o Texto1, sendo que o caracter ♫ deve ser utilizado para 
comprimir os zeros e o caracter ♣ deve ser utilizado para comprimir os espaços em branco: 
2) Utilize a técnica de Comprimento de fileira (run-lenght) para comprimir o Texto1. Neste caso, o caracter especial que 
indica a compressão é o CHR(11) (♂).
3) Comprima o Texto1 utilizando mapa de bits para o caracter “0”.
4) Comprima o Texto2 utilizando compactação de meio byte.
5) Comprima o Texto3 utilizando codificação diatômica, usando a seguinte tabela: ♫: ro ►: ob ↕: ab
6) construa a árvore de Shannon-Fano para o texto 3.
 prof. Neilor Tonin 29
Algoritmos e Estrutura de Dados III
Algoritmo da Mochila booleana (0/1) (não pegar/pegar)
O problema da mochila 0/1 pode ser a princípio resolvido por 2 algoritmos (recursivo ou programação dinâmica). Em
termos de performance o algoritmo recursivo é muito ineficiente, “pendurando” na resolução de vários problemas não
muito complexos. O algoritmo que utiliza programação dinâmica pode não ser lá tão eficiente, mas é infinitamente mais
eficiente que o algoritmo recursivo (mochila recursiva)
O algoritmo de programação dinâmica [CLR 17.2-1] consome O(nW) unidades de tempo. Mas isso só é possível se W,
w[1],…,w[n] forem todos inteiros não-negativos. 
Um exemplo clássico da aplicabilidade deste algoritmo é o que lhe dá o nome (capítulo 16 - Th.H. Cormen, Ch.E.
Leiserson, R.L. Rivest, C. Stein ), onde um ladrão de obras de artes entra em uma galeria com uma maleta de tamanho x.
Obviamente ele quer carregar o máximo de valor em obras de artes que caibam em sua maleta. O algoritmo da mochila é
usado para resolver este problema. Segue uma ilustração. Tem-se um mochila com capacidade para carregar 5 quilos e um
total de 4 itens, cujos pesos e valores são os seguintes:
Peso Valor
4 500
2 400
1 300
3 450
Suponha que W = 5 e n = 4. Os vetores w e v são dados pela figura esquerda. A figura direita dá a tabela t.
Peso
1 2 3 4
w 4 2 1 3
v 500 400 300 450
t[5][6]
 itens
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 0 500 500
2 0 0 400 400 500 500
3 0 300 400 700 700 800
4 0 300 400 700 750 850
A execução do algoritmo usando PD (programação dinâmica) se faz através da recurção em iteração com apoio de uma
tabela. Na tabela t[m][n] são guardadas todas as soluções em instância possíveis. Abaixo segue o algoritmo, onde:
Variável Descrição
int w[] Vetor contendo os pesos (weight) de cada um dos itens
int v[] Vetor contendo os valores (values) de cada um dos itens
int n Número de itens que serão considerados (trabalhados)
int W Peso total (capacidade da mochila)
/// peso valor elems capac
int mochila (int w[], int v[], int n, int W){
 for (int col=0; col <=W; y++) {
 t[0][col]=0;
 for (int i=1; i <= n;i++) {
 a = t[i-1][col];
 if (w[i] > col){
 b=0;
 } else {
 b=t[i-1][col-w[i]] + v[i];
 }
 if (a>b)
 t[i][col] = a;
 else
 t[i][col] = b;
 }
 }
 return(t[n][W]);
}
 prof. Neilor Tonin 30
No programa principal, sua chamada seria
 
mochila(w,v,objetos,carga);
Obviamente, segundo estes itens ao lado 
esquerdo, a melhor combinação a carregar
seria o segundo e o quarto item 
(R$ 400,00 + R$ 450,00) totalizando 
R$ 850,00.
Note que pelo peso, poderia-se pegar o
 item de valor R$ 500,00 + R$ 300,00 (5 kg)
ou R$ 450,00 +R$ 300,00 (4 kg). Porém,
 nenhuma destas é a melhor escolha.
Algoritmos e Estrutura de Dados III
O número de linhas será sempre a quantidade de itens (n) e o número de colunas será sempre o W, que seria o tamanho da
mochila. Note que o maior valor possível sempre estará na posição t[n][W] (última linha e coluna à direita). 
Em muitos problemas, além de saber quanto é possível carregar na mochila, necessita-se saber quais valores serão
selecionados pelo algoritmo. Isso é muito simples de se obter através da tabela t (a mesma tabela do exemplo anterior). O
procedimento para isso é listado abaixo:
a) define-se um vetor x[maxobjetos] que conterá 1 ou 0 para cada posição indicando, respectivamente, se o valor
correspondente do vetor w deve ser selecionado ou não. Neste caso é x[5] e se ocupa as posições de 1 a 4.
b) partindo-se do elemento inferior direito (último da matriz t) diminui-se o valor selecionado (w[i]) da coluna, caso ele
seja diferente do elemento da linha anterior. Neste caso, 850 é diferente de 800, portanto coloca-se o valor 1 em x[4] e
diminui-se 3 (w[i]) do y.
c) repete-se o procedimento enquanto a linha for maior do que 0
1 2 3 4
w 4 2 1 3
v 500 400 300 450
t 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 0 500 500
2 0 0 400 400 500 500
3 0 300 400 700 700 800
4 0 300 400 700 750 850
Segue o código desta parte: 
Nota: Isso só é necessário quando se precisa saber quais valores foram selecionados.
 int y=W;
 for ( int i=n; i >0; i--){
 if (t[i][y]==t[i-1][y]) {
 x[i]=0;
 } else {
 x[i]=1;
 y=y-w[i];
 }
 }
0 1 2 3 4
X 0 0 1 0 1
Por último, pode-se desejar somar o total em peso colocado na mochila. Isso se deve ao fato de que mesmo que a mochila
tenha capacidade para 5 kg, pode ser que devido aos objetos, seja colocado na mesma menos do que isso (4,3,2,...etc).
 int peso=0;
 for (int i = 1; i<=n; i++) {
 if (x[i]==1) {
 peso += w[i]; // 2 + 3 = 5
 }
 }
Entrada e saída para problema explanado:
Um grande supermercado fez uma promoção, onde uma pessoa pode entrar e carregar tudo o que conseguir para pegar o
maior valor possível. São 1000 produtos (no máximo) e a pessoa pode carregar um peso que é no máximo 5 kg (varia de
pessoa para pessoa) de produtos não repetidos e cada produto pode valer de 1 a R$ 500,00.
Entrada
4 4 produtos
500 4 R$ 500,00 e 4 kg
400 2 R$ 400,00 e 2 kg
300 1 R$ 300,00 e 1 kg
450 3 R$ 450,00 e 3 kg
5 A pessoa pode carregar 5 kg
Saída
850 A pessoa pegou o produto de 3 kg e o produto de 2 kg
PS.: Note que neste caso específico não precisamos saber quais os produtos foram pegos, ou seja, não há necessidade de
utilizar a segunda parte do algoritmo. 
 prof. Neilor Tonin 31
Volta 2 colunas (0)
Volta 3 colunas (2)
Algoritmos e Estrutura de Dados III
#include <iostream>
#include <cstdio>
#define MAXOBJ 5 // até 4 objetos diferentes
#define MAXCARGA 6 // até 5 kg de carga, no máximo
using namespace std;
int a,b,t[MAXOBJ][MAXCARGA],x[MAXOBJ];
/// peso valor elems capac
int mochila (int w[], int v[], int n, int W) {
 for (int col=0; col <= W; col++) {//Eh necessario coluna zero???
 t[0][col]=0;
 for (int i=1; i <= n; i++) { //linha 1 a n (itens)
 a = t[i-1][col]; //valor da mesma coluna, linha anterior
 if (w[i] > col) { //se peso do elemento for maior que a coluna
 b=0; //valor = 0
 } else {
 b=t[i-1][col-w[i]] + v[i]; //valor = lin ant, com peso complementar à cap.
 }
 if (a>b) {
 t[i][col] = a;
 } else {
 t[i][col] = b;
 }
 }
 /*for (int g=0; g<=n; g++) {
 for (int h=0; h<=W; h++) {
 cout << t[g][h] << " ";
 }
 cout << endl;
 }
 cout << endl;
 */
 }
 return(t[n][W]);
}
int main() {
 freopen("knapsack.in","r",stdin);
 int w[MAXOBJ],v[MAXOBJ];int objetos,limite_carga,total;
 cin >> objetos;
 for (int i=1; i<=objetos; i++) {
 cin >> v[i]; //valor (value)
 cin >> w[i]; //peso (weight)
 }
 cin >> limite_carga;
 total = mochila(w,v,objetos,limite_carga);
 cout << total << endl;
 return(0);
}
 prof. Neilor Tonin 32
Algoritmos e Estrutura de Dados III
Grafos
Como já foi vista a parte teórica de grafos em Teoria dos grafos, nesta parte da disciplina serão abordados problemas com 
implementação dos algoritmos mais conhecidos de grafos e, na medida do possível, algoritmos diferentes dos aqui 
apresentados.
Algoritmo de Bellman-Ford 
É um pouco mais lento que dijkstra, mas é mais simples e fácil de compreender e permite pesos negativos nas arestas, 
enquanto que dijkstra não permite.
#include <iostream>
#define INFINITY 99999999
using namespace std;
typedef struct {
 int source;
 int dest;
 int weight;
} Edge; // Arestas
void BellmanFord(Edge edges[], int edgecount, int nodecount, int source) {
 int i,j;
 int *distance = new int [nodecount];
 for (i = 0; i < nodecount; i++) {
 distance[i] = INFINITY;
 }
 distance[source] = 0;
 for (i = 0; i < nodecount; i++) { // como otimizar este laço?
 for (j = 0; j < edgecount; j++) {
 if (distance[edges[j].dest] > distance[edges[j].source] + edges[j].weight) {
 distance[edges[j].dest] = distance[edges[j].source] + edges[j].weight;
 }
 }
 }
 for (i = 0; i < edgecount; i++) {
 if (distance[edges[i].dest] > distance[edges[i].source] + edges[i].weight) {
 cout << "Ciclo negativo de pesos de arestas detectado" << endl;
 break;
 }
 }
 for (i = 0; i < nodecount; i++) {
 cout << "Distancia menor entre nodos " << source << " e " << i <<" eh " << distance[i] << endl;
 }
 delete distance;
}
int main (void){
 Edge Arestas[100];
 int casos,nc,vertices,arestas;
 cin >> casos;
 for (nc = 0; nc < casos; nc ++){
 cin >> vertices; //m
 cin >> arestas;
 for (int i=0; i< arestas; i++){
 cin >> Arestas[i].source;
 cin >> Arestas[i].dest;
 cin >> Arestas[i].weight;
 }
 BellmanFord(Arestas,arestas,vertices,0); //Arestas,n de arestas,n de vertices,origem);
 cout << endl;
 }
 return(0);
}
Entrada:
2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
Saída:
Ciclo negativo de pesos de arestas detectado
A distancia mais curta entre os nodos 0 e 0 eh 0
A distancia mais curta entre os nodos 0 e 1 eh 919
A distancia mais curta entre os nodos 0 e 2 eh 961
A distancia mais curta entre os nodos 0 e 0 eh 0
A distancia mais curta entre os nodos 0 e 1 eh 10
A distancia mais curta entre os nodos 0 e 2 eh 30
A distancia mais curta entre os nodos 0 e 3 eh 60
 prof. Neilor Tonin 33
Algoritmos e Estrutura de Dados III
Análise do algoritmo
Edge Arestas[100];
typedef struct {
 int source;
 int dest;
 int weight;
} Edge; // Arestas
Arestas[ ] source dest weight
0 0 1 31
1 0 4 78
2 1 2 12
3 1 3 8
4 2 0 -5
5 2 3 124
6 3 4 61
7 3 6 13
8 4 0 78
9 4 5 14
10 5 1 -3
11 6 4 4
i distance[i]
0 1 2 3 4 5 6
distance [ ] 0 α α α α α α
Pega campo dest do vetor de Arestas (arestas[] .dest)
(distance[1] > distance[0] + 31) ? 
α > 0 + 31 ? (sim)
distance[1] = 31 
0 1 2 3 4 5 6
distance [ ] 0 31 α α α α α
(distance[4] > distance[0] + 78) ? 
α > 0 + 31 ? (sim)
distance[4] = 78
0 1 2 3 4 5 6
distance [ ] 0 31 α α 78 α α
(distance[2] > distance[1] + 12) ? 
α > 31 12
distance[2]= 43
...
0 1 2 3 4 5 6
distance [ ] 0 31 43 39 56 70 52
A distancia mais curta entre os nodos 0 e 0 eh 0
A distancia mais curta entre os nodos 0 e 1 eh 31
A distancia mais curta entre os nodos 0 e 2 eh 43
A distancia mais curta entre os nodos 0 e 3 eh 39
A distancia mais curta entre os nodos 0 e 4 eh 56
A distancia mais curta entre os nodos 0 e 5 eh 70
A distancia mais curta entre os nodos 0 e 6 eh 52
 prof. Neilor Tonin 34
Algoritmos e Estrutura de Dados III
Algoritmo de Floyd - Warshall
#include <iostream>
#include <iomanip>
#define INFINITO 999999999
using namespace std;
/* A estrutura digraph representa um digrafo. O campo adj é um ponteiro
para a matriz de adjacência do digrafo. O campo Vertices contém o número de Vértices
 e o campo A contém o número de arcos do digrafo. */
struct digraph {
 int V;
 int A;
 int adj[301][301];
};
 /* Um objeto do tipo Digraph contém o endereço de um digraph. */
typedef struct digraph *Digraph;
void Floyd (Digraph G) {
 for (int k=1; k <= G->V; k++) {
 for (int i=1; i <= G->V; i++) {
 for (int j=1; j <= G->V; j++){
 if ( (G->adj[j][k]+G->adj[k][i] < G->adj[j][i]) ) {
 G->adj[j][i]=G->adj[j][k]+G->adj[k][i];
 }
 }
 }
 }
}
int main(void){
 Digraph D= new (struct digraph);
 int i, j, vertices, arestas, origem, destino, custo;
 cin >> vertices >> arestas;
 for (i=0; i<vertices+1; i++){
 for (j=0; j<vertices+1; j++){
 D->adj[i][j]=INFINITO;
 }
 }
 D->V=vertices;
 D->A=arestas;
 for (i=0; i<arestas; i++){
 cin >> origem >> destino >> custo;
 D->adj[origem][destino]=custo;
 }
 Floyd (D);
 for (i=1;i<D->V+1;i++){ // Mostra a Matriz de Adjascencia
 for (j=1;j<D->V+1;j++)
 cout << setw(12) << D->adj[i][j] << " " ;
 cout << endl;
 }
 return(0);
}
floyd.in
4 7
1 3 5
3 1 4
1 2 8
2 1 10
2 4 12
4 2 6
3 4 3
 prof. Neilor Tonin 35
Algoritmos e Estrutura de Dados III
Algoritmo de Dijkstra
#include <iostream>
#define MAXCST 999999999 //Equivalente à 1<<30
#define MAX 100
using namespace std;
int g[MAX][MAX],vertices;
int dijkstra(int origem, int destino) {
 int i,minimo,atual;
 int passou[MAX],pred[MAX],custo[MAX];
 for(i=0;i<vertices;i++) {
 pred[i] = -1;
 custo[i] = MAXCST;
 passou[i] = 0;
 }
 custo[origem] = 0;
 atual = origem;
 while(atual != destino) {
 for(i=0;i<vertices;i++){
 if (custo[atual] + g[atual][i] < custo[i]) {
 custo[i] = custo[atual] + g[atual][i];
 pred[i] = atual;
 }
 }
 minimo = MAXCST;
 passou[atual] = 1;
 for(i=0;i<vertices;i++){
 if((custo[i] < minimo) && (!passou[i])) {
 minimo = custo[i];
 atual = i;
 }
 }
 //caso não conseguiu ir para lugar algum saindo da origem 
 if(minimo == MAXCST) {
 return MAXCST; 
 }
 for(i=0;i<vertices;i++) {
 cout << pred[i] << " " << custo[i] << " " << passou[i] << endl;
 }
 }
 return custo[destino];
}
int main(){
 int i,j, arestas,orig, dest, peso;
 cin >> vertices >> arestas;
 memset(g,63,sizeof(g)); //1.061.109.567 (deve ser um pouco maior ou igual a MAXCST)
 for (i=0; i <arestas; i++){
 cin >> orig >> dest >> peso;
 g[orig][dest]=peso;
 }
 cout << dijkstra(0,5) << endl << endl;
 cout << dijkstra(0,1) << endl << endl;
 cout << dijkstra(0,4) << endl << endl;
 cout << dijkstra(0,2) << endl << endl;
 return(0);
}
Dijkstra.in
6 11
0 1 41
0 5 29
3 0 45
3 5 38
5 1 29
5 4 21
4 3 36
1 4 32
4 2 32
2 3 50
1 2 51
 prof. Neilor Tonin 36
	Compactação (compressão) de Dados
	#include <cstdio>
	#define MAXOBJ 5 // até 4 objetos diferentes
	#define MAXCARGA 6 // até 5 kg de carga, no máximo
	using namespace std;
	int a,b,t[MAXOBJ][MAXCARGA],x[MAXOBJ];
	/// peso valor elems capac
	int mochila (int w[], int v[], int n, int W) {
	for (int col=0; col <= W; col++) {//Eh necessario coluna zero???
	t[0][col]=0;
	for (int i=1; i <= n; i++) { //linha 1 a n (itens)
	a = t[i-1][col]; //valor da mesma coluna, linha anterior
	if (w[i] > col) { //se peso do elemento for maior que a coluna
	b=0; //valor = 0} else {
	b=t[i-1][col-w[i]] + v[i]; //valor = lin ant, com peso complementar à cap.
	}
	if (a>b) {
	t[i][col] = a;
	} else {
	t[i][col] = b;
	}
	}
	/*for (int g=0; g<=n; g++) {
	for (int h=0; h<=W; h++) {
	cout << t[g][h] << " ";
	}
	cout << endl;
	}
	cout << endl;
	*/
	}
	return(t[n][W]);
	}
	int main() {
	freopen("knapsack.in","r",stdin);
	int w[MAXOBJ],v[MAXOBJ];
	int objetos,limite_carga,total;
	cin >> objetos;
	for (int i=1; i<=objetos; i++) {
	cin >> v[i]; //valor (value)
	cin >> w[i]; //peso (weight)
	}
	cin >> limite_carga;
	total = mochila(w,v,objetos,limite_carga);
	cout << total << endl;
	return(0);