Estrutura de Dados - Valter Castelhano

Prévia do material em texto

ES
TR
UT
UR
A 
DE
DA
DO
S
Estrutura de dados
Valter Castelhano de Oliveira
A Série Universitária foi desenvolvida pelo 
Senac São Paulo com o intuito de preparar 
profissionais para o mercado de trabalho. 
Os títulos abrangem diversas áreas, 
abordando desde conhecimentos teóricos
e práticos adequados às exigências
profissionais até a formação ética e sólida.
Estrutura de dados aprofunda o conceito 
de tipo abstrato de dados, evidenciando 
aspectos de implementação, aplicações
e complexidade, por meio de estudo de 
estruturas abstratas de dados encadeados:
lista ligada, árvores binárias, árvore de
busca, árvores balanceadas, multicaminhos
e grafos. O livro apresenta algoritmos
clássicos implementados com a utilização
de estruturas abstratas de dados e
reforça o estudo da eficiência assintótica
de algoritmos.
SÉRIE
UNIVERSITÁRIA
Dados Internacionais de Catalogação na Publicação (CIP)
(Jeane Passos de Souza – CRB 8a/6189)
Oliveira, Valter Castelhano de
 Estrutura de dados / Valter Castelhano de Oliveira. – São Paulo : 
Editora Senac São Paulo, 2020. (Série Universitária)
	 Bibliografia.
 e-ISBN 978-65-5536-198-8 (ePub/2020)
 e-ISBN 978-65-5536-199-5 (PDF/2020)
 1. Estrutura de dados (Ciência da computação) I. Título II. Série.
20-1164t CDD-005.74
 COM018000
Índice para catálogo sistemático
1. Estrutura de dados 005.74 
M
at
er
ia
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
ESTRUTURA DE DADOS
Valter Castelhano de Oliveira
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Administração Regional do Senac no Estado de São Paulo
Presidente do Conselho Regional
Abram Szajman
Diretor do Departamento Regional
Luiz Francisco de A. Salgado
Superintendente Universitário e de Desenvolvimento
Luiz Carlos Dourado
M
at
er
ia
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
Editora Senac São Paulo
Conselho Editorial
Luiz Francisco de A. Salgado 
Luiz Carlos Dourado 
Darcio Sayad Maia 
Lucila Mara Sbrana Sciotti 
Jeane Passos de Souza
Gerente/Publisher
Jeane Passos de Souza (jpassos@sp.senac.br)
Coordenação Editorial/Prospecção
Luís Américo Tousi Botelho (luis.tbotelho@sp.senac.br) 
Dolores Crisci Manzano (dolores.cmanzano@sp.senac.br)
Administrativo
grupoedsadministrativo@sp.senac.br
Comercial 
comercial@editorasenacsp.com.br
Acompanhamento Pedagógico
Mônica Rodrigues dos Santos
Designer Educacional
Diogo Maxwell Santos Felizardo
Revisão Técnica
Gustavo Moreira Calixto
Preparação de Texto
Bianca Rocha
Revisão de Texto
Bianca Rocha
Projeto Gráfico
Alexandre Lemes da Silva 
Emília Corrêa Abreu
Capa
Antonio Carlos De Angelis
Editoração Eletrônica
Cristiane Marinho de Souza
Ilustrações
Cristiane Marinho de Souza
Imagens
iStock Photos
E-pub
Ricardo Diana
Proibida a reprodução sem autorização expressa.
Todos os direitos desta edição reservados à
Editora Senac São Paulo
Rua 24 de Maio, 208 – 3o andar 
Centro – CEP 01041-000 – São Paulo – SP
Caixa Postal 1120 – CEP 01032-970 – São Paulo – SP
Tel. (11) 2187-4450 – Fax (11) 2187-4486
E-mail: editora@sp.senac.br 
Home page: http://www.livrariasenac.com.br
© Editora Senac São Paulo, 2020
Sumário
Capítulo 1 Capítulo 5
Tipo abstrato de dados, 7 Árvore AVL, 65
1 Entendimento do tipo abstrato 1 Entendimento sobre árvore AVL, 66
de dados, 8 2 Operações de balanceamento 
2 Exemplos do uso de e rotação, 70
encapsulamento, reúso Considerações	finais,	77
e alocação dinâmica, 10
Referências, 77
Considerações	finais,	15
Referências, 15 Capítulo 6
Grafos, 79
Capítulo 2 1 Conceitos básicos de grafos, 80Lista ligada, 17
2 Exemplos de aplicações práticas 
1 Conceito de lista ligada, 18 representadas por grafos, 88
2 Operações de adição Considerações	finais,	96
e remoção de nós, 23
Referências, 96
Considerações	finais,	30
Referências, 31 Capítulo 7
Grafos e multicaminhos, 97
Capítulo 3 1 Representação de multicaminhos Árvores binárias, 33 por grafos, 98
1 Conceito de árvore 2 Algoritmo de Dijkstra para 
em computação, 34 determinar caminhos, 102
2 Elaboração de uma Considerações	finais,	112
árvore binária, 36
Referências, 112
3 Técnicas de varredura, 
altura e profundidade, 41 Capítulo 8
4 Implementando árvore Eficiência assintótica 
com recursividade, 43 de algoritmos, 113
Considerações	finais,	47 1	Eficiência	dos	algoritmos	recursivos	
Referências, 48 e não recursivos aplicados às 
estruturas estudadas, 114
Capítulo 4 Considerações	finais,	126
Balanceamento de árvores, 49 Referências, 127
1 Entendimento sobre a árvore 
binária de busca (ABB), 50 Sobre o autor, 129
2 Técnica de balanceamento 
de árvore binária, 60
Considerações	finais,	64
Referências, 64
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Capítulo 1
Tipo abstrato 
de dados
No processo de desenvolvimento de software, ocorre o envolvimen-
to	de	pessoas	com	diversos	perfis	e	expectativas	quanto	ao	resultado	
a	 ser	 obtido.	 O	 usuário	 final	 espera	 que	 todas	 as	 suas	 necessidades	
sejam	 atendidas,	 e	 a	 equipe	 de	 desenvolvimento	 trabalha	 para	 ofere-
cer	um	sistema	de	qualidade	atendendo	às	restrições	de	prazo	e	custo.	
Apesar das diversas e efetivas técnicas empregadas na engenharia de 
software, diversos projetos estão propensos a apresentar problemas 
associados a custos, prazo e atendimento das necessidades dos usuá-
rios (OLIVEIRA, 2008).
7
8 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
Os estudos na área de computação procuram mitigar o efeito desses 
problemas	propondo	teorias,	técnicas,	métodos	e	práticas	que	auxiliem	
as	equipes	de	desenvolvimento	de	software,	com	destaque	para	técni-
cas de programação, evolução nas linguagens de programação e estu-
do de algoritmos visando à implementação de soluções para problemas 
comuns de programação.
O objetivo deste capítulo é apresentar conceitos associados a tipos 
abstratos	 de	 dados	 (TADs),	 bem	 como	 exemplos	 que	 favoreçam	 o	
entendimento de sua importância para a elaboração de estruturas de 
dados baseadas em alocação dinâmica.
1 Entendimento do tipo abstrato de dados
De forma generalizada, “um algoritmo é um processo sistemático 
para a resolução de um problema” (SZWARCFITER; MARKENZON, 2010, 
p.	 1),	 no	 qual	 as	 informações	 conhecidas	 inicialmente	 (dados	 de	 en-
trada) são computadas pelo algoritmo, resultando em informações de 
saída (dados de saída).
Estruturas	de	dados	são	elementos	de	computação	que	armazenam	
dados	de	formaeficiente	(listas,	pilhas,	filas,	entre	outros),	e	o	estudo	
de algoritmos associados a estruturas de dados é fundamental para a 
formação de programadores e analistas.
O tipo abstrato de dados é caracterizado por um “conjunto de valo-
res	e	uma	sequência	de	operações	sobre	estes	valores”	(TENENBAUM;	
LANGSAM; AUGENSTEIN, 1995, p. 18), ou seja, um TAD encapsula ou 
agrupa um conjunto de dados (estruturas de dados) associado a um 
elemento	de	computação	junto	aos	operadores	(algoritmos)	que	atuam 
na	modificação	desses	dados.	A	figura	1	ilustra	uma	representação	grá-
fica	 de	 um	 TAD.	 Observe	 que	 os	 dados	 são	 acessados	 apenas	 pelas	
operações, protegendo e disciplinando o acesso aos dados, além de 
ocultar como as operações são realizadas.
9Tipo abstrato de dados
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Figura 1 – Representação gráfica de um TAD
Conjunto de dados
Operações sobre o
conjunto de dados
Utilização do TAD,
acessando apenas
as operações.
O	tratamento	de	cadastro	de	clientes,	problema	comum	para	qual-
quer	empresa,	pode	ser	facilmente	resolvido	com	diversos	aplicativos	
disponibilizados na internet. Entretanto, diversos aplicativos oferecidos 
– muitas vezes gratuitamente – demandam esforços de programa-
ção envolvendo o desenvolvimento de programas de computador 
(algoritmos)	e	definição	de	estruturas	de	dados	(muitas	vezes	bancos	
de dados) para armazenar as informações.
De uma forma geral, independentemente da linguagem ou do siste-
ma de implementação, o registro de um cliente pode ser tratado como 
um	TAD,	no	qual	os	dados	do	cliente	são	CNPJ,	razão	social,	endereço	
e previsão de vendas. As operações disponibilizadas poderiam ser: cria-
ção de um registro fornecendo todos os dados do cliente, alteração da 
razão social, alteração do endereço, alteração da previsão de vendas 
e	 resgate	 dos	 dados	 do	 cliente.	 A	 figura	 2	 ilustra	 uma	 representação	
gráfica	do	TAD	cliente.
Figura 2 – TAD cliente
CNPJ, razão social,
endereço e previsão
de vendas
Criação do registro do cliente
Alteração da razão social
Alteração do endereço
Alteração da previsão de vendas
Resgate dos dados do cliente
Apenas as operações são
acessadas externamente.
A forma como as operações
são implementadas não
precisa ser publicada.
10 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
O cadastro de clientes também pode ser tratado como um TAD, sen-
do o conjunto de registros de clientes os dados e as operações: inserção 
de um novo cliente, busca de um cliente, total de previsão de vendas, 
exclusão	 de	 cliente	 e	 listagem	 dos	 clientes.	 Observe	 que	 o	TAD	 pode	
ser implementado inicialmente com essas operações, mas, ao longo 
do tempo, pode passar a oferecer novas funções, como listagem de um 
conjunto	específico	de	clientes.
Na	definição	de	um	TAD,	não	há	a	preocupação	com	a	alocação	de	
memória ou tempo de resposta, pois um TAD não está associado a um 
paradigma, método ou linguagem de programação, mas, sim, à comuni-
cação	da	abstração	obtida	na	sua	definição	e	no	isolamento	entre	a	defini-
ção e a implementação (TENENBAUM; LANGSAM; AUGENSTEIN, 1995).
2 Exemplos do uso de encapsulamento, 
reúso e alocação dinâmica
A estrutura de dados lista ligada, ou lista encadeada, é um exemplo 
de	TAD	composto	por	elementos	(ou	nós)	encadeados.	A	figura	3	ilustra	
uma	representação	gráfica	de	uma	lista	 ligada	com	os	elementos	E1,	
E2,	E3,	E4	até	En,	sendo	que	um	elemento	precede	o	próximo,	sempre	
que	a	lista	apresenta	dois	ou	mais	elementos	(TENENBAUM;	LANGSAM;	
AUGENSTEIN, 1995). Em uma lista ligada, o primeiro elemento é sempre 
conhecido,	e	o	último	indica	o	final	da	lista.
Figura 3 – Lista ligada ou encadeada
E1 E2 E3 E4 En
A implementação de uma lista ligada pode ser realizada de diversas 
maneiras (vetores, alocação dinâmica e ponteiros) e nas mais variadas 
linguagens de programação, mas o seu conceito como um TAD facilita 
a	sua	definição	e	o	seu	entendimento.	A	lista	ligada	deve	apresentar	um	
conjunto	de	operações	que	permitam	manipular	a	lista	e	seus	dados:
11Tipo abstrato de dados
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
• Inserção de um elemento.
• Remoção de um elemento.
• Busca por um determinado elemento.
• Busca por um elemento em determinada posição.
• Listagem dos elementos.
• Esvaziamento completo da lista.
Em diversos problemas computacionais, os elementos precisam 
ser	 utilizados	 na	 forma	 de	 fila,	 na	 qual	 o	 primeiro	 a	 entrar	 deve	 ser	 o	
primeiro a sair (FIFO – first in, first out) (GOODRICH; TAMASSIA, 2013). 
Como exemplo, podemos citar os trabalhos a serem enviados para 
uma impressora, a automação de sistema de atendimento ao público, 
entre outros.
A	figura	4	ilustra	uma	representação	gráfica	do	TAD	fila,	composto	
pelos elementos E1, E2, E3, E4, E5 até En, com a marcação de onde os 
novos	 elementos	 devem	 ser	 colocados	 na	 fila	 (inserir)	 e	 onde	 os	 ele-
mentos devem ser retirados (remover).
Figura 4 – Representação de uma fila
E1 E2 E3 E4 E5 ....... En
Inserir
En + 1
Remover
IMPORTANTE 
O TAD fila deve apresentar obrigatoriamente as seguintes operações:
• inserção na fila;
• remoção na fila.
12 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
Algumas operações adicionais podem ser suportadas para completar e 
enriquecer o funcionamento do TAD fila (GOODRICH; TAMASSIA, 2013):
• tamanho da fila;
• teste se a fila está vazia;
• retorna o primeiro elemento e não remove da fila.
 
A	tabela	1	apresenta	uma	sequência	de	operações	aplicadas	a	uma	
fila	F	com	valores	inteiros	e	inicialmente	vazia.	Os	resultados	e	o	estado	
da	fila	F	são	exibidos	a	cada	linha	(GOODRICH;	TAMASSIA,	2013).
Tabela 1 – Sequência de operações sobre a fila F
LINHAS OPERAÇÃO SAÍDA FILA F
1 inserir(5) – (5)
2 inserir(3) – (5,3)
3 remover 5 (3)
4 inserir(7) – (3,7)
5 remover 3 (7)
6 primeiro 7 (7)
7 remover 7 ( )
8 remover erro ( )
9 vazia verdade ( )
10 inserir(9) – (9)
11 inserir(7) – (9,7)
12 tamanho 2 (9,7)
13 inserir(3) – (9,7,3)
14 inserir(5) – (9,7,3,5)
15 remover 9 (7,3,5)
Fonte: adaptado de Goodrich e Tamassia (2013).
13Tipo abstrato de dados
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Um outro TAD empregado largamente em computação é a pilha, for-
mada	por	um	conjunto	de	elementos,	no	qual	o	último	elemento	a	en-
trar é o primeiro a sair (LIFO – last in, first out) (GOODRICH; TAMASSIA, 
2013), semelhante a uma pilha de livros em cima de uma mesa. A retira-
da	do	primeiro	livro	é	simples,	tanto	quanto	colocar	mais	um	livro	nesse	
mesmo topo da pilha.
O	TAD	pilha	apresenta	um	comportamento	muito	simplificado	com	
basicamente duas operações representadas pelos termos em inglês 
“push” e “pop”. A estrutura básicaempregada para a lista ligada pode 
ser aplicada para implementar outros tipos de TAD, bastando apenas 
explicitar os operadores e fornecer alguns dados adicionais; no caso da 
pilha, basta incluir a indicação do seu topo coincidindo com o início da 
lista	ligada,	conforme	apresentado	na	figura	5.
Figura 5 – Representação de uma pilha
E1 E2 E3 E4Topo En
O	vetor	é	um	arranjo	de	elementos	organizados	em	sequência,	com	
o	mesmo	nome	e	armazenados	em	memória,	e	contém	um	número	fixo	
de	 elementos,	 sendo	 que	 cada	 elemento	 pode	 ser	 acessado	 pelo	 seu	
índice	(GOODRICH;	TAMASSIA,	2013).	A	figura	6	ilustra	a	representação	
de um vetor de nome “a” com dez posições, contendo os valores inteiros 
-23,	45,	12,	33,	0,	0,	88,	31,	15	e	19,	que	poderiam	ser,	por	exemplo,	dez	
números obtidos por um gerador de números aleatórios entre -100 e 
100.	Perceba	que	o	índice	de	um	vetor	começa	sempre	em	zero.
14 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 Figura 6 – Representação de um vetor com dez posições
a
0 -23
1 45
2 12
3 33
4 0
5 0
6 88
7 31
8 15
9 19
A matriz, ou vetores multidimensionais, tem um comportamento se-
melhante a um vetor, mas com duas ou mais dimensões (GOODRICH; 
TAMASSIA,	2013).	A	figura	7	apresenta	uma	matriz	com	duas	colunas	
e	 quatro	 linhas,	 que	 poderia	 ser	 a	 representação	 de	 uma	 figura	 geo-
métrica	(quadrado)	no	plano	XY.
Figura 7 – Representação de uma matriz bidimensional 2 × 4
q
0 1
0 1.0 1.0
1 5.0 1.0
2 3.0 5.0
3 1.0 3.0
Tanto vetores como matrizes podem ser apresentados como tipos 
abstratos	 de	 dados,	 nos	 quais	 os	 dados	 estariam	 encapsulados	 ou	
agrupados	junto	aos	operadores	que	atuam	na	modificação	desses	da-
dos. As operações poderiam ser simplesmente: adicionar um dado em 
15Tipo abstrato de dados
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
determinada posição, inspecionar um dado em determinada posição e 
listar todos os dados.
Considerações finais
A diversidade de projetos de desenvolvimento de software, associa-
da à crescente exigência de atendimento a restrições de custo, prazo 
e	 qualidade,	 implica	 que	 os	 projetos	 de	 implementação	 de	 software	
devem atender a objetivos associados a robustez, adaptabilidade e 
reusabilidade.
A	 robustez	 em	 um	 processo	 de	 programação	 significa	 produzir	 as	
saídas corretas considerando todo o conjunto possível de entradas pre-
vistas para o sistema. O software desenvolvido deve ser capaz de se 
adaptar	à	evolução	e	à	alteração	do	ambiente	que	o	suporta.	Isso	está	
associado,	 também,	à	portabilidade	desse	software,	de	modo	que	ele	
possa ser executado em diversas plataformas e sistemas operacionais. 
Por	fim,	há	o	requisito	reusabilidade,	no	qual	parte	do	código	desenvolvi-
do para um sistema possa ser utilizada em outros sistemas, diluindo os 
custos de desenvolvimento (GOODRICH; TAMASSIA, 2013). A utilização 
de tipo abstrato de dados como forma de organizar as estruturas de 
dados	é	um	instrumento	eficaz	para	viabilizar	robustez,	adaptabilidade	
e reusabilidade de componentes no processo de programação, além fa-
vorecer	a	comunicação	entre	a	equipe	de	desenvolvimento.
Referências
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013.
OLIVEIRA, Valter Castelhano de. Proposta de método para gestão de 
requisitos de sistemas integrando modelagem de negócio e linguagens 
16 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
formais. Dissertação (Mestrado em Engenharia) – Escola Politécnica da 
Universidade de São Paulo, São Paulo, 2008.
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de dados e seus 
algoritmos. Rio de Janeiro: LTC, 2010.
TENENBAUM,	 Aaron	 M.;	 LANGSAM,	 Yedidyah;	 AUGENSTEIN,	 Moshe	 J.	
Estruturas de dados usando C. São Paulo: Makron Books, 1995.
17 
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Capítulo 2 
Lista ligada 
A representação de um conjunto de dados, por exemplo, um grupo 
de clientes de uma empresa, é uma necessidade comum a diversos sis-
temas de computação. A estrutura básica vetor, por exemplo, pode ser 
utilizada em várias aplicações, entretanto o uso de vetores implica a 
declaração do número máximo de elementos, e isso pode ser um limi-
tador, pois nem sempre o número máximo de elementos do conjunto é 
conhecido, e muitas vezes esse número pode resultar em desperdício 
de recursos, com a alocação desnecessária de memória (GOODRICH; 
TAMASSIA, 2013). 
18 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 
Uma solução seria a utilização de estruturas de dados que possibi-
litam a variação do número de elementos de acordo com a necessida-
de, permitindo aumentar e diminuir o número de elementos conforme 
a necessidade da aplicação e oferecendo alternativas para implemen-
tação computacional de problemas como o cadastro de clientes de 
uma empresa. 
Neste capítulo, abordaremos o conceito de lista ligada, as técnicas 
de implementação utilizando a linguagem Java que viabilizam o fun-
cionamento de listas ligadas e um conjunto de operações sobre esse 
tipo de estrutura de dados. 
1 Conceito de lista ligada 
A lista ligada é uma estrutura de dados composta por um conjun-
to de elementos, denominados “nós”, organizados e encadeados em 
sequência, e que pode ser representado como um tipo abstrato de 
dados (GOODRICH; TAMASSIA, 2013; TENENBAUM; LANGSAM; 
AUGENSTEIN, 1995). 
Ela pode ser aplicada em diversos problemas computacionais, prin-
cipalmente naqueles em que não se sabe o tamanho do conjunto de 
dados. Vamos tomar como exemplo um conjunto de equipamentos au-
tônomos, alimentados por energia solar, que são destinados a coletar a 
umidade do terreno e são instalados em vários pontos de uma fazenda 
no interior do país. O software de controle desse equipamento preci-
sa armazenar as amostragens continuamente até que os dados sejam 
coletados por um funcionário, que circula periodicamente pela fazenda 
com um aparelho coletor de dados. O sistema do equipamento pode ser 
implementado com uma lista ligada para armazenar as diversas amos-
tragens de umidade. 
19 Lista ligada
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
A figura 1 ilustra a representação gráfica de uma lista ligada imple-
mentada como uma sequência de nós encadeados, na qual a variável 
início aponta para o primeironó, e, assim sucessivamente, um nó apon-
ta para o próximo, até que o último nó aponte para um valor nulo, indi-
cando o final da lista. 
Figura 1 – Representação gráfica de uma lista ligada 
Início Nó 1 Nó 2 Nó 3 ... Nó n 
No caso de uma lista ligada vazia, ou seja, que não apresenta ne-
nhum elemento, o início aponta para um valor nulo, conforme apresen-
tado na figura 2. A lista vazia é, geralmente, o estado inicial de criação 
de uma lista ligada, além disso, é um estado a ser testado em diversas 
situações computacionais; por exemplo, ao remover um elemento da 
lista ligada, o estado de lista vazia deve sempre ser testado. 
Figura 2 – Lista ligada vazia 
Início 
O código a seguir implementa a classe No, caracterizada como um 
TAD, contendo os campos elemento e proximo, implementando as ope-
rações necessárias para a manipulação desses nós, incluindo método 
para construção dos objetos “nó”, atribuição dos campos (elemento e 
próximo) e recuperação do objeto atribuído ao campo elemento do nó. 
20 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
// Implementação da classe No 
public class No 
{
 private No proximo; // aponta para o próximo No da Lista
 private Object elemento; // armazena o elemento de cada No
 public No(Object elemento, No proximo) // construtor classe No
 {
 this.elemento = elemento;
 this.proximo = proximo;
 } 
public void setProximo(No proximo) // método que altera próximo No da Lista
 {
 this.proximo = proximo;
 } 
public No getProximo() // método que recebe o próximo No da Lista
 {
 return proximo;
 }
 public void setElemento(Object elemento) // método para alterar o elemento
 {
 this.elemento = elemento;
 }
 public Object getElemento() // método para receber o objeto contido no No
 {
 return elemento;
 } 
} 
// Final da classe No 
Cabe observar que a variável elemento de cada nó é um objeto gené-
rico (tipo Object de Java) que pode armazenar qualquer tipo de objeto, 
inclusive os associados a um cadastro de clientes. O trecho de código 
Java a seguir apresenta a classe Lista, que representa uma primeira ver-
são do TAD lista ligada: 
21 Lista ligada
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 
 
// Implementação da classe Lista 
public class Lista 
{
 private No inicio; 
public Lista() // construtor da classe Lista inicializada vazia
 {
 this.inicio = null;
 } 
} 
// Final da classe Lista 
A implementação do TAD lista ligada ainda deve apresentar um con-
junto de operações que viabilizam a manipulação da classe Lista e que 
serão implementadas na próxima seção deste capítulo: 
• Inserção de um elemento no início da Lista. 
• Remoção de um elemento no início da Lista. 
• Busca por um determinado elemento da Lista. 
• Busca por um elemento em determinada posição da Lista. 
• Listagem de todos os elementos da Lista. 
• Esvaziamento completo da Lista. 
Por exemplo, no tratamento do cadastro de uma lista de clientes, 
cada nó pode conter os dados de cliente, e a lista ligada deve armazenar 
o conjunto de dados dos clientes da empresa. O código em linguagem 
Java a seguir apresenta a implementação da classe Cliente contendo os 
atributos (razão social, endereço e previsão de vendas), o construtor da 
classe e os métodos para operação dos atributos (atualiza a previsão de 
vendas e mudança de endereço). 
22 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
// Implementação da classe Cliente 
public class Cliente 
{
 private long codigo;
 private String razaoSocial;
 private String endereco;
 private double previsaoVendas; 
public Cliente(long c, String r, String e, double p) // construtor classe Cliente
 {
 codigo = c;
 razaoSocial = r;
 endereco = e;
 previsaoVendas = p;
 }
 public String toString()
 {
 return ″Codigo: ″+codigo+″ Razão Social: ″+razaoSocial;
 }
 public void atualizaRazaoSocial(String r)
 {
 razaoSocial = r;
 }
 public void atualizaPrevisao(double p )
 {
 previsaoVendas = p;
 }
 public void mudaEndereco (String e )
 {
 endereco = e;
 } 
} 
// Final da classe Cliente 
Observe que “no Java, a hierarquia de classes inicia com a classe 
Object” (DEITEL; DEITEL, 2010, p. 284), ou seja, um objeto instanciado da 
classe No poderá conter no atributo elemento a classe Cliente. Na próxi-
ma seção, serão abordadas as operações oferecidas pela lista ligada e 
a utilização da classe cliente como elemento do nó da lista. 
23 Lista ligada
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
2 Operações de adição e remoção de nós 
O modo mais simples de adição de elementos em uma lista liga-
da é a inserção de um novo elemento no início da lista (GOODRICH; 
TAMASSIA, 2013). A figura 3 apresenta os passos para realizar esse 
procedimento, sendo que, nessa operação, basta criar um novo nó 
(passo 1) com o elemento desejado, atribuir ao atributo próximo o início 
atual da lista (passo 2) e, em seguida, atribuir ao início da lista o novo nó 
criado (passo 3) (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). 
Figura 3 – Inserção de elemento no início da lista ligada 
 Inserção de novo nó Início Nó 1 ...Nó 2 Nó n 
Passo 1: Novo nó criado Novo 
Passo 2: Ligar novo nó à lista Início Nó 1 ...Nó 2 Nó n 
Passo 3: Início ligado ao novo nó Início Novo Nó 1 ...Nó 2 Nó n 
A implementação da operação de inserção no início da lista ligada 
também é simples e apresentada na nova versão da classe Lista a se-
guir. Cabe observar, no código, os comentários relacionando as linhas 
de comando com os passos descritos na figura 3. 
// Implementação da classe Lista com o método para inserção no início 
public class Lista 
{
 private No inicio;
 public Lista() // construtor da classe Lista inicializada vazia 
24 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 {
 this.inicio = null;
 }
 public void insereInicio(Object elemento)
 {
 No novoNo = new No(elemento, null); // passo 1 da figura 3
 novoNo.setProximo(this.inicio); // passo 2 da figura 3
 this.inicio = novoNo; // passo 3 da figura 3
 } 
} 
// Final da classe Lista 
A remoção de elementos no início de uma lista ligada também 
é o modo mais simples de implementação desse tipo de operação 
(GOODRICH; TAMASSIA, 2013). Os passos para realizar a operação 
de remoção no início da lista ligada são apresentados na figura 4. O 
passo 1 é fazer uma cópia do início da lista. Em seguida, no passo 2, 
o início passa a ser ligado ao próximo elemento da lista. Por fim, no 
passo 3, o elemento a ser removido é liberado. Cabe ressaltar que esses 
passos só podemser utilizados se a lista ligada apresentar pelo menos 
um elemento, ou seja, não for uma lista ligada vazia. 
Figura 4 – Remoção de elemento no início da lista ligada 
 Remoção de nó inicial 
Passo 1: 
Variável auxiliar copia início Início ... Nó n 
Auxiliar 
Passo 2: 
Início ligado ao próximo nó ... Nó n 
Auxiliar 
Nó 1 Nó 2 
Nó 1 Nó 2 
Início 
Passo 3: 
O nó ligado a auxiliar é liberado Início Nó 2 ... Nó n 
Auxiliar 
25 Lista ligada
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
Semelhante à implementação da operação de inserção no início da 
lista ligada, o método para remoção de um nó do início também é bas-
tante simples e está representado em uma nova versão da classe Lista. 
Os comentários no código nas linhas de comando estão relacionados 
com os passos descritos na figura 4. 
// Implementação da classe Lista com os métodos inserção e remoção no início 
public class Lista 
{
 private No inicio;
 public Lista() // construtor da classe Lista inicializada vazia
 {
 this.inicio = null;
 }
 public void insereInicio(Object elemento)
 {
 No novoNo = new No(elemento, null); // passo 1 da figura 3
 novoNo.setProximo(this.inicio); // passo 2 da figura 3
 this.inicio = novoNo; // passo 3 da figura 3
 }
 public Object removeInicio()
 {
 No auxiliar = this.inicio; // passo 1 da figura 4
 this.inicio = auxiliar.getProximo(); // passo 2 da figura 4
 return auxiliar.getElemento(); // passo 3 da figura 4
 } 
} 
// Final da classe Lista 
Tomando como referência a versão anterior da classe Lista, o códi-
go a seguir apresenta a classe CadastroCliente, que exemplifica como 
cadastros de clientes são inseridos e removidos da lista ligada e, tam-
bém, o pleno funcionamento de um tipo abstrato de dados, no qual os 
dados estão encapsulados e são acessados apenas pelas operações 
disponibilizadas. 
26 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 
// Exemplo de inserção e remoção de cadastros de clientes 
public class CadastroCliente 
{
 public static void main(String[] args)
 { 
Lista listaClientes = new Lista(); // cria a lista de clientes
 Cliente c = new Cliente(221,″Produtos excelentes LTDA″,
 ″Rua sem fim, 200″,
 5000.0);
 // inserindo elementos na Lista Ligada
 listaClientes.insereInicio(c); // usando uma variável cliente
 listaClientes.insereInicio(new Cliente(185,″Negócios Importantes SA″,
 ″Avenida Principal, 10″,
 12000.0));
 listaClientes.insereInicio(new Cliente(443,″Parceiros Críticos LTDA″,
 ″Rua dos negócios, 2000″,
 7000.0));
 // removendo um elemento da Lista Ligada
 // necessário type casting para a classe Cliente
 Cliente clienteRemovido = (Cliente) listaClientes.removeInicio();
 System.out.println(clienteRemovido);
 } 
} 
// final da classe CadastroCliente 
As operações de inserção e remoção implementadas são essenciais 
para o funcionamento de uma lista ligada. Uma operação adicional in-
teressante de ser implementada é a operação de listagem de toda a 
lista ligada. O trecho de código em Java a seguir apresenta o método 
imprimeLista, que será incorporado à classe Lista.
 public void imprimeLista() // método para imprimir todo o conteúdo da lista
 {
 No auxiliar = this.inicio; //auxiliar percorre a lista do início ao fim
 System.out.println(″Inicio da Lista Ligada″);
 while (auxiliar != null) // testa se ainda não chegou no final da lista 
27Lista ligada
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 { 
System.out.println(auxiliar.getElemento()); // imprime com o método toString
 auxiliar = auxiliar.getProximo(); // passa para o próximo Nó da lista
 }
 System.out.println(″Final da Lista Ligada″);
 } 
Cabe observar que o método imprimeLista apresenta uma estrutura 
de programação que percorre toda a lista utilizando a variável auxiliar, 
que recebe o início da lista. Enquanto essa variável auxiliar não chegar 
ao final da lista (auxiliar for diferente de null), o elemento do nó é im-
presso e a variável auxiliar recebe o próximo nó da lista (GOODRICH; 
TAMASSIA, 2013; LAFORE, 2004). 
O algoritmo para percorrer uma lista ligada pode ser aplicado em 
diversas operações, por exemplo, a busca de um elemento na lista ou 
para esvaziar totalmente a lista eliminando todos os nós que a com-
põem. A última versão da classe Lista apresenta métodos adicionais 
(buscaElemento e liberaLista, respectivamente), que desempenham es-
sas novas operações, e incorpora também o método imprimeLista. 
// Implementação da classe Lista com os métodos inserção e remoção no início 
public class Lista 
{
 private No inicio; 
public Lista() // construtor da classe Lista inicializada vazia
 {
 this.inicio = null;
 }
 public void insereInicio(Object elemento)
 {
 No novoNo = new No(elemento, null); // passo 1 da figura 3
 novoNo.setProximo(this.inicio); // passo 2 da figura 3
 this.inicio = novoNo; // passo 3 da figura 3 
28 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 }
 public Object removeInicio()
 {
 No auxiliar = this.inicio; // passo 1 da figura 4
 this.inicio = auxiliar.getProximo(); // passo 2 da figura 4
 return auxiliar.getElemento(); // passo 3 da figura 4
 }
 public void imprimeLista() // método para imprimir todo o conteúdo da lista
 {
 No auxiliar = this.inicio; //auxiliar percorre a lista do início ao fim
 System.out.println(″Inicio da Lista Ligada″);
 while (auxiliar != null) // testa se ainda não chegou no final da lista
 {
 System.out.println(auxiliar.getElemento()); //imprime com o método toString
 auxiliar = auxiliar.getProximo(); // passa para o próximo Nó da lista
 }
 System.out.println(″Final da Lista Ligada″);
 } 
public Object buscaElemento(long posicao) // busca o elemento na posição da lista
 {
 No auxiliar= this.inicio;
 while ((posicao > 0) && (auxiliar != null))
 {
 if (posicao == 1)
 return auxiliar.getElemento();
 posicao--;
 auxiliar = auxiliar.getProximo(); // passa para o próximo Nó da lista
 }
 return null; // a lista não possui elemento na posição indicada
 }
 public void liberaLista() // libera todos os nós da lista
 {
 while (inicio != null)
 {
 inicio = inicio.getProximo();
 // o garbage collector de Java libera automaticamente o nó eliminado
 }
 } 
} 
// Final da classe Lista 
29 Lista ligada
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 
 
 
 
 
 
 
Por fim, utilizando essa última versão da classe Lista, o código a se-
guir exemplifica a utilização das operações oferecidas pelo TAD lista. 
// Exemplo de inserção e remoção de cadastros de clientes 
public class CadastroCliente 
{
 public static void main(String[] args){
 Lista listaClientes = new Lista(); // cria a lista de clientes
 listaClientes.imprimeLista();
 Cliente c = new Cliente(221,″Produtos excelentes LTDA″,
 ″Rua sem fim, 200″,
 5000.0); 
// inserindo elementos na Lista Ligada
 listaClientes.insereInicio(c); // usando uma variável cliente
 listaClientes.imprimeLista();
 listaClientes.insereInicio(new Cliente(185,″Negócios Importantes SA″,
 ″Avenida Principal, 10″,
 12000.0));
 listaClientes.imprimeLista();
 listaClientes.insereInicio(new Cliente(443,″Parceiros Críticos LTDA″,
 ″Rua dos negócios, 2000″,
 7000.0));
 listaClientes.imprimeLista();
 // busca do elemento na posição 2 da lista
 c = (Cliente) listaClientes.buscaElemento(2);
 if (c != null)
 {
 System.out.println(″Elemento da posicao 2 da Lista Ligada″);
 System.out.println(c);
 }
 // removendo um elemento da Lista Ligada
 // necessário type casting para a classe Cliente
 Cliente clienteRemovido = (Cliente) listaClientes.removeInicio();
 System.out.println(″Elemento removido da Lista Ligada″);
 System.out.println(c);
 listaClientes.imprimeLista();
 // liberando toda a lista
 System.out.println(″Liberando toda a lista″); 
30 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 listaClientes.liberaLista();
 listaClientes.imprimeLista();
 } 
} 
// final da classe CadastroCliente 
Considerações finais 
Neste capítulo, foram apresentados os conceitos associados a listas 
ligadas e como implementar esses tipos abstratos de dados. As opera-
ções de inserção, remoção, busca, listagem e liberação de elementos da 
lista foram exemplificadas em aplicações e explicadas passo a passo, 
para um completo entendimento dos algoritmos de implementação. 
Cabe ressaltar que os conceitos associados a alocação de dinâmica, 
encapsulamento, tratamento de ponteiros e diversas estruturas básicas 
de programação foram apresentados visando oferecer recursos de pro-
gramação fundamentais para o desenvolvimento de sistemas compu-
tacionais e fornecer insumos para os estudos abordados nos demais 
capítulos deste livro. 
PARA SABER MAIS 
Existem variações de implementação e operações sobre listas ligadas, 
por exemplo, listas duplamente encadeadas, listas circulares, listas or-
denadas, listas de prioridades e coleções, que podem ser estudadas em 
nas obras de Deitel e Deitel (2010), Goodrich e Tamassia (2013), Lafore 
(2004) e Szwarcfiter e Markenzon (2010). 
 
31 Lista ligada
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Referências 
DEITEL, Paul J. Y.; DEITEL, Harvey M. Como programar Java. 10. ed. São Paulo: 
Pearson, 2010. 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013. 
LAFORE, Robert. Estrutura de dados e algoritmos em Java. Rio de Janeiro: 
Ciência Moderna, 2004. 
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de dados e seus 
algoritmos. Rio de Janeiro: LTC, 2010. 
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. 
Estruturas de dados usando C. São Paulo: Makron Books, 1995. 
33
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Capítulo 3
Árvores binárias
As estruturas de dados vetores, listas, pilhas e filas têm em comum 
a organização sequencial dos dados e oferecem recursos para a so-
lução de um grande conjunto de implementações computacionais. 
Entretanto, vários problemas requerem soluções não sequenciais, por 
exemplo: uma lista de itens de montagem de um equipamento, na qual 
cada parte do equipamento possui um conjunto de peças e determina-
das peças também podem ser representadas por um novo conjunto de 
peças; um diretório de arquivos de computador, com suas pastas e ar-
quivos; a estrutura de um site na web, com diversas opções oferecidas 
ao usuário (GOODRICH; TAMASSIA, 2013).
34 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
A estrutura de dados organizada no conceito de árvore é uma ruptu-
ra na organização linear dos dados, já apresentada anteriormente nas 
listas, na qual os dados são organizados de forma hierárquica, e viabi-
liza a implementação de algoritmos mais simples, rápidos e eficientes 
(SZWARCFITER; MARKENZON, 2010).
Neste capítulo, será abordado o conceito de árvore, bem como a ela-
boração de uma árvore binária e as técnicas de varredura com algorit-
mos recursivos.
1 Conceito de árvore em computação
A estrutura de dados árvore é um TAD no qual os dados são organi-
zados de forma hierárquica. Os elementos de uma árvore são denomi-
nados “nós”, sendo que cada nó possui um nó pai e zero ou mais nós 
filhos. O nó do topo da árvore é denominado “raiz”, ocupa a posição 
mais elevada da árvore e não possui um nó pai (GOODRICH; TAMASSIA, 
2013). A estrutura hierárquica de arquivos e pastas utilizada para arma-
zenar documentos em um computador é um bom exemplo de aplicação 
de árvore, conforme apresentado na figura 1.
Figura 1 – Organização hierárquica de pastas ou diretórios em um computador
Disco local (C):
35Árvores binárias
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Na representação gráfica de uma árvore, os nós geralmente são re-
tângulos (ou elipses) e estão interligados por retas. De modo diferente 
do que foi apresentado na figura 1, tradicionalmente uma árvore em 
computação é desenhada com a raiz para cima e os demais nós para 
baixo, como na figura 2.
Figura 2 – Representação típica de uma árvore
Nó 1
Nó 2
Nó 6 Nó 7 Nó 8 Nó 9
Nó 12 Nó 13
Nó 10 Nó 11
Nó 3 Nó 4 Nó 5
Na figura 2, o nó 1 é a raiz da árvore, pois não possui pai e está no 
nível mais alto. Todos os nós filhos de um mesmo pai são irmãos; por 
exemplo, os nós 7, 8 e 9 são irmãos, já que são filhos de um mesmo pai, 
no caso o nó 3. Um nó é interno à árvore se tem um ou mais filhos (por 
exemplo, os nós 2, 3, 5 e 9), e os nós que não têm filhos são denomi-
nados “externos” ou “folhas” (por exemplo, os nós 4, 6, 7, 8, 10, 11, 12 e 
13). Dois nós relacionados como pai e filho pertencentes a uma árvore 
determinam uma aresta (por exemplo, os nós 3 e 7 ou os nós 9 e 13). 
Um caminho em uma árvore é uma sequência de nós na qual quaisquer 
dois nós formam uma aresta (por exemplo, a sequência dos nós 1, 3, 
9 e 12 forma um caminho). Quando existe uma ordem entre os filhos 
dos nós de uma árvore, esta é denominada “ordenada” (por exemplo, 
a árvore da figura 2 pode ser considerada ordenada de acordo com a 
numeração dos nós) (GOODRICH; TAMASSIA, 2013).
Uma árvore pode ser representada como um TAD que armazena 
elementos ou dados em cada um de seus nós e algumas operações 
36 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
ação
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
importantes para a manipulação e o acesso a esses elementos, como 
as descritas a seguir (GOODRICH; TAMASSIA, 2013):
• Operação raiz: retorna a raiz da árvore. No caso de uma árvore 
vazia, retornará o valor nulo.
• Operação pai de um nó: retorna o pai desse nó. Se o nó for a raiz, 
resultará em erro.
• Operação filhos de um nó: retorna um conjunto de nós formado 
por todos os filhos desse nó.
• Operação para teste se um nó é folha: verifica se o nó é uma 
folha, ou seja, não tem filhos.
• Operação para teste se um nó é interno: verifica se o nó é interno 
à árvore, ou seja, se possui filhos.
• Operação tamanho: retorna o número de nós da árvore.
• Operação para teste se é vazio: verifica se uma árvore está vazia, 
ou seja, não tem nós.
A quantidade de filhos ligados a cada nó pai e, também, o tipo de 
dado armazenado em cada um dos nós propiciam a classificação de 
diversos tipos de árvores; entre elas, a mais significativa para as apli-
cações computacionais é a árvore binária, que permite um máximo de 
dois filhos para cada nó e é implementada com algoritmos recursivos 
muito compactos e simples para a sua manipulação (TENENBAUM; 
LANGSAM; AUGENSTEIN, 1995).
2 Elaboração de uma árvore binária
Uma árvore binária apresenta as seguintes características 
(GOODRICH; TAMASSIA, 2013):
• Deve ser ordenada; os filhos de um nó devem estar ordenados da 
esquerda para a direita.
37Árvores binárias
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
• Cada nó tem no máximo dois filhos, ou seja, zero, um ou dois filhos.
• Cada um dos filhos é rotulado como filho da direita ou filho da 
esquerda.
A figura 3 ilustra uma representação gráfica de uma árvore binária. 
Perceba que todo nó tem no máximo dois filhos e que os filhos estão 
sempre ordenados.
Figura 3 – Árvore binária
A
CB
D E
G H
F
O código em linguagem Java a seguir implementa a classe No, tam-
bém caracterizada como um TAD, contendo os campos de identifica-
ção do nó, o elemento armazenado e as ligações para os filhos es-
querdo e direito. A classe No implementa os métodos para construção 
dos objetos No e métodos para atribuição e recuperação de todos os 
campos da classe.
// Implementação da classe No de uma árvore
public class No
{
 private long id; // identificador do elemento
 private Object elemento; // armazena o elemento de cada No
 private No esq; // aponta para o filho esquerdo do nó
38 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 private No dir; // aponta para o filho direito do nó
 public No(long id, Object elemento, No esq, No dir) // construtor classe No
 {
 this.id = id;
 this.elemento = elemento;
 this.esq = esq;
 this.dir = dir;
 }
 public void setId(long id) // método para alterar o identificador do nó
 {
 this.id = id;
 }
 public long getId() // método para receber o identificador do nó
 {
 return this.id;
}
 public void setElemento(Object elemento) // método para alterar o elemento
 {
 this.elemento = elemento;
 }
 public Object getElemento() // método para receber o objeto contido no No
 {
 return elemento;
 }
 public void setEsq(No esq) // método que altera o filho esquerdo
 {
 this.esq = esq;
 }
 public No getEsq() // método que recebe o filho esquerdo do nó
{
 return esq;
}
 public void setDir(No dir) // método que altera o filho direito
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
39Árvores binárias
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
{
 this.dir = dir;
 }
 public No getDir() // método que recebe o filho direito do nó
 {
 return dir;
 }
}
// Final da classe No
Cabe observar que a variável elemento de cada nó é um objeto gené-
rico (tipo Object de Java) que pode armazenar qualquer tipo de objeto, 
desde objetos simples, como números e nomes, até objetos complexos 
com diversos campos, como o cadastro de clientes de uma empresa.
A inserção de nós em uma árvore binária deve atender a caracterís-
ticas de ordenação dos filhos. O código em Java a seguir implementa a 
classe ArvoreBinaria com o construtor e o método para inserir um novo 
elemento na árvore.
// Implementação da classe árvore binária, com construtor e o método insere()
public class ArvoreBinaria
{
 private No raiz;
 public ArvoreBinaria() // construtor da classe Arvore Binaria
 {
 this.raiz = null; // inicia a árvore vazia
 }
 public void insere(long id, Object elemento) // método para inserção de elemento
 {
 No novoNo = new No(id,elemento,null,null);
 if (raiz == null) {
raiz = novoNo;
40 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 } else {
 No atual = raiz;
 No pai;
 while (true) {
 pai = atual;
 if (id < atual.getId()) { // vai inserir à esquerda
 atual = atual.getEsq();
 if (atual == null) { // pode inserir à esquerda
 pai.setEsq(novoNo);
 return;
 } // se não é nulo, vai tentar o próximo filho
 } else { // vai inserir à direita 
 atual = atual.getDir();
 if (atual == null) { // pode inserir à direita
 pai.setDir(novoNo);
 return;
 }
 }
 }
 }
 } // final método insere
} // Final da classe ArvoreBinaria
Neste código, se a árvore for vazia, ou seja, a raiz for nula, o novo 
elemento é inserido diretamente na raiz. Caso contrário, o método cria 
uma variável atual (inicializada com a raiz da árvore), que será utilizada 
para percorrer os caminhos da árvore até encontrar a posição correta 
para o novo elemento. A garantia da ordenação da árvore é obtida com a 
comparação entre o identificador do novo elemento e o identificador do 
nó atual, tentando realizar a inserção à esquerda ou à direita, conforme 
o resultado da comparação. Se o filho do nó atual for nulo, então o novo 
nó é inserido e o método é terminado; caso contrário, uma nova iteração 
começa com o nó atual percorrendo a árvore.
O código em Java a seguir utiliza a classe ArvoreBinaria para criar a 
árvore da figura 3.
41Árvores binárias
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
public class ExemploArvoreBinaria // Exemplo de criação de uma árvore binária
{
 public static void main(String[] args)
 {
 ArvoreBinaria a = new ArvoreBinaria(); // cria a árvore binária
 a.insere(10,″A″);
 a.insere(5,″B″);
 a.insere(15,″C″);
 a.insere(2,″D″);a.insere(7,″E″);
 a.insere(12,″F″);
 a.insere(6,″G″);
 a.insere(8,″H″);
 }
} // final do exemplo de criação de uma árvore binária
Perceba que os identificadores utilizados para inserir os nós garan-
tem a construção da árvore binária ordenada exatamente igual à árvore 
da figura 3.
3 Técnicas de varredura, altura e profundidade
A profundidade de um determinado nó em uma árvore é o número 
de ancestrais que esse nó possui. Por exemplo, na árvore binária da 
figura 3, o nó E tem dois ancestrais, os nós B e A; sendo assim, a profun-
didade de E é igual a dois. O cálculo da profundidade de um nó qualquer 
da árvore pode ser obtido com algoritmos específicos de varredura dos 
nós da árvore.
A altura de uma árvore é representada pelo número de níveis da ár-
vore. Uma árvore vazia apresenta altura igual a zero. Em uma árvore 
com apenas a raiz, a altura é 1. De modo geral, a altura de uma árvore 
é a maior profundidade calculada para todas as folhas (nós externos) 
da árvore. Tomando novamente como exemplo a figura 3, a árvore tem 
altura igual a 4. Assim como para a profundidade de um nó, o cálculo 
42 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
da altura de uma árvore pode ser obtido com algoritmos específicos de 
varredura ou caminhamento.
A forma sistemática de acessar todos os nós de uma árvore é de-
nominada “caminhamento” (GOODRICH; TAMASSIA, 2013). O caminha-
mento de uma árvore é realizado por algoritmos de varredura da árvore, 
nos quais as ligações entre os nós são utilizadas para percorrer um de-
terminado conjunto de nós.
A inspeção sistemática de todos os elementos de uma árvore pode 
ser realizada de duas maneiras básicas: caminhamento pré-fixado e ca-
minhamento pós-fixado (GOODRICH; TAMASSIA, 2013).
No caminhamento pré-fixado, primeiramente, a raiz da árvore é visi-
tada para a realização da inspeção, e, depois, as subárvores, representa-
das pelos filhos, são percorridas recursivamente. O caminhamento pré-
-fixado da árvore representada na figura 4 resulta na seguinte sequência 
de elementos: A, B, D, E, G, H, C e F.
Figura 4 – Caminhamento pré-fixado
A
CB
D E
G H
F
1
7
83 4
5 6
2
No caminhamento pós-fixado, ocorre o oposto ao caminhamento pré-
-fixado. Primeiramente, são percorridas as subárvores recursivamente, 
43Árvores binárias
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
e, depois, é inspecionada a raiz. O caminhamento pós-fixado da árvore 
representada na figura 5 resulta na seguinte sequência de elementos: D, 
G, H, E, B, F, C e A.
Figura 5 – Caminhamento pós-fixado
A
CB
D E
G H
F
5
1
2
7
6
8
4
3
Os algoritmos para implementação dessas operações do TAD árvore 
binária serão tratados na próxima seção.
4 Implementando árvore com recursividade
A repetição de instruções pode ser obtida utilizando os comandos 
de iteração for e while, disponíveis em diversas linguagens de progra-
mação, inclusive em Java. Entretanto, as repetições em algumas aplica-
ções podem ser implementas por meio da recursão, na qual uma função 
realiza a chamada a si mesma recursivamente até que seja detectada 
uma condição de parada (GOODRICH; TAMASSIA, 2013).
As operações de cálculo de altura de árvore, bem como as operações 
caminhamento pré-fixado e pós-fixado, são operações adequadas para 
a implementação baseada em recursividade (DEITEL; DEITEL, 2010).
As implementações dos caminhamentos pré-fixado e pós-fixado, 
quando realizadas recursivamente, são muito semelhantes e simples. 
44 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
O código a seguir apresenta a implementação em linguagem Java dos 
métodos preFixado e posFixado.
 private void preFixado(No atual) // caminhamento pré-fixado da árvore binária
 {
 if (atual != null) {
 System.out.println(″Id: ″+atual.getId()+″ Elemento: ″+atual.getElemento());
 preFixado(atual.getEsq());
 preFixado(atual.getDir());
 }
 } // final método preFixado
 
 private void posFixado(No atual) // caminhamento pós-fixado da árvore binária
 {
 if (atual != null) {
 posFixado(atual.getEsq());
 posFixado(atual.getDir());
 System.out.println(″Id: ″+atual.getId()+″ Elemento: ″+atual.getElemento());
 }
 } // final método posFixado
O critério de parada em ambos os métodos é a condição de árvore 
vazia, pois, nesse caso, não temos mais nós a serem varridos. A recur-
sividade ocorre na chamada do caminhamento a cada um dos filhos de 
cada um dos nós, alterando apenas a ordem na qual o elemento do nó 
é exibido.
No caso de árvores binárias, o caminhamento simétrico pode ser 
implementado. Nesse caso, primeiramente, é visitada a subárvore es-
querda, depois a raiz e, por fim, a subárvore direita. O código a seguir 
apresenta a implementação em linguagem do método simFixado.
45Árvores binárias
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 private void simFixado(No atual) // caminhamento simétrico fixado da árvore binária
 {
 if (atual != null) {
 simFixado(atual.getEsq());
 System.out.println(″Id: ″+atual.getId()+″ Elemento: ″+atual.getElemento());
 simFixado(atual.getDir());
 }
 } // final método inFixado
A exibição de uma árvore é um método oferecido pelo TAD ár-
vore binária, que simplesmente realiza a chamada de um dos mé-
todos de caminhamento. O código a seguir apresenta o método 
imprimeElementosArvore utilizando o método pré-fixado.
 public void imprimeElementosArvore() // impressão dos elementos da árvore
 {
 preFixado(raiz);
 } // final do método para impressão
O próximo código apresenta o método recursivo calcAltura, que rea-
liza o cálculo da altura de uma árvore binária.
 private long calcAltura(No atual, long a) // calcula a altura da árvore
 {
 if (atual != null) {
 long e,d;
 e = calcAltura(atual.getEsq(),a)+1;
 d = calcAltura(atual.getDir(),a)+1;
 if (e > d) {
 return a+e;
46 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 } else {
 return a+d;
 }
 }
 return a;
 } // final método calcAltura
 
 public long alturaArvore()
 {
 long a = 0;
 return calcAltura(raiz,a);
 } // final do método alturaArvore
Uma árvore binária vazia possui altura igual a zero, e essa caracterís-
tica que é utilizada como critério de parada da recursividade. A recursi-
vidade ocorre até que o critério de parada seja encontrado, ou seja, uma 
árvore (ou uma subárvore) vazia seja recebida. Nesse caso, o método 
retorna o valor acumulado. Caso a árvore (ou subárvore) recebidanão 
seja nula, as alturas das subárvores esquerda e direita são calculadas 
(chamadas recursivas de calcAltura), e o maior valor entre os dois é 
acrescido ao cálculo da altura da árvore, e esse resultado é retornado.
Por fim, o código a seguir apresenta um exemplo de programa em 
Java que cria a árvore binária da figura 3 e exibe os elementos da árvore 
utilizando o caminhamento pré-fixado.
public class ExemploArvoreBinaria // Exemplo de criação de uma árvore binária
{
 public static void main(String[] args)
 {
 ArvoreBinaria a = new ArvoreBinaria(); // cria a árvore binária
 a.insere(10,″A″);
 a.insere(5,″B″);
47Árvores binárias
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 a.insere(15,″C″);
 a.insere(2,″D″);
 a.insere(7,″E″);
 a.insere(12,″F″);
 a.insere(6,″G″);
 a.insere(8,″H″);
 
 a.imprimeElementosArvore();
 System.out.println(″Altura: ″+a.alturaArvore());
 }
} // final do exemplo de criação de uma árvore binária
O resultado na tela após a execução do programa é o seguinte:
Id: 2 Elemento: D
Id: 5 Elemento: B
Id: 6 Elemento: G
Id: 7 Elemento: E
Id: 8 Elemento: H
Id: 10 Elemento: A
Id: 12 Elemento: F
Id: 15 Elemento: C
Altura: 4
Considerações finais
As estruturas de dados baseadas em árvores são utilizadas em larga 
escala na computação, desde problemas de busca de dados em con-
juntos, passando por análise gramatical, até inteligência artificial, além 
de estimularem técnicas de programação e exemplos de algoritmos im-
portantes para a formação de programadores.
Neste capítulo, foram apresentados os conceitos associados a ár-
vore em computação, como deve ser elaborada uma árvore binária, 
48 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
técnicas de varredura e cálculos de altura e profundidade de árvores, 
bem como a implementação em linguagem Java e utilizando recursivi-
dade das principais operações associadas ao TAD árvore binária.
Referências
DEITEL, Paul J. Y.; DEITEL, Harvey M. Como programar Java. 10. ed. São Paulo: 
Pearson, 2010.
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013.
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de dados e seus 
algoritmos. Rio de Janeiro: LTC, 2010.
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. 
Estruturas de dados usando C. São Paulo: Makron Books, 1995.
49 
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
Capítulo 4 
Balanceamento 
de árvores 
A utilização de estruturas de dados baseadas em alocação dinâmica 
sem predefinição do tamanho do conjunto é interessante para diversos 
tipos de aplicação. Entretanto, as estruturas lineares, como as listas li-
gadas, apresentam limitações devido ao acesso ser sempre realizado 
de forma sequencial, podendo demandar longos processamentos, prin-
cipalmente para buscas (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). 
50 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
Neste capítulo, serão abordados os conceitos de árvore binária de 
busca (ABB) e das técnicas de balanceamento no processo de manu-
tenção desse tipo de árvore, com o objetivo de avaliar a utilização de 
estruturas hierárquicas, não lineares, como alternativa para a alocação 
dinâmica baseada em estruturas lineares. 
1 Entendimento sobre a árvore binária de 
busca (ABB) 
Estruturas lineares baseadas em alocação dinâmica podem e devem 
ser aplicadas a diversos tipos de problemas. Entretanto, sofrem com li-
mitações de desempenho no processo de busca de dados, pois exigem 
acesso sequencial aos elementos. 
Uma simples divisão da lista em duas partes, uma com valores me-
nores que um determinado elemento K e outra com valores maiores 
que K, pode melhorar a performance de busca aos dados do conjunto, 
conforme apresentado na figura 1. 
Figura 1 – Divisão da lista linear em duas metades 
Início 
Elementos menores que K 
Elementos maiores que K 
K 
O aprimoramento dessa ideia pode resultar em uma proposta mais 
robusta, ou seja, generalizar a proposta de separação em duas metades 
para todos os elementos do conjunto, consistindo em sempre dividir 
51 Balanceamento de árvores
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
recursivamente a lista em dois lados, resultando em uma árvore binária 
sempre com os filhos menores que o pai de um lado e os filhos maiores 
do outro lado, conforme apresentado na figura 2. 
Figura 2 – Generalização da divisão da lista 
> 
> 
K 
< 
Início 
> 
< 
< 
 
 
A árvore binária de busca é uma estrutura de dados não linear que 
visa à melhoria na eficiência do processo de acesso aos dados ar-
mazenados, na qual os elementos seguem a seguinte organização 
(GOODRICH; TAMASSIA, 2013): 
• Todos os elementos da subárvore esquerda de um nó são sempre 
menores que o valor armazenado nesse nó. 
• Todos os elementos da subárvore direita de um nó são sempre 
maiores que o valor armazenado nesse nó. 
A figura 3 apresenta um exemplo de uma árvore binária de busca 
com valores inteiros, representando a inserção do conjunto de dados 
88, 70, 75, 99, 110, 105, 119, 80, 67, 59, 72, 91, 90, 95 e 69. 
52 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
Figura 3 – Exemplo de árvore binária de busca 
Raiz 
88 
70 
67 75 
69 72 8059 
99 
91 110 
9590 119105 
A estrutura de dados árvore binária de busca é um tipo abstrato de 
dados que oferece os seguintes operadores: inserção de um novo ele-
mento, impressão dos elementos da árvore, busca de um determinado 
elemento e remoção de elementos (LAFORE, 2004). 
A inserção de um novo elemento em uma ABB consiste em percor-
rer a árvore a partir da raiz, comparando o novo elemento sempre com 
o nó acessado. Se o novo elemento for menor que o nó acessado, a 
operação é repetida recursivamente na subárvore esquerda. Se o novo 
elemento for maior que o nó acessado, a operação é repetida recursiva-
mente na subárvore direita. O algoritmo termina quando for encontrado 
um elemento igual, dispensando, assim, a inserção, ou quando a subár-
vore pesquisada for nula. Nesse caso, o novo elemento é inserido no 
local da subárvore nula (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). 
Observe que a inserção de um novo elemento em uma ABB ocorre 
sempre como uma nova folha da árvore (GOODRICH; TAMASSIA, 2013). 
O código em linguagem Java apresentadoa seguir implementa o 
método público insereABB(), que insere o novo elemento diretamente 
na raiz se a árvore for vazia; caso contrário, realiza a chamada ao méto-
do recursivo e privado insere. O método insere busca recursivamente a 
posição adequada para a inserção do novo elemento. Observe que, se o 
elemento procurado já existir na ABB, nada é inserido. 
53 Balanceamento de árvores
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
public void insereABB(long id, Object elemento) // inserção na ABB
 {
 if (raiz == null) {
 raiz = new No(id,elemento,null,null);
 } else {
 No novoNo = new No(id,elemento,null,null);
 insere(raiz,novoNo);
 }
 } // final do método insereABB
 private void insere(No atual, No novo) // inserção ordenada
 {
 if (atual.getId() == novo.getId()) { // achou o elemento, nada inserido
 return;
 } 
if (novo.getId() < atual.getId()) { // vai inserir à esquerda
 if(atual.getEsq() == null) { // achou a posição, basta inserir
 atual.setEsq(novo);
 } else { // continua buscando resursivamente à esquerda
 insere(atual.getEsq(),novo);
 }
 } 
if (novo.getId() > atual.getId()) { // vai inserir à direita
 if(atual.getDir() == null) { // achou a posição, basta inserir
 atual.setDir(novo);
 } else { // continua buscando resursivamente à direita
 insere(atual.getDir(),novo);
 }
 } 
} // final método insere 
O código Java a seguir cria a ABB representada na figura 3, por meio 
da inserção dos valores 88, 70, 75, 99, 110, 105, 119, 80, 67, 59, 72, 91, 
90, 95 e 69, atribuindo esses valores aos identificadores de cada nó 
da árvore. Observe que, para simplificar o código, o elemento inserido 
em cada nó é sempre o mesmo texto “elemento”, mas poderia ser, por 
exemplo, um cadastro de cliente completo. 
54 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
public class ExemploABB // Exemplo de criação de uma ABB 
{
 public static void main(String[] args)
 {
 ABB a = new ABB(); // cria a árvore binária de busca
 a.insereABB(88,″elemento″);
 a.insereABB(70,″elemento″);
 a.insereABB(75,″elemento″);
 a.insereABB(99,″elemento″);
 a.insereABB(110,″elemento″);
 a.insereABB(105,″elemento″);
 a.insereABB(119,″elemento″);
 a.insereABB(80,″elemento″);
 a.insereABB(67,″elemento″);
 a.insereABB(59,″elemento″);
 a.insereABB(72,″elemento″);
 a.insereABB(91,″elemento″);
 a.insereABB(90,″elemento″);
 a.insereABB(95,″elemento″);
 a.insereABB(69,″elemento″);
 a.insereABB(77,″elemento adicional″); // um elemento adicional
 a.imprimeElementosArvore();
 } 
} // final do exemplo de criação de uma ABB 
Neste último código, um último elemento é adicionado à ABB, por 
meio do comando a.insereABB(77,″″), com identificador 77 e com a ca-
deia de caracteres “elemento adicional”. Esse último comando primeira-
mente compara 77 com o identificador da raiz, que é 88 (77 é menor que 
88), e segue para a subárvore esquerda, para, em seguida, comparar 
com o identificador 70 (77 é maior que 70), depois, 75 e 80, resultando 
na inserção do elemento 77 como filho esquerdo de 80 (figura 4). 
55 Balanceamento de árvores
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Figura 4 – Inserção do elemento 77 na ABB 
77 < 88 
77 > 70 
Raiz Insere: 77 
88 
70 99 
67 75 91 110 
77 > 75 
59 69 72 80 90 95 105 119 
77 < 80 
77 
 O método a.imprimeElementosArvore() desse último código resulta 
na impressão dos elementos da ABB representada na figura 4, e o resul-
tado da chamada desse método pode ser observado a seguir. 
Id: 59 Elemento: elemento 
Id: 67 Elemento: elemento 
Id: 69 Elemento: elemento 
Id: 70 Elemento: elemento 
Id: 72 Elemento: elemento 
Id: 75 Elemento: elemento 
Id: 77 Elemento: elemento adicional 
Id: 80 Elemento: elemento 
Id: 88 Elemento: elemento 
Id: 90 Elemento: elemento 
Id: 91 Elemento: elemento 
Id: 95 Elemento: elemento 
Id: 99 Elemento: elemento 
Id: 105 Elemento: elemento 
Id: 110 Elemento: elemento 
Id: 119 Elemento: elemento 
56 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
Observe que os identificadores estão ordenados crescentemen-
te, pois, na implementação do método imprimeElementosArvore(), foi 
utilizado o método inFixado() para caminhamento da árvore. No mé-
todo inFixado(), para todo nó da árvore, primeiramente é percorrida a 
subárvore esquerda. Em seguida, é visitado o nó pai. Depois, é percor-
rida a subárvore direita. O código a seguir apresenta a implementação 
dos métodos inFixado() e imprimeElementosArvore(). 
private void inFixado(No atual) // caminhamento in fixado da árvore binária
 {
 if (atual != null) {
 inFixado(atual.getEsq());
 System.out.println(″Id: ″+atual.getId()+″ Elemento: ″+atual.getElemento());
 inFixado(atual.getDir());
 }
 } // final método inFixado
 public void imprimeElementosArvore() // impressão dos elementos da árvore
 {
 inFixado(raiz);
 } // final do método para impressão da árvore 
A busca de um elemento em uma ABB consiste em percorrer a árvo-
re, visitando cada um dos nós apenas uma vez e verificando se o iden-
tificador do nó visitado satisfaz a condição de busca. O caminhamento 
infixado pode ser utilizado como base da implementação da busca de 
um elemento. O código Java a seguir implementa o método buscaABB(), 
que utiliza a chamada ao método recursivo busca para procurar o identi-
ficador do elemento procurado. 
public No buscaABB(long id) // busca de um elemento na ABB
 {
 return busca(raiz,id);
 } // final do método buscaABB 
57Balanceamento de árvores
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 private No busca(No atual, long id) // busca recursiva na ABB
 {
 if (atual == null) { // não encontrou e retorna nulo
 return null;
 } else {
 if (id == atual.getId()) { // achou o elemento
 return atual;
 } else {
 if (id < atual.getId()) {
 // busca só na subárvore esquerda
 return busca(atual.getEsq(), id);
 } else {
 // busca só na subárvore direita
 return busca(atual.getDir(), id);
 }
 }
 } 
} // final do método buscaABB 
A eliminação ou remoção de um elemento da ABB tem início com a 
localização do elemento que será retirado da árvore, e, em caso de su-
cesso, pode ocorrer um destes três casos (LAFORE, 2004): 
• Caso 1: o nó a ser removido é uma folha. 
• Caso 2: o nó a ser removido possui apenas um filho. 
• Caso 3: o nó a ser removido possui dois filhos. 
O primeiro caso, quando o nó a ser removido é uma folha, é o mais 
simples: basta alterar o campo adequado do pai (filho esquerdo ou di-
reito) para o valor nulo. 
No segundo caso, o nó a ser eliminado está ligado ao seu único filho. 
Então, basta alterar o campo adequado do pai (filho esquerdo ou direito) 
para que receba essa ligaçãoao único filho. 
58 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
No terceiro caso, o nó a ser eliminado está ligado aos seus dois fi-
lhos. A solução é possível, mas com uma abordagem diferenciada, ba-
seada na busca de seu sucessor, que consiste em encontrar “o menor 
do conjunto de nós que são maiores que o nó original” (LAFORE, 2004). 
O código Java a seguir apresenta o método removeABB(), que recebe 
o identificador do elemento a ser eliminado da ABB e, se o identificador 
for encontrado na árvore, implementa as três possibilidades de elimina-
ção. Adicionalmente, o código apresenta o método getSucessor(), ne-
cessário para a implementação do caso 3. 
public boolean removeABB(long id) // remove um elemento da ABB
 { // a ABB não pode ser vazia
 No atual = raiz;
 No pai = raiz;
 boolean filhoEsq = true;
 while (atual.getId() != id) { // busca o elemento
 pai = atual;
 if (id < atual.getId()) { // busca à esquerda
 filhoEsq = true;
 atual = atual.getEsq();
 } else { // busca à direita
 filhoEsq = false;
 atual = atual.getDir();
 }
 if (atual == null) { // não achou e termina
 return false;
 }
 }
 // caso 1: elemento não possui filhos
 if (atual.getEsq() == null && atual.getDir() == null) {
 if (atual == raiz) { // eliminando a raiz da ABB
 raiz = null;
 } else {
 if (filhoEsq) { // o elemento era filho esquerdo
 pai.setEsq(null); 
59Balanceamento de árvores
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 } else { // o elemento era filho direito
 pai.setDir(null);
 }
 }
 } else {
 if (atual.getDir() == null) { // Caso 2: com apenas o filho esquerdo
 if (atual == raiz) { // eliminando a raiz
 raiz = atual.getEsq();
 } else {
 if (filhoEsq) { // o elemento era filho esquerdo
 pai.setEsq(atual.getEsq());
 } else { // o elemento era filho direito
 pai.setDir(atual.getEsq());
 }
 }
 } else {
 if (atual.getEsq() == null) { // Caso 2: com apenas o filho direito
 if (atual == raiz) { // eliminando a raiz
 raiz = atual.getDir();
 } else {
 if (filhoEsq) { // o elemento era filho esquerdo
 pai.setEsq(atual.getDir());
 } else { // o elemento era filho direito
 pai.setDir(atual.getDir());
 }
 }
 } else { // Caso 3: elemento possui os dois filhos
 No sucessor = getSucessor(atual); // busca o elemento sucessor
 if (atual == raiz) { // raiz passa a ser o sucessor
 raiz = sucessor;
 } else {
 if (filhoEsq) { // o elemento era filho esquerdo
 pai.setEsq(sucessor);
 } else { // o elemento era filho direito
 pai.setDir(sucessor);
 } 
60 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 }
 sucessor.setEsq(atual.getEsq());
 }
 } 
}
 return true;
 } // final método removeABB
 private No getSucessor(No eliminado) // encontra o próximo menor valor
 {
 No sucessorPai = eliminado;
 No sucessor = eliminado;
 No atual = eliminado.getDir(); // ir para o filho da direita
 while (atual != null) { // até não haver mais filhos à esquerda
 sucessorPai = sucessor;
 sucessor = atual;
 atual = atual.getEsq();
 }
 if (sucessor != eliminado.getDir()) { // se não for o próprio filho direito
 sucessorPai.setEsq(sucessor.getDir());
 sucessor.setDir(eliminado.getDir());
 }
 return sucessor;
 } // final método getSucessor 
2 Técnica de balanceamento de árvore 
binária 
A utilização de árvore binária de busca visa melhorar a eficiência no 
processo de acesso aos dados. Entretanto, o tempo de busca nesse 
tipo de árvore depende da profundidade a ser percorrida para localizar o 
nó desejado (LAFORE, 2004). 
A altura de uma ABB depende de como os dados são inseridos na ár-
vore. A inserção de dados em ordem aleatória resulta em uma ABB com 
bom funcionamento na busca de dados. Entretanto, a inserção de dados 
já ordenados pode resultar em problemas. Observe a árvore da figura 5, 
na qual foram inseridos, nesta ordem, os elementos: 10, 20, 30, 40 e 50. 
61 Balanceamento de árvores
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Figura 5 – ABB com inserção de elementos ordenados 
Raiz 
10 
20 
30 
40 
50 
 
 
 
Na ABB da figura 5, a vantagem em dividir os elementos em duas 
metades desaparece, e o tempo de busca de um elemento permanece 
similar ao de uma lista ligada (LAFORE, 2004). 
A criação de uma ABB pode não garantir uma busca eficiente, sendo 
interessante manter, de alguma forma, a árvore sempre o mais comple-
ta possível, com os diversos níveis sempre preenchidos, ou seja, manter 
a árvore balanceada. 
De acordo com Tenenbaum, Langsam e Augenstein (1995, p. 526), “o 
balanceamento de um nó numa árvore binária é definido como a altura 
de sua subárvore esquerda menos a altura de sua subárvore direita”, e 
uma árvore binária está balanceada se a diferença entre as alturas das 
subárvores esquerda e direita for menor ou igual a 1. 
A figura 6 apresenta uma árvore binária balanceada, na qual o 
conteúdo de cada nó é justamente a diferença entre as alturas de suas 
subárvores esquerda e direita, que pode ter um dos seguintes valores: 
-1, 0 e 1. 
62 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
Figura 6 – Árvore binária com indicações do balanceamento 
-1 
1 
0 
0 0 
0 
0 
1 
0 0 
0 0 0 0 
0 0 
-1 
Fonte: adaptado de Tenenbaum, Langsam e Augenstein (1995, p. 527). 
No caso de inserção de um elemento na árvore já balanceada (o 
mesmo pode ocorrer na remoção), a árvore pode deixar de ser balan-
ceada. Na figura 7, podem ser encontradas todas as possibilidades re-
sultantes da execução do método inserção em uma ABB. As inserções 
resultando em uma árvore balanceada estão marcadas com a letra B, 
as inserções que eliminam o balanceamento estão marcadas com U1 a 
U12. O nó com marcação 1-4 indica que as inserções U1 a U4 o afetam, 
e o mesmo pode ser observado nos nós com marcações 5-8 e 9-12. 
Figura 7 – Possibilidades de inserção em uma árvore balanceada 
9-12 
BBB B 
5-8 
U3 U4U1 U2 
1-4 
BB 
U5 U6 U7 U8 U9 U10 U11 U12 
Fonte: adaptado de Tenenbaum, Langsam e Augenstein (1995, p. 527). 
63 Balanceamento de árvores
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Uma proposta de solução é testar o balanceamento da árvore após 
uma inserção ou remoção e providenciar uma alteração na árvore que 
restaure o balanceamento, baseada nas operaçõesde rotação à direita 
ou rotação à esquerda da árvore. 
A figura 8 apresenta uma árvore que estava balanceada até a inser-
ção do novo elemento com valor 95, resultando na eliminação do ba-
lanceamento da árvore, e já com uma indicação da rotação à direita da 
subárvore direita do nó 88. 
Figura 8 – Inserção de elemento eliminando o balanceamento da árvore 
Raiz 
88 
70 99 
91 
95 
A árvore resultante da aplicação da rotação à direita está represen-
tada na figura 9. 
Figura 9 – Operação de rotação restaurando o balanceamento da árvore 
Raiz 
88 
70 91 
95 99 
 
 
64 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
A árvore balanceada AVL foi introduzida pelos russos Adelson-Velsky 
e Landis em 1962 e é caracterizada pela adição de um novo campo em 
cada nó destinado ao armazenamento da diferença entre as alturas das 
subárvores esquerda e direita (LAFORE, 2004). 
Considerações finais 
Neste capítulo, foram apresentados os conceitos associados ao TAD 
árvore binária de busca, incluindo características, regras de formação 
e as operações de inserção de elementos, impressão de todos os ele-
mentos da árvore, busca de um determinado elemento e remoção de 
elementos. Também foram apresentados conceito básicos e técnicas 
de balanceamento de árvores binárias, preparando para o estudo das 
árvores balanceadas AVL. 
Referências 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013. 
LAFORE, Robert. Estrutura de dados e algoritmos em Java. Rio de Janeiro: 
Ciência Moderna, 2004. 
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. 
Estruturas de dados usando C. São Paulo: Makron Books, 1995. 
65 
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Capítulo 5 
Árvore AVL 
A utilização direta de árvores binárias de busca visa melhorar a 
eficiência no processo de acesso aos dados, entretanto apenas a cria-
ção de uma ABB pode não garantir uma busca eficiente, pois o tempo 
de busca nesse tipo de árvore depende da profundidade a ser percor-
rida para localizar o nó desejado (LAFORE, 2004). Sendo assim, é inte-
ressante manter, de alguma forma, a árvore sempre o mais completa 
possível, com os diversos níveis sempre preenchidos, ou seja, manter a 
árvore balanceada. 
66 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 
Neste capítulo, será abordado um tipo específico de árvore binária 
de busca balanceada, a árvore AVL, além das operações de balancea-
mento necessárias para a sua manutenção após as ações de inserção 
e remoção de nós. 
1 Entendimento sobre árvore AVL 
De acordo com Szwarcfiter e Markenzon (2010, p. 130), “uma árvore 
binária T é denominada AVL quando, para qualquer nó de T, as alturas 
de suas subárvores, esquerda e direita, diferem em módulo de até uma 
unidade”. A figura 1 ilustra uma árvore e as subárvores esquerda e direi-
ta, sendo que, para representar uma árvore AVL, o indicador B de cada 
nó é calculado pela diferença entre as alturas das subárvores esquerda 
e direita, sendo que essa diferença deve ser -1, 0 ou 1. 
Figura 1 – Ilustração de uma árvore e as alturas de suas subárvores 
Raiz 
Indicador B 
Altura 
esquerda Altura 
direita 
O termo “AVL” representa as iniciais dos russos Adelson-Velsky e 
Landis, que, em 1962, introduziram um campo adicional a cada nó da 
árvore balanceada, o campo indicador de balanceamento ou simples-
mente “indicador B”, que armazena a diferença entre as alturas das 
subárvores esquerda e direita do nó (LAFORE, 2004). Para assegurar o 
balanceamento após a alteração da estrutura da árvore, com inserção ou 
67 Árvore AVL
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
remoção de nó, são utilizadas operações de rotação da árvore. A figura 2 
apresenta um exemplo genérico de árvore AVL, apenas com a represen-
tação do indicador de balanceamento (indicador B) em cada nó, na qual 
todos os nós estão de acordo com a definição, ou seja, o valor absoluto 
da diferença das alturas das subárvores não pode ser maior que 1. 
Figura 2 – Exemplo genérico de árvore AVL 
Raiz 
1 
0 
1 -1 
0 0 0 0 
0 0 00 
1 
0 0 
00 
Fonte: adaptado de Tenenbaum, Langsam e Augenstein (1995). 
Na inserção de um novo elemento na árvore AVL, pode ocorrer a 
perda do balanceamento. Nesse caso, é preciso realizar a correção, 
promovendo uma alteração na árvore que restaure o balanceamento 
(GOODRICH; TAMASSIA, 2013). 
A proposta na árvore AVL é verificar se, após a inserção, existe al-
gum nó da árvore desbalanceado, ou seja, se a operação resultou em 
algum nó com o valor absoluto do indicador B maior que 1. No caso 
do desbalanceamento de um nó, transformações baseadas em rota-
ção devem ser aplicadas para restaurar o balanceamento da árvore 
(SZWARCFITER; MARKENZON, 2010). 
Tomando como referência a árvore AVL da figura 2, a inserção de 
um novo elemento pode ocasionar diversos tipos de alteração nessa 
árvore. A figura 3 apresenta, na cor azul, as possibilidades de inserção 
68 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
sem que haja a quebra do balanceamento. Por outro lado, as posições 
em laranja são aquelas que tornariam a árvore desbalanceada, portan-
to, carecendo de transformações para a correção. 
Figura 3 – Exemplos de inserção de nós em uma árvore AVL 
Raiz 
1 
0 
1 -1 
0 0 
00 00 
1 
0 0 
00 
0 0 
 
 
Fonte: adaptado de Tenenbaum, Langsam e Augenstein (1995). 
Na ocorrência do desbalanceamento na inserção, as transforma-
ções realizadas para restaurar o balanceamento precisam conservar as 
mesmas características básicas de uma ABB, ou seja, todos os elemen-
tos da subárvore esquerda de um nó são sempre menores que o valor 
armazenado nesse nó e todos os elementos da subárvore direita de um 
nó são sempre maiores que o valor armazenado nesse nó (GOODRICH; 
TAMASSIA, 2013). 
As operações de rotação sobre uma árvore alteram o balancea-
mento da árvore, mas mantêm todas as características da árvore ori-
ginal. São quatro tipos de rotação: rotação à direita, rotação à esquer-
da, rotação dupla à direita e rotação dupla à esquerda (SZWARCFITER; 
MARKENZON, 2010). 
A figura 4 ilustra a inserção de um elemento (o valor 15), e, como resul-
tado, ocorre o desbalanceamento do nó com valor 31, que passa a ter o 
69 Árvore AVL
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.indicador B = 2. A operação de rotação à direita gira os elementos ligados 
a esse elemento, resultando, novamente, em uma árvore balanceada. 
Figura 4 – Inserção do elemento 15 e rotação à direita 
Raiz 
31 
12 21 
4018 
Raiz 
31 
12 21 
4018 
Inserção: 15 
B = 2 
Nó desbalanceado 
Rotação à direita no nó 31 
e volta a ser AVL 
Raiz 
18 
3112 
15 
15 21 40 
A figura 5 apresenta a inserção do elemento 20, que resulta no des-
balanceamento do mesmo nó com valor 31, mas, nesse caso, a simples 
rotação não resolveria o problema. São necessárias uma primeira rota-
ção e, em seguida, a rotação final, retornando à condição de balancea-
mento da árvore. 
Figura 5 – Inserção do elemento 20 e rotação dupla à direita 
18 
Raiz Raiz Raiz Raiz 
Nó desbalanceado 
31 B = 2 31 31 21 
12 21 12 21 
Primeira rotação, 
mas não é suficiente 
Rotação dupla à direita 
402018 20 12 
no nó 31 e volta a ser AVL 
Inserção: 20 20 12 
40 18 40 21 40 18 31 
A rotação à esquerda e a rotação dupla à esquerda seguem os mes-
mos princípios, mas são aplicadas quando o desbalanceamento ocorre 
na outra subárvore do nó desbalanceado. 
70 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
Na operação de remoção de um elemento, vale o mesmo princípio: 
remove-se o elemento como se fosse uma ABB e verifica-se o balan-
ceamento; caso haja desbalanceamento, as operações de rotação são 
aplicadas. 
2 Operações de balanceamento e rotação 
O TAD árvore AVL é muito semelhante à ABB, sendo assim, os mes-
mos operadores são oferecidos: inserção, impressão, busca e remoção. 
Na implementação da árvore AVL, o TAD nó utilizado em ABB neces-
sita de dois novos dados, um para armazenar o indicador de balancea-
mento B (diferença entre as alturas das subárvores) e outro para arma-
zenar um novo apontador para o pai do nó. Nesse contexto, o código 
Java a seguir apresenta a classe No, com esses dois novos dados, os 
atributos long b e No pai e os operadores necessários para tratá-los. 
public class No // Implementação da classe No de uma árvore AVL 
{
 private long id; // identificador do elemento
 private Object elemento; // armazena o elemento de cada No
 private No esq; // aponta para o filho esquerdo do nó
 private No dir; // aponta para o filho direito do nó
 private No pai; // aponta para o pai do nó
 private long b; // balanceamento do NO
 public No(long id, Object elemento, No esq, No dir) { // construtor classe No
 this.id = id;
 this.elemento = elemento;
 this.esq = esq;
 this.dir = dir;
 this.b = 0; // inicia o nó sempre balanceado com 0
 this.pai = null; // inicia o pai sempre como vazio
 } 
public String toString() { // método para converter o nó em texto
 return Long.toString(getId());
 // return ″Id:″+Long.toString(getId())+″ B:″+Long.toString(getB()); 
71Árvore AVL
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 }
 public void setId(long id) { // método para alterar o identificador do nó
 this.id = id;
 } 
public long getId() { // método para receber o identificador do nó
 return this.id;
 }
 public void setElemento(Object elemento) { // método para alterar o elemento
 this.elemento = elemento;
 }
 public Object getElemento() { // método para receber o objeto contido no No
 return elemento;
 }
 public void setEsq(No esq) { // método que altera o filho esquerdo
 this.esq = esq;
 }
 public No getEsq() { // método que recebe o filho esquerdo do nó
 return esq;
 }
 public void setDir(No dir) { // método que altera o filho direito
 this.dir = dir;
 }
 public No getDir() { // método que recebe o filho direito do nó
 return dir;
 }
 public void setB(long b) { // método para alterar o balanceamento
 this.b=b;
 }
 public long getB() { // método que recebe o balanceamento
 return b;
 } 
public void setPai( No pai ) { // método que altera o pai do nó
 this.pai = pai;
 }
 public No getPai() { // método que recebe o pai do nó
 return pai;
 } 
} // Final da classe No 
O primeiro operador a ser implementado é o de inserção de um nó na 
árvore AVL. Esse operador é semelhante ao operador insereABB, mas, 
após a inserção, é feita uma avaliação do balanceamento. O código em 
72 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
Java a seguir apresenta o método público insereAVL() e, principalmente, 
o método privado insere(), ambos pertencentes à classe ArvoreAVL, que 
implementa a inserção de um novo elemento em uma árvore AVL. 
public void insereAVL(long id, Object elemento) // inserção na AVL
 {
 No novoNo = new No(id,elemento,null,null);
 insere(raiz,novoNo);
 } // final do método insereAVL
 private void insere(No atual, No novo) // inserção ordenada
 {
 if (atual == null) { // árvore vazia, insere na raiz
 this.raiz = novo;
 return;
 }
 if (novo.getId() < atual.getId()) { // vai inserir à esquerda 
if(atual.getEsq() == null) { // achou a posição, basta inserir
 atual.setEsq(novo);
 novo.setPai(atual);
 avaliaBalanceamento(atual);
 } else { // continua buscando resursivamente à esquerda
 insere(atual.getEsq(),novo);
 }
 } else {
 if (novo.getId() > atual.getId()) { // vai inserir à direita
 if(atual.getDir() == null) { // achou a posição, basta inserir
 atual.setDir(novo);
 novo.setPai(atual);
 avaliaBalanceamento(atual);
 } else { // continua buscando resursivamente à direita
 insere(atual.getDir(),novo);
 }
 } else {
 return; // achou o elemento igual, nada inserido
 }
 }
 } // final método insere 
73 Árvore AVL
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 
 
 
 
 
 
 
 
No método insere() implementado na árvore AVL, a grande diferen-
ça para a inserção em ABB está nos comandos novo.setPai(atual) e 
avaliaBalanceamento(atual). No comando novo.setPai(atual), o nó in-
serido recebe um apontador adicional para o seu pai (já mostrado no 
código da classe No). No comando avaliaBalanceamento(atual), que 
está apresentado no código a seguir, o balanceamento é avaliado, e, 
no caso de a inserção resultar em desbalanceamento, o método cor-
reto de rotação (ver comentários no código a seguir) é executado para 
restaurar a árvore AVL. 
private void avaliaBalanceamento(No atual) // avaliar o balanceamento da árvore AVL
 { 
calcBalanceamento(atual); // calcula o indicador B do nó atual
 long b = atual.getB();
 if (b == -2) { // b=-2 indica que a subárvore direita ficou maior
 if (altura(atual.getEsq().getEsq()) >= altura(atual.getEsq().getDir())) { 
// testa netos esq
 atual = rotacaoDir(atual); //subárvore esquerda do neto é maior, rotação simples
 }else{
 atual = duplaRotacaoDir(atual); // rotação dupla
 }
 } else {
 if (b == 2) { // b=2 indica que a subárvore esquerda ficou maior
 if (altura(atual.getDir().getDir()) >= altura(atual.getDir().getEsq())) { 
// testa netos dir 
atual = rotacaoEsq(atual); //subárvore direita do neto é maior, rotação simples
 }else{
 atual = duplaRotacaoEsq(atual); // rotação dupla
 }
 }
 }
 if (atual.getPai() != null) { 
avaliaBalanceamento(atual.getPai()); // sempre vai testar o balanceamento do pai
 }else{
 this.raiz = atual; // senão atual passa a ser a raiz
 }
 } // final método avaliaBalanceamento 
74 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
O código em Java a seguir apresenta os métodos calcBalanceamento 
(No) e altura(No). Observe que o método calcBalanceamento(No) realiza 
a operação diferença entre as alturas das subárvores esquerda e direita 
e, para realizar esse cálculo, utiliza o método altura(No), que retorna a 
altura do nó na árvore. 
private void calcBalanceamento(No no) // calcular o indicador B de um nó
 {
 no.setB(altura(no.getDir()) - altura(no.getEsq()));
 } // final método calcBalanceamento
 private long altura(No atual) // calcula a altura da árvore
 {
 if (atual == null) { // se o nó está vazio sempre retorna -1
 return -1;
 }
 if ((atual.getEsq() == null) && (atual.getDir() == null)) {
 return 0;
 } else {
 if (atual.getEsq() == null) {
 return 1 + altura(atual.getDir());
 } else {
 if (atual.getDir() == null) {
 return 1 + altura(atual.getEsq());
 } else {
 return 1 + Math.max(altura(atual.getEsq()), altura(atual.getDir()));
 }
 }
 }
 } // final método altura 
Os métodos para rotação alteram a estrutura da árvore, mas man-
têm as características de uma árvore binária de busca. A figura 6 ilustra 
o processo de alteração das ligações dos nós na execução de uma ro-
tação à direita. Nesse caso, o nó desbalanceado é o 31, que passará a 
ser filho direito de seu filho esquerdo 18; o nó 21, que é filho direito de 
18, passará a ser filho esquerdo de 31 (substituindo o 18); as ligações 
continuam as mesmas nos demais nós da árvore. No caso de rotação à 
esquerda, a transformação é semelhante, mas para o lado oposto. 
75 Árvore AVL
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Figura 6 – Processo de rotação à direita 
Raiz Raiz Raiz Raiz Nó 31 está Nó 31 fica 18 passa a Nó 31 está 
balanceado desbalanceado balanceadoser a raiz 
B = 1 B = 2 B = 0 
31 31 18 passa a 
ser pai de 31 
15 4021 
Neto direito do 
12 21 12 21 12 21 filho esquerdo passa a ser 
Neto esquerdo 
fica inalterado 
filho de 31 Rotação à direita 
no nó 31 e volta 
a ser AVL Inserção: 15 15 15 
31 18 
18 40 18 40 18 40 12 31 
 
 
 
 
Os métodos para rotação à esquerda e rotação à direita são muito 
semelhantes: ambos recebem um nó da árvore e realizam a operação 
de rotação visando ao balanceamento das subárvores do nó e manten-
do as características da árvore binária de busca. O código em Java a 
seguir apresenta esses dois métodos. Os comentários do código estão 
associados à explicação da figura 6. 
private No rotacaoEsq(No inicial) // realizar rotação à esquerda
 {
 No dir = inicial.getDir(); // salva apontamento do novo pai após rotação
 dir.setPai(inicial.getPai()); 
inicial.setDir(dir.getEsq());//Neto esquerdo do filho direito passa a ser filho direito
 if (inicial.getDir() != null) {
 inicial.getDir().setPai(inicial);
 }
 dir.setEsq(inicial); // filho esquerdo passa a ser pai
 inicial.setPai(dir);
 if (dir.getPai() != null) { // acerta os apontamentos do novo pai
 if (dir.getPai().getDir() == inicial) {
 dir.getPai().setDir(dir);
 } else if (dir.getPai().getEsq() == inicial) {
 dir.getPai().setEsq(dir);
 }
 } 
calcBalanceamento(inicial); // calcula os novos indicadores de balanceamento 
76 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 calcBalanceamento(dir);
 return dir;
 } // final método rotação esquerda
 private No rotacaoDir(No inicial) // realizar rotação à direita
 {
 No esq = inicial.getEsq(); // salva apontamento do novo pai após rotação
 esq.setPai(inicial.getPai()); 
inicial.setEsq(esq.getDir());//Neto direito do filho esquerdo passa a ser filho esquerdo
 if (inicial.getEsq() != null) {
 inicial.getEsq().setPai(inicial);
 }
 esq.setDir(inicial); // filho esquerdo passa a ser pai
 inicial.setPai(esq);
 if (esq.getPai() != null) { // acerta os apontamentos do novo pai
 if (esq.getPai().getDir() == inicial) {
 esq.getPai().setDir(esq);
 } else if (esq.getPai().getEsq() == inicial) {
 esq.getPai().setEsq(esq);
 }
 } 
calcBalanceamento(inicial);
 // calcula os novos indicadores de balanceamento
 calcBalanceamento(esq);
 return esq;
 } // final método rotação direita 
Para completar o entendimento da inserção em árvore AVL, restam 
os métodos para rotação dupla, que apenas realizam chamadas dos 
métodos de rotação à esquerda e rotação à direita. O código em Java a 
seguir apresenta esses métodos. 
private No duplaRotacaoDir(No inicial) // realizar dupla rotação à direita
 {
 inicial.setEsq(rotacaoEsq(inicial.getEsq()));
 // rotaciona o filho esquerdo para a esquerda
 return rotacaoDir(inicial); // e depois rotaciona a árvore à direita
 } // final método dupla rotação direita 
77Árvore AVL
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 
 
 
 private No duplaRotacaoEsq(No inicial) // realizar dupla rotação à esqueda
 {
 inicial.setDir(rotacaoDir(inicial.getDir()));//rotacionaofilho direito para a direita
 return rotacaoEsq(inicial); // e depois rotaciona a árvore à esquerda
 } // final método dupla rotação esquerda 
A operação de remoção de um nó em uma árvore AVL é similar à re-
moção em ABB. Entretanto, como pode haver desbalanceamento após 
a remoção, basta avaliar o balanceamento resultante no pai do nó logo 
após a sua remoção. 
Considerações finais 
Neste capítulo, foram apresentados os conceitos sobre árvore AVL 
e o processo de avaliação do balanceamento na operação de inser-
ção de um novo elemento e a consequente necessidade de alterar 
a estrutura da árvore com operações de rotação para satisfazer as 
condições de uma árvore binária de busca. Além disso, foram apre-
sentados os métodos em Java necessários para a implementação 
dessas operações. 
A implementação das operações do TAD árvore AVL é razoavelmente 
complexa, merece atenção especial pelo uso intensivo de recursividade 
e oferece bons desafios para a formação de programadores. 
Referências 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013. 
LAFORE, Robert. Estrutura de dados e algoritmos em Java. Rio de Janeiro: 
Ciência Moderna, 2004. 
78 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
dito
ra
 S
en
ac
 S
ão
 P
au
lo
.
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de dados e seus 
algoritmos. Rio de Janeiro: LTC, 2010. 
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. 
Estruturas de dados usando C. São Paulo: Makron Books, 1995. 
79 
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Capítulo 6 
Grafos 
Grafos são estruturas versáteis e representam uma importante fer-
ramenta matemática aplicável a diversas áreas do conhecimento e 
utilizada na resolução de diversos tipos de problema, não só ligados a 
computação, mas também a problemas do cotidiano. 
Neste capítulo, serão tratados os conceitos básicos de grafos, a im-
plementação de um tipo abstrato de dados, bem como o tratamento de 
exemplos e aplicações práticas. 
80 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
1 Conceitos básicos de grafos 
Os grafos são estruturas baseadas em conceitos matemáticos utili-
zadas para modelar e resolver problemas por meio de uma representa-
ção gráfica formada por vértices e arestas. Grafos podem ser aplicados 
a diversos domínios do conhecimento, por exemplo, na logística, na quí-
mica, nas redes de computadores, na engenharia elétrica, na medicina, 
entre outros (GOODRICH; TAMASSIA, 2013). Os grafos podem ser uti-
lizados para resolver alguns problemas, como qual o melhor caminho 
a ser utilizado por um entregador e qual a melhor alocação entre as 
posições profissionais de uma empresa e os profissionais que se sub-
meteram a essas posições. Eles também são utilizados na busca de 
informações relevantes na internet, entre outros. 
No século XVIII, o suíço Leonhard Euler foi o primeiro matemáti-
co a representar um problema real utilizando grafos. A cidade russa 
Königsberg era entrecortada pelo rio Pregel, resultando em duas gran-
des ilhas, sendo que a população local utilizava sete pontes para aces-
sar os vários pontos da cidade (figura 1). O grande desafio da época era, 
partindo de um local da cidade, atravessar cada uma das pontes uma 
vez e retornar ao ponto de partida (LAFORE, 2004). 
Figura 1 – Pontes de Königsberg 
1 2 
4 
3 
5 6 7 
Fonte: adaptado de Lafore (2004). 
81 Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
O matemático Leonhard Euler analisou e modelou o problema utili-
zando grafos e provou matematicamente que não era possível resolver 
o desafio, ou seja, partir de um ponto qualquer da cidade, passar em to-
das as pontes apenas uma vez e retornar ao ponto de partida. A figura 2 
apresenta o diagrama de grafos associado ao problema das pontes. 
Perceba que os vértices (círculos) do grafo representam as porções de 
terra da cidade e as arestas (arcos) representam as pontes. 
Figura 2 – Diagrama de grafos associado ao problema das sete pontes de Königsberg 
B 
A D 
C 
Ponte 1 
Ponte 3 
Ponte 4 
Ponte 7 
Ponte 2 
Ponte 5 Ponte 6 
Um grafo consiste em um conjunto de vértices (ou nós) e um conjun-
to de arestas (ou arcos), sendo que cada aresta é definida por um par 
de vértices (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). A figura 3 
apresenta um grafo com o conjunto de vértices {A,B,C,D,E} e o conjunto 
de pares ordenados de vértices representando as arestas {(A,B), (A,C), 
(A,D), (A,A), (C,A), (C,D)}. Observe que o vértice E não participa do conjun-
to de pares, pois não possui ligação com outro vértice. 
82 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
Figura 3 – Exemplo de grafo com vértices e arestas 
A 
B 
C 
D E 
As arestas de um grafo podem ser simples ou direcionadas por uma 
seta, indicando que a relação entre os vértices tem um sentido definido. 
Quando um grafo possui todas as arestas direcionadas, é denominado 
“dígrafo”. A figura 4 ilustra um dígrafo com os mesmos vértices do grafo 
da figura 3, mas com todas as arestas direcionadas e resultando no 
conjunto de arestas {(A,B), (A,C), (A,A), (C,A), (D,A), (E,D)}. Quando um 
grafo possui arestas dirigidas e não dirigidas, é denominado grafo misto 
(GOODRICH; TAMASSIA, 2013). 
Figura 4 – Exemplo de grafo com todas as arestas direcionados (dígrafo) 
A 
B 
C 
D E 
Complementando o entendimento de grafos visando aos demais tó-
picos, o quadro 1 apresenta terminologias e definições associadas a 
grafos (GOODRICH; TAMASSIA, 2013): 
83 Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 
 
 
 
 
 
 
Quadro 1 – Terminologias e definições 
VÉRTICES 
FINAIS 
São dois vértices ligados por uma mesma aresta, por exemplo, vértices A e B na 
figura 3, mas o vértice E não é final, pois não tem a aresta conectada a um vértice. 
Se a aresta for dirigida, o primeiro vértice final é a origem, e o segundo, o destino. Na 
figura 4, A é origem e B é destino. 
VÉRTICES 
ADJACENTES 
São dois vértices ligados por uma aresta. Por exemplo, o vértice A ligado ao B na 
figura 3, mas o vértice B não é adjacente a C e a D. 
ARESTA 
INCIDENTE 
Uma aresta é incidente a um vértice se este for um ponto final da aresta. Por exemplo, 
na figura 3, a aresta que liga os vértices A e B é incidente a A e a B. 
Ocorrem com grafos que apresentam arestas direcionadas. As arestas de entrada de 
um vértice são as arestas direcionadas nas quais o vértice é o destino, e as arestas 
de saída são as arestas direcionadas nas quais o vértice é a origem. Na figura 4, o 
vértice B possui uma aresta de entrada, e o vértice E possui uma aresta de saída. 
Dois vértices constituem o par ordenado que caracteriza uma aresta. Então, o primeiro 
vértice do par é o predecessor do segundo, e o segundo é sucessor do primeiro. 
É a quantidade de arestas incidentes ao vértice. Por exemplo, na figura 3, o grau do 
ARESTAS DE 
ENTRADA E 
DE SAÍDA 
VÉRTICE 
SUCESSOR E 
PREDECESSOR 
vértice A é 6, o grau do vértice D é 2, e o grau do vértice E é 0. Em grafos dirigidos, o 
GRAU DO 
VÉRTICE 
grau pode ser de entrada ou saída. Por exemplo, na figura 4, para o vértice A, o grau 
de saída é 3 e o grau de entrada é também 3; já para o vértice C, o grau de saída é 2 e 
o grau de entrada é 1. 
Ocorrem quando duas arestas não dirigidas têm os mesmos pontos finais. Por 
exemplo, na figura 3, as arestas entre os vértices A e C são paralelas. No caso de 
arestas dirigidas, estas serão paralelas quando tiverem a mesma origem e o mesmo 
destino. Observe que, na figura 4, as arestas entre os vértices A e C não são paralelas, 
pois possuem origem e destino diferentes. 
São arestas que ligam um mesmo vértice. Na figura 3 e na figura 4, a aresta que liga o 
vértice A a ele mesmo são dois exemplos de laço. 
É uma sequência alternada de vértices e arestas de um grafo. Um caminho inicia 
e termina em vértices e tem arestas ligando cada um dos vértices do caminho. Na 
figura 3, a sequênciaB, A, C, D seria um exemplo de caminho, ou seja, esses vértices 
seriam visitados nessa ordem durante a realização desse caminho. 
É um caminho formado apenas por arestas dirigidas e percorridas de acordo com 
as direções definidas. Na figura 4, um exemplo de caminho dirigido poderia ser a 
sequência de vértices E, D, C, A. 
ARESTAS 
PARALELAS 
LAÇOS 
CAMINHO 
CAMINHO 
DIRIGIDO 
GRAFO CONEXO Um grafo é conexo se, para quaisquer dois vértices, existir um caminho entre eles. 
VÉRTICE 
ISOLADO 
É um vértice do grafo que não é adjacente a nenhum outro vértice. Por exemplo, o 
vértice E da figura 3. 
84 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
O TAD grafo permite tratar os dados associados a um grafo por 
meio de operações que manipulem os vértices e as arestas. A pri-
meira estrutura a ser definida na implementação do TAD é o vértice, 
que deve ser capaz de representar objetos do mundo real, como pe-
daços de terra, cidades, pontes, atividades a serem realizadas, entre 
outros. Sendo assim, o código em Java a seguir apresenta a classe 
Vertice, com dois campos rótulo e o indicador se o vértice foi visitado 
(LAFORE, 2004). 
public class Vertice // Implementação da classe Vertice 
{
 private String rotulo; // armazena o rótulo de cada vértice
 private boolean visitado; // indica se o vértice foi visitado
 public Vertice(String rotulo) { // construtor classe Vertice
 this.rotulo = rotulo;
 this.visitado = false;
 }
 public String toString() { // método para converter o vértice em texto
 return rotulo;
 }
 public void setRotulo(String rotulo) { // método para alterar o rótulo
 this.rotulo = rotulo;
 }
 public Object getRotulo() { // método para receber o rótulo
 return rotulo;
 }
 public void foiVisitado() { // método para indicar visitado
 this.visitado = true;
 }
 public void naoFoiVisitado() { // método para indicar não foi visitado
 this.visitado = false; 
}
 public boolean getVisitado() { // método que retorna o estado de visitado
 return visitado;
 } 
} // Final da classe Vertice 
85 Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
Nos exemplos de grafos apresentados (figura 2, figura 3 e figura 4), 
para os rótulos dos vértices, foram utilizadas letras. Entretanto, em apli-
cações reais, como o problema das sete pontes, os rótulos dos vértices 
podem ser substituídos por objetos mais elaborados. Visando simpli-
ficar o código, mas não prejudicando o entendimento sobre grafos, os 
rótulos serão representados por um campo string de texto, ou seja, os 
vértices continuarão sendo representados por letras. 
Duas estruturas de dados computacionais são comumente utiliza-
das na implementação de grafos: a lista de adjacências e a matriz de 
adjacências (GOODRICH; TAMASSIA, 2013). Na lista de adjacências, as 
arestas são armazenadas em um vetor de listas ligadas, e cada uma 
dessas listas armazena em seus nós as adjacências de cada vértice. 
Neste texto, será priorizada a utilização da matriz de adjacências como 
estrutura de armazenamento de implementação do TAD grafo. 
Na implementação de um grafo com N vértices baseada em matriz 
de adjacências, utiliza-se um vetor bidimensional com N posições em 
cada dimensão (matriz N × N) para indicar a existência de uma aresta 
entre dois vértices (LAFORE, 2004). Usualmente, em uma matriz de ad-
jacências (tabela 1), a existência de valor 1 em uma determinada linha 
e coluna indica uma aresta entre os vértices. O grafo da figura 5 possui 
quatro vértices (A, B, C e D) e o conjunto de arestas {(A,B), (A,C), (A,D), 
(C,D)}. A matriz de adjacências para representar esse grafo é forma-
da por quatro linhas e quatro colunas, e está apresentada na tabela 1. 
Observe que as posições associadas às arestas do grafo estão mar-
cadas com o valor 1. Por exemplo, a aresta (A,B) resulta nas posições 
Matriz [A,B] = 1 e Matriz [B,A] = 1, pois o grafo não é dirigido, e, nes-
se caso, os dois sentidos da aresta são válidos. No caso de um grafo 
dirigido, a matriz terá a mesma estrutura, mas a atribuição de valores 
será diferente. 
86 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
Figura 5 – Grafo representado na matriz de adjacências 
A 
C 
D 
B 
Tabela 1 – Matriz de incidência do grafo 
MATRIZ A B C D 
A 0 1 1 1 
B 1 0 0 0 
C 1 0 0 1 
D 1 0 1 0 
Para completar a implementação do TAD grafo, é necessário ainda 
criar uma estrutura para armazenar os vértices. No caso, será utilizado 
um vetor de vértices, no qual o índice do vetor será coincidente com o 
índice usado na matriz de adjacências, ou seja, se o grafo apresentar 
N vértices, as N primeiras posições do vetor (de 0 a N-1) serão arma-
zenadas com os vértices (classe Vertice), e, na matriz de adjacências, 
as duas dimensões da matriz serão indexadas de 0 a N-1. O código em 
Java a seguir apresenta a classe Grafo implementando essa solução 
baseada em matriz de adjacências com os operadores para adicionar 
vértices e arestas ao grafo. 
class Grafo // implementação da classe Grafo 
{ 
private final int MAX_VERTICES = 20; // número máximo de vértices
 private Vertice listaVertice[]; // lista de vértices
 private int matriz[][]; // matriz adjacente
 private int numVertices; // número atual de vértices 
87Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 public Grafo() { // construtor da clase Grafo
 listaVertice = new Vertice[MAX_VERTICES]; // cria a lista de vértices
 matriz = new int[MAX_VERTICES][MAX_VERTICES]; // cria a matriz adjacente
 numVertices = 0; // inicia número de vértices como 0 
for(int y=0; y<MAX_VERTICES; y++) { // inicializa matriz zerada, sem arestas
 for(int x=0; x<MAX_VERTICES; x++) {
 matriz[x][y] = 0;
 }
 }
 }// final construtor 
public void adicVertice(String rotulo) { // método para adicionar um novo vértice
 numVertices++;
 listaVertice[numVertices] = new Vertice(rotulo);
 } // final adicVertice 
public void adicAresta(int inicio, int fim) { // método para adicionar uma aresta
 matriz[inicio][fim] = 1;
 matriz[fim][inicio] = 1;
 } // final adicAresta 
public void displayVertice(int v) { // método para exibir um determinado vértice
 System.out.print(listaVertice[v].getRotulo());
 } // final displayVértice 
} // final da classe Grafo 
O código em Java a seguir realiza a criação do grafo da figura 5 re-
presentado pela matriz de adjacências da tabela 1. 
class ExemploGrafo 
{
 public static void main(String[] args) { // criação de um grafo simples
 Grafo g = new Grafo(); // criação do novo Grafo com até 20 vértices
 // inserção dos vértices
 g.adicVertice(″A″); // será índice 0
 g.adicVertice(″B″); // será índice 1
 g.adicVertice(″C″); // será índice 2
 g.adicVertice(″D″); // será índice 3
 // inserção das arestas
 g.adicAresta(0,1); // aresta AB 
88 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
om
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 g.adicAresta(0,2); // aresta AC
 g.adicAresta(0,3); // aresta AD
 g.adicAresta(2,3); // aresta CD
 } // final main 
} // final ExemploGrafo 
O código apenas cria o grafo da figura 5 e permite que novas ope-
rações sejam realizadas sobre o grafo, sendo que uma das operações 
mais importantes a ser realizada é a identificação de quais nós podem 
ser atingidos a partir de um determinado vértice (LAFORE, 2004). Um 
exemplo prático e real poderia ser, partindo de uma determinada cidade 
europeia, identificar ou buscar todas as cidades atingíveis por um cami-
nho realizado apenas por trem. 
PARA SABER MAIS 
Para encontrar mais exemplos sobre a aplicação de grafos para tratar 
problemas cotidianos, consulte o início do capítulo 13 do livro Estrutura 
de dados e algoritmos em Java (GOODRICH; TAMASSIA, 2013). 
 
2 Exemplos de aplicações práticas 
representadas por grafos 
A implementação do TAD grafo permite criar um grafo adicionando 
todos os seus vértices e arestas, mas ainda é necessário um método 
ou algoritmo que permita sistematicamente buscar e identificar todos 
os vértices alcançáveis a partir de um determinado vértice inicial. Para 
esse fim, existem basicamente dois métodos para percorrer um grafo: 
a pesquisa em profundidade (depth-first search – DFS) e a pesquisa em 
largura (breadth-first search – BFS) (GOODRICH; TAMASSIA, 2013). 
89 Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Na pesquisa em profundidade de um grafo, o princípio básico é, par-
tindo de um determinado vértice, visitar recursivamente cada nó adja-
cente ainda não visitado até encontrar um vértice que não tenha vérti-
ces adjacentes ainda não visitados, ou seja, segue um caminho em toda 
a profundidade do grafo, depois volta e segue outro caminho até o final, 
e assim por diante. 
Na implementação da operação DFS do TAD grafo, é necessária a uti-
lização de um TAD pilha para armazenar os vértices já visitados e saber 
para onde voltar quando chegar ao final de um caminho em profundidade. 
O algoritmo para realizar a operação DFS é o seguinte (LAFORE, 2004): 
• Selecione um vértice inicial, visite o vértice e empilhe-o. Visitar 
o vértice significa marcar o vértice como visitado e realizar uma 
ação sobre ele, por exemplo, escrever o seu conteúdo na tela. 
• Regra 1: se possível, visite um vértice adjacente que ainda não 
tenha sido visitado, faça a marcação como visitado e empilhe 
esse vértice. 
• Regra 2: se a regra 1 não puder ser seguida, se a pilha não estiver 
vazia, retire um vértice da pilha. 
• Regra 3: se as regras 1 e 2 não puderem ser seguidas, terminou 
o algoritmo. 
Aplicando o algoritmo ao grafo da figura 6 e partindo do vértice A, a 
primeira ação é visitar e empilhar A (1a visita). Em seguida, aplicando a 
regra 1, o vértice B é visitado e empilhado (2a visita). Observe que o vérti-
ce C também poderia ser o próximo a ser visitado, pois é adjacente a A, 
mas se optou por B. Visitado o vértice B, aplica-se a regra 1, e o vértice 
E é visitado e empilhado (3a visita). Novamente a regra 1 é aplicada, e o 
vértice G é visitado e empilhado (4a visita). Nesse ponto, como G não tem 
mais adjacentes, a regra 2 é aplicada. O vértice G é retirado da pilha, e a 
regra 2 é aplicada novamente duas vezes, para E e para B, voltando-se 
ao vértice A, que ficou no topo da pilha. Observe que o vértice A ainda 
90 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
apresenta vértices adjacentes, sendo assim, a regra 1 é aplicada e um 
novo caminho em profundidade é percorrido, ou seja, C (5a visita) e D (6a 
visita). Observe, agora, que C tem mais um adjacente, o vértice F. Sendo 
assim, a regra 1 pode ser aplicada, e F é visitado e empilhado (7a visita). 
Agora, a regra 2 é aplicada três vezes, desempilhando F, C e A. Por fim, a 
regra 3 é aplicada, terminando o algoritmo. 
Figura 6 – Pesquisa em profundidade no grafo 
2a visita 3a visita 4a visita 
1a visita 5a visita 7a visita 
A 
B 
6a visita 
D 
FC 
E G 
A tabela 2 apresenta a sequência de ações tomadas na pesquisa em 
profundidade do grafo da figura 6, bem como as regras aplicadas e o 
estado da pilha após cada ação. 
Tabela 2 – Sequência de ações da pesquisa em profundidade 
Regra Ação Pilha 
Início Visita A A 
1 Visita B AB 
1 Visita E ABE 
1 Visita G ABEG 
2 POP G ABE 
2 POP E AB 
2 POP B A 
1 Visita C AC 
1 Visita D ACD 
(cont.) 
91 Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
Regra Ação Pilha 
2 POP D AC 
1 Visita F ACF 
2 POP F AC 
2 POP C A 
2 POP A 
3 Termina 
Fonte: adaptado de Lafore (2004, p. 572). 
O código em Java a seguir apresenta o método DFS que implementa 
a operação de pesquisa em profundidade do TAD grafo, junto ao méto-
do auxiliar que retorna um vértice ainda não visitado da lista de vértices 
(LAFORE, 2004). O TAD pilha não é exibido aqui, mas pode ser imple-
mentado com os conceitos de lista ligada ou mesmo um vetor. 
public void DFS () { // pesquisa em profundidade no grafo
 Pilha p = new Pilha(); 
listaVertice[0].foiVisitado(); // indica que o primeiro vértice foi visitado
 mostraVertice(0); // mostra o primeiro vértice
 p.push(0); // coloca na pilha
 while( !p.eVazia() ) { // até que a pilha seja vazia
 // pega um vértice adjacente ainda não visitado para colocar na pilha
 int v = pegaVerticeNaoVisitado( (int) p.topo() );
 if(v == -1) { // se não encontrou, tira um da pilha
 p.pop();
 }else{ // encontrou um vértice não visitado
 listaVertice[v].foiVisitado(); // marca como visitado
 mostraVertice(v); // mostra o vértice na tela
 p.push(v); // coloca na pilha
 }
 }
 // a pilha está vazia, basta resetar todas as marcações
 for(int j=0; j<numVertices; j++) // reset flags
 listaVertice[j].naoFoiVisitado();
 } // final método DFS 
92 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
private int pegaVerticeNaoVisitado(int v) { // método encontra vértice ainda não visitado
 for(int j=0; j<numVertices; j++) {
 if(matriz[v][j]==1 && listaVertice[j].getVisitado() == false) {
 return j;
 }
 }
 return -1;
 } // final pegaVerticeNaoVisitado 
Para exemplificar a pesquisa em profundidade, o programa em Java 
a seguir cria o grafo da figura 6 e executa a operação DFS. 
class ExemploDFS 
{ 
public static void main(String[] args) { // criação de um grafo simples
 Grafo g = new Grafo(); // criação do novo Grafo com até 20 vértices
 // inserção dos vértices
 g.adicVertice(″A″); // será índice 0
 g.adicVertice(″B″); // será índice 1g.adicVertice(″C″); // será índice 2
 g.adicVertice(″D″); // será índice 3
 g.adicVertice(″E″); // será índice 4
 g.adicVertice(″F″); // será índice 5
 g.adicVertice(″G″); // será índice 6
 // inserção das arestas
 g.adicAresta(0,1); // aresta AB
 g.adicAresta(0,2); // aresta AC
 g.adicAresta(0,3); // aresta AD
 g.adicAresta(1,4); // aresta BE
 g.adicAresta(4,6); // aresta EG
 g.adicAresta(2,5); // aresta CF
 g.adicAresta(2,3); // aresta CD
 System.out.print(″DFS - Vertices visitados: ″);
 g.DFS(); // pesquisa em profundidade
 System.out.println();
 } // final main 
} // final ExemploDFS 
93 Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
O resultado apresentado na tela após a execução do programa é o 
seguinte: 
DFS - Vertices visitados: ABEGCDF 
A pesquisa em profundidade é muito útil para aplicações de simu-
lação de jogos, nas quais o jogador faz uma escolha entre várias op-
ções e isso faz com que o jogo ofereça um outro conjunto de opções. 
Nesse tipo de aplicação, as opções do jogo são modeladas por um 
grafo e a pesquisa em profundidade é utilizada para definir, dada uma 
opção escolhida (um vértice inicial), todas as opções possíveis a partir 
desse ponto. 
Na pesquisa em largura de um grafo, o princípio básico é, partindo 
de um determinado vértice, visitar todos os seus vértices adjacentes e, 
depois, procurar se ainda existe vértice não visitado e recursivamente 
visitar todos os adjacentes. Ou seja, o grafo é percorrido em toda a sua 
largura e o mais próximo possível do vértice inicial e depois passa para 
o próximo nível mais distante, e assim por diante. 
Na implementação da operação BFS do TAD grafo, é necessária a 
utilização de um TAD fila para armazenar os vértices já visitados e sa-
ber para onde voltar quando chegar ao final de um caminho em largura. 
O algoritmo para realizar a operação BFS é o seguinte (LAFORE, 2004): 
• Selecione um vértice inicial, visite o vértice e torne-o atual. 
• Regra 1: se possível, visite um próximo vértice adjacente ao vérti-
ce atual que ainda não tenha sido visitado, faça a marcação como 
visitado e insira na fila. 
• Regra 2: se a regra 1 não puder ser seguida e se a fila não estiver 
vazia, retire um vértice da fila e o torne o vértice atual. 
94 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
• Regra 3: se a regra 2 não puder ser seguida devido à fila estar 
vazia, terminou o algoritmo. 
O código em Java a seguir apresenta a método BFS que implementa 
a operação de pesquisa em largura do TAD grafo (LAFORE, 2004). O 
TAD fila não é exibido aqui, mas pode ser implementado com os concei-
tos de lista ligada ou mesmo um vetor. 
public void BFS() { // pesquisa em profundidade no grafo
 Fila f = new Fila(); 
listaVertice[0].foiVisitado(); // indica que o primeiro vértice foi visitado
 mostraVertice(0); // mostra o primeiro vértice
 f.insere(0); // insere no final da fila
 int v2;
 while( !f.eVazia() ) { // até que a fila seja vazia
 int v1 = (int) f.remove(); // remove o vértice do início da fila
 // até que não haja mais adjacente não visitado
 while( (v2=pegaVerticeNaoVisitado(v1)) != -1 ) { // pegue um
 listaVertice[v2].foiVisitado(); // marca como visitado
 mostraVertice(v2); // mostra o vértice na tela
 f.insere(v2); // insere no final da fila
 }
 }
 // a fila está vazia, basta resetar todas as marcações
 for(int j=0; j<numVertices; j++) // reset flags
 listaVertice[j].naoFoiVisitado();
 } // final método BFS 
Para exemplificar a pesquisa em largura, o programa em Java a se-
guir cria o grafo da figura 6 e executa a operação BFS. 
class ExemploBFS 
{ 
public static void main(String[] args) { // criação de um grafo simples
 Grafo g = new Grafo(); // criação do novo Grafo com até 20 vértices 
95Grafos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 Grafo g = new Grafo(); // criação do novo Grafo com até 20 vértices
 // inserção dos vértices
 g.adicVertice(″A″); // será índice 0
 g.adicVertice(″B″); // será índice 1
 g.adicVertice(″C″); // será índice 2
 g.adicVertice(″D″); // será índice 3
 g.adicVertice(″E″); // será índice 4
 g.adicVertice(″F″); // será índice 5
 g.adicVertice(″G″); // será índice 6
 // inserção das arestas
 g.adicAresta(0,1); // aresta AB
 g.adicAresta(0,2); // aresta AC
 g.adicAresta(0,3); // aresta AD
 g.adicAresta(1,4); // aresta BE
 g.adicAresta(4,6); // aresta EG
 g.adicAresta(2,5); // aresta CF
 g.adicAresta(2,3); // aresta CD
 System.out.print(″DFS - Vertices visitados: ″);
 g.BFS(); // pesquisa em profundidade
 System.out.println();
 } // final main 
} // final ExemploBFS 
O resultado apresentado na tela após a execução do programa é 
o seguinte: 
BFS - Vertices visitados: ABCDEFG 
A pesquisa em largura visita primeiramente todos os vértices que es-
tão a uma aresta de distância do vértice inicial, depois todos que estão 
a duas arestas de distância, e assim por diante. Sendo assim, essa pro-
priedade da pesquisa em largura é particularmente útil para determinar 
o caminho mais curto entre dois vértices (LAFORE, 2004). 
96 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
NA PRÁTICA 
Para encontrar exemplos completos de código Java associados a gra-
fos, basta consultar o capítulo 13 do livro Estrutura de dados e algoritmos 
em Java (LAFORE, 2004). 

Considerações finais 
Neste capítulo, foram apresentados os conceitos básicos de grafos 
e abordados exemplos de aplicações práticas representadas por grafos, 
bem como a implementação do TAD grafo junto às operações de cria-
ção do grafo e pesquisa dos vértices. 
Grafos são úteis para solucionar diversos tipos de problemas do 
cotidiano, e a implementação do TAD grafo é razoavelmente simples. 
Entretanto, a dificuldade está em entender os problemas e aplicar o mo-
delo baseado em grafos adequado para a solução do problema, o que 
requer grande capacidade de abstração, lógica e amadurecimento do 
profissional de computação. 
Referências 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013. 
LAFORE, Robert. Estrutura de dados e algoritmos em Java. Rio de Janeiro: 
Ciência Moderna, 2004. 
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. 
Estruturas de dados usando C. São Paulo: Makron Books, 1995. 
97 
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
Capítulo 7 
Grafos e 
multicaminhos 
Os grafos são estruturas formadas por vértices e arestas, que auxi-
liam na modelagem e resolução de problemas das mais diversas áreas 
do conhecimento. Os vértices possuem sempre uma identificação ou 
rótulo e estão associados a algum elemento do problema a ser mode-lado, uma cidade ou local no mapa, uma entrega de um projeto ou até 
uma peça no processo de montagem de um equipamento. As arestas 
conectam dois vértices e podem ser simples ou direcionadas, mas tam-
bém podem ser quantificadas por um valor ou peso, permitindo a repre-
sentação, por exemplo, de distâncias, custos e tempo. 
Neste capítulo, serão apresentados conceitos e técnicas associados 
a grafos que sustentam a solução de problemas com várias alternativas 
de caminhamento e determinam caminhos eficientes. 
98 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
1 Representação de multicaminhos por grafos 
Os vértices de um grafo podem representar diversos elementos do 
mundo real, por exemplo, as cidades existentes em uma determinada 
região, e as arestas, simples ou direcionadas, podem representar, por 
exemplo, as estradas que interligam essas cidades. 
Pode ocorrer de não existir uma estrada que ligue diretamente duas 
cidades, entretanto, outro caminho pode conectá-las passando por ou-
tras cidades. Existe a possibilidade de mais de um caminho possível en-
tre as duas cidades (multicaminhos), pois as estradas da região podem 
propiciar alternativas de caminhamento utilizando diferentes possibili-
dades que passam por outras cidades e que permitem a interligação 
entre elas. Além disso, as estradas podem ter características diferencia-
das de piso, limite de velocidade, pedágio, tipo de trajeto, direção única 
ou dupla e até mesmo algumas variáveis, como acidentes, quantidade 
de caminhões, de veículos, entre outros. 
Nesse contexto, o modelo utilizando grafos de um sistema viário 
requer recursos adicionais que permitam representar essas caracterís-
ticas, o que pode ser conseguido com o direcionamento e uma nova 
característica associada às arestas, denominada “peso”, que permite 
atribuir a definição de valores às arestas, podendo indicar distâncias, 
tempos, custos e outros valores (LAFORE, 2004). 
Nos grafos com todas as arestas direcionadas (setas indicativas), os 
dígrafos, a noção de alcançabilidade dos vértices é muito importante, 
sendo que a alcançabilidade trata dos elementos que podem ser aces-
sados em grafo partindo de um determinado ponto para chegar a outro 
ponto; ou seja, partindo de um vértice específico do grafo, é necessário 
determinar qual o caminhamento que permita alcançar outro vértice do 
grafo, sempre considerando o direcionamento das arestas (GOODRICH; 
TAMASSIA, 2013). 
99 Grafos e multicaminhos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
 
 
 
A figura 1 apresenta um exemplo de alcançabilidade em um dígrafo 
(grafo totalmente dirigido) que modela o transporte entre cidades utili-
zando rotas aéreas (as siglas representam aeroportos), no qual o vér-
tice BOS consegue alcançar o vértice LAX pelo caminho, passando por 
JFK e DFW. Entretanto, outro caminho poderia ser utilizado, passando 
pelo vértice MIA e alcançando LAX. 
Figura 1 – Dígrafo representando o transporte entre cidades 
SFO 
LAX 
ORD 
DFW 
MIA 
JFK 
BOS 
Fonte: adaptado de Goodrich e Tamassia (2013). 
Um dígrafo é considerado como sendo fortemente conectado quan-
do todos os seus vértices podem ser alcançados por um caminho, não 
importando o vértice inicial utilizado; ou seja, existe pelo menos um ca-
minho formado por arestas direcionadas que conecta quaisquer dois 
vértices do grafo. A figura 1 apresenta um dígrafo fortemente conectado. 
Observe que, partindo de qualquer cidade (vértice), é possível determinar 
um caminho de arestas dirigidas que alcance todas as outras cidades. 
Quando um caminho de um grafo forma um ciclo (partindo de um 
vértice, é possível voltar a esse mesmo vértice), esse caminho é deno-
minado “ciclo dirigido”. Novamente, tomando a figura 1 como exemplo, 
o caminho formado pelos aeroportos BOS e JFK é um ciclo dirigido. O 
outro caminho, entre os aeroportos ORD, MIA e LAX, é um ciclo dirigido 
100 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
do grafo. Um dígrafo acíclico é aquele que não possui ciclo dirigido. A 
figura 2 apresenta o grafo da figura 1 modificado para eliminar todos os 
ciclos dirigidos (GOODRICH; TAMASSIA, 2013). 
Figura 2 – Dígrafo sem ciclos dirigidos 
SFO 
LAX 
ORD 
DFW 
MIA 
JFK 
BOS 
Fonte: adaptado de Goodrich e Tamassia (2013). 
A noção de alcançabilidade em um dígrafo permite trabalhar com 
algoritmos e soluções para diversas propostas de problemas, por exem-
plo: determinar se um certo vértice do grafo atinge outro vértice espe-
cífico; encontrar o conjunto de vértices atingíveis a partir de um deter-
minado vértice; avaliar se um dígrafo é fortemente conectado ou não; 
determinar se um dígrafo é acíclico; realizar caminhamentos tanto em 
profundidade como em largura (GOODRICH; TAMASSIA, 2013). 
PARA SABER MAIS 
Para aprofundamento conceitual de técnicas de programação em Java 
para o tratamento da avaliação se um dígrafo é fortemente conectado, 
determinação se um dígrafo é acíclico e realização de caminhamentos 
em um dígrafo tanto em profundidade como em largura, procure a se-
ção 13.4 do livro Estrutura de dados e algoritmos em Java (GOODRICH; 
TAMASSIA, 2013). 
 
101 Grafos e multicaminhos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
Os dígrafos apresentados nas figuras 1 e 2 representam a modela-
gem simplificada de um sistema de transporte entre cidades, que, no 
caso real, certamente seria composto por centenas de vértices e ares-
tas, sendo praticamente impossível identificar os ciclos e as alcançabili-
dades apenas com uma observação visual. Sendo assim, os algoritmos 
para cálculo sistemático de resultados são fundamentais para a aplica-
ção real de grafos. 
Continuando a análise do sistema de transporte entre cidades, além 
de obter as alcançabilidades e os vários caminhos existentes entre os 
vértices, outros problemas carecem de solução, por exemplo, saber 
qual o caminho mais curto, o trajeto mais econômico, e muitos outros. 
Portanto, é necessário incluir recursos adicionais aos grafos e con-
siderar um peso para cada aresta do grafo. Dessa forma, será possível 
armazenar informações como a distância entre os vértices, os custos 
de viagens, o esforço de uma tarefa, o número de pessoas envolvidas e 
outros dados pertinentes a cada tipo de aplicação. Os grafos pondera-
dos, que apresentam pesos diferenciados entre o conjunto de arestas, 
implicam estudo e desenvolvimento de algoritmos e técnicas diferen-
ciadas para viabilizar o tratamento sistemático na resolução de proble-
mas (LAFORE, 2004). 
O TAD grafo necessita, agora, tratar tanto das arestas dirigidas como 
dos pesos nas arestas. Algumas alterações precisam ser realizadas nas 
estruturas de armazenamento, principalmente na matriz de incidência, 
que precisa considerar essas mudanças. O quadro 1 apresenta uma 
matriz de incidência para o dígrafo da figura 2, com o conjunto de vérti-
ces {BOS, JFK,MIA, ORD, DFW, LAX, SFO} e as marcações de distância 
em milhas entre os aeroportos nas devidas posições da matriz. 
102 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
Tabela 1 – Matriz de incidência com arestas dirigidas e pesos 
AEROPORTOS BOS JFK MIA ORD DFW LA X SFO 
BOS 0 187 1.258 0 0 0 2.704 
JFK 0 0 1.090 0 1.584 0 2.933 
MIA 0 0 0 0 1.121 2.342 0 
ORD 0 0 0 0 802 0 0 
DFW 0 0 0 0 0 1.235 1.464 
LAX 0 0 0 0 0 0 0 
SFO 0 0 0 0 0 0 0 
Fonte: adaptado de Goodrich e Tamassia (2013). 
Um dos grandes potenciais oferecidos pelos grafos na resolução de 
problemas é a possibilidade de encontrar o caminho mais curto entre 
dois vértices. Essa solução é aplicável a vários problemas do nosso 
cotidiano, desde o uso de um GPS para encontrar a menor rota entre 
dois endereços, passando pelo roteamento de uma placa de circuito 
integrado, até a otimização do custo de equipes no desenvolvimento de 
projetos, que, apesar de tratar de custos, pode ser enquadrado na busca 
do menor caminho (LAFORE, 2004). 
2 Algoritmo de Dijkstra para determinar 
caminhos 
A busca sistemática em grafos não ponderados para encontrar to-
dos os vértices alcançáveis a partir de um vértice inicial pode ser re-
alizada por dois métodos básicos: a pesquisa em profundidade e a 
pesquisa em largura (GOODRICH; TAMASSIA, 2013). A pesquisa em lar-
gura é particularmente útil para determinar o caminho mais curto entre 
103 Grafos e multicaminhos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
dois vértices, entretanto, nesse método, o caminho é medido pela quan-
tidade de arestas entre os vértices, sem considerar o tamanho (ou peso) 
de cada aresta. 
O algoritmo publicado pelo holandês Edsger Dijkstra, em 1959, utiliza 
a representação baseada em matriz de adjacência de um grafo pon-
derado e permite encontrar o caminho mais curto entre um vértice ini-
cialmente selecionado e todos os demais vértices alcançáveis a partir 
desse vértice inicial (LAFORE, 2004). O algoritmo retorna o peso total 
do menor caminho entre os dois vértices, ou seja, a soma dos pesos de 
todas as arestas que formam o menor caminho. 
O algoritmo de Dijkstra tem semelhanças com a pesquisa em largu-
ra, pois sempre visita primeiro os vértices adjacentes, ou seja, os mais 
próximos ao vértice inicial, para depois visitar os mais distantes. No en-
tanto, em vez de apenas contar as arestas, o algoritmo armazena, para 
cada vértice visitado, uma estimativa de limite superior para o caminho 
mais curto e que inicialmente tem um valor muito grande, impossível 
de ser alcançado mesmo com a soma de todos os pesos do grafo, um 
valor entendido como infinito. Além dessa estimativa de limite superior, 
para cada vértice visitado, o algoritmo armazena a identificação do pai 
(ou predecessor) desse vértice no caminho percorrido, viabilizando a 
recuperação do caminho percorrido e eventuais correções e alterações 
no menor caminho. 
O processo de cálculo do menor caminho e o algoritmo apresenta-
do são resultado da adaptação do conteúdo do capítulo 14 de Lafore 
(2004) e começam marcando o vértice inicial como já fechado na lista 
de vértices (mesma lista utilizada na pesquisa em largura e utilizada 
a marcação de já visitado para esse fim). Cabe ressaltar que todos os 
menores caminhos partem do mesmo nó inicial e o conjunto desses 
caminhos se assemelha muito a uma árvore. Dessa forma, o algoritmo 
tenta buscar todos esses caminhos, que incialmente são desconheci-
dos, e, a cada iteração de acesso aos vértices adjacentes ainda não 
104 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
fechados, novas distâncias mínimas são estimadas e algumas são 
efetivadas, marcando o respectivo vértice como fechado. O algoritmo 
termina quando todos os vértices alcançáveis estão marcados como 
fechados. 
Para a implementação do cálculo do menor caminho, o TAD grafo 
receberá algumas melhorias e alterações, com a inclusão de dados e 
de uma nova operação, denominada “Menor Caminho”. O código Java a 
seguir apresenta a classe DistanciaEstimada, que tratará os dados as-
sociados à estimativa do limite superior para a distância e do pai do 
vértice visitado. 
public class DistanciaEstimada // classe trará a distância estimada do menor 
caminho 
{
 private int paiVertice; // pai atual do vértice
 private int distancia; // distância do início até o vértice
 public DistanciaEstimada(int p, int d) { //construtor
 this.paiVertice = p;
 this.distancia = d;
 }
 public void setDistancia( int d ) { // método para atribuir distância
 this.distancia = d;
 } 
public int getDistancia() { // método para retornar distância
 return this.distancia;
 }
 public void setPaiVertice(int p) { // método para atribuir pai do vértice
 this.paiVertice = p;
 }
 public int getPaiVertice() { // método para retornar o pai do vértice
 return this.paiVertice;
 } 
} // final classe DistanciaEstimada 
105 Grafos e multicaminhos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
A classe Grafo precisa, agora, armazenar todas as menores distân-
cias, que inicialmente serão as distâncias estimadas. Com o andamen-
to do algoritmo, essas estimativas serão efetivadas como as menores 
distâncias entre o vértice inicial e cada um dos demais vértices do 
grafo. A seguir, temos o código em Java com os campos necessários e 
o construtor da classe. 
class Grafo // implementação da classe Grafo 
{ 
private final int MAX_VERTICES = 20; // número máximo de vértices
 private final int INFINITO = 1000000; // número muito grande
 private Vertice listaVertice[]; // lista de vértices
 private int matriz[][]; // matriz adjacente
 private int numVertices; // número atual de vértices
 private int numFechados; // número de vértices com distância fechada
 private DistanciaEstimada menor[]; // vetor com o caminho mais curto
 private int verticeAtual; // vértice atual
 private int distParaAtual; // distância para o vértice atual
 public Grafo() { // construtor da clase Grafo
 listaVertice = new Vertice[MAX_VERTICES]; // cria a lista de vértices
 matriz = new int[MAX_VERTICES][MAX_VERTICES]; // cria a matriz adjacente
 numVertices = 0; // inicia número de vértices como 0
 numFechados = 0; // inicia com nenhum vértice fechado
 for(int y=0; y<MAX_VERTICES; y++) { // inicia matriz com valor infinito
 for(int x=0; x<MAX_VERTICES; x++) {
 matriz[x][y] = INFINITO;
 }
 }
 menor = new DistanciaEstimada[MAX_VERTICES];
 }// final construtor 
A classe Grafo possui alguns campos adicionais: o campo menor é 
um vetor criado para armazenar a menor distância estimada para cada 
um dos vértices do grafo; o campo numFechados armazena quantos 
vértices já tiveram o cálculo de distância fechado, ou seja, a menor dis-
tância deixou de ser estimada para ser definitiva; o campo verticeAtual 
106 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
uno 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 
 
 
marcará o vértice que está sendo avaliado a cada iteração do algorit-
mo; o campo distParaAtual armazenará a soma dos pesos das arestas 
percorridas até o vértice atual, dado útil para preencher a distância es-
timada do vértice atual ao vértice inicial. O construtor inicializa a matriz 
de adjacência com todas as posições inicializadas com valor infinito 
(não mais com o valor 0), que indicará que a aresta marcada com infini-
to não está presente no grafo. A constante INFINITO é suficientemente 
maior que qualquer distância a ser calculada. 
Antes de apresentar a operação para cálculo do menor caminho 
do TAD grafo, três métodos auxiliares são importantes: um para en-
contrar no vetor com as distâncias estimadas o vértice que ainda não 
foi fechado e que esteja com a menor distância calculada até o mo-
mento, outro para ajustar o vetor com as distâncias estimadas após 
a visita a um determinado vértice (será explicado com mais detalhes 
após a apresentação do código Java), e o último, que exibe todo o 
conteúdo do vetor com as distâncias estimadas. Lembrando que, 
na classe Grafo, o vetor com as distâncias estimadas foi declarado 
como menor. O código Java a seguir apresenta esses três métodos: 
pegaMinimo, ajustaMenor e mostraMenor. 
private int pegaMinimo() { // pega o índice com a menor distância
 int minimo = INFINITO; // inicia o mínimo
 int indice = 0;
 for (int j=1;j<numVertices;j++) { // acessa cada vértice
 if (!listaVertice[j].getVisitado() && menor[j].getDistancia()<minimo) 
{
 // se for menor que o anterior, marca como menor
 minimo = menor[j].getDistancia();
 indice = j;
 }
 }
 return indice;
 } // final pegaMinimo
 private void ajustaMenor() { // ajusta o vetor com os caminhos mais curtos 
107Grafos e multicaminhos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 int coluna = 1; // pula o vértice inicial
 while (coluna < numVertices) { // percorre as colunas
 if (listaVertice[coluna].getVisitado()) { 
// se vértice já está fechado, pula a coluna
 coluna++;
 continue;
 }
 // calcula a distância para uma entrada de menor[]
 int atualParaMargem = matriz[verticeAtual][coluna];
 int inicioParaMargem = distParaAtual+atualParaMargem;
 int menorDistancia = menor[coluna].getDistancia();
 if (inicioParaMargem < menorDistancia) {
 menor[coluna].setPaiVertice(verticeAtual);
 menor[coluna].setDistancia(inicioParaMargem);
 }
 coluna++;
 }
 } // final ajustaMenor
 private void mostraMenor() { // mostra o menor caminho encontrado
 for(int j=0;j<numVertices;j++) { // mostra o conteúdo de menor[]
 System.out.print(listaVertice[j].getRotulo() + ″=″);
 if (menor[j].getDistancia() == INFINITO) {
 System.out.print(″inf″);
 }else{
 System.out.print(menor[j].getDistancia());
 }
 String pai = (String) listaVertice[menor[j].getPaiVertice()]. 
getRotulo()
 System.out.print(″(″ + pai + ″) ″);
 }
 System.out.println(″″);
 } // final mostraMenor 
O método ajustaMenor inclui um conceito adicional necessário para 
a implementação do algoritmo, que é o conceito de margem do pro-
cesso de pesquisa. Os vértices do grafo podem estar em três estados 
diferentes durante o processo de busca do menor caminho: vértice fe-
chado, quando a distância até o vértice inicial já foi calculada e definida; 
vértice ainda não visitado e ainda com informação de distância com 
valor infinito; vértice na margem do processo de pesquisa, no caso de 
108 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
vértices que já foram visitados e possuem uma estimativa de menor ca-
minho armazenado no vetor de distâncias estimadas, mas ainda podem 
sofrer alteração, pois novos vértices visitados podem originar caminhos 
mais curtos. O método ajustaMenor percorre o vetor com as distâncias 
estimadas (menor), pulando aqueles vértices que já estão fechados (in-
dicação de já visitado na matriz de adjacências) e recalculando a menor 
distância do vértice inicial até o vértice que está na margem do proces-
so. Se o novo valor for menor que o valor anteriormente armazenado, 
efetua a substituição pelo novo valor. 
Por fim, o código em Java a seguir apresenta o método público 
menorCaminho, responsável pelo cálculo dos menores caminhos entre 
o vértice inicial e cada um dos vértices alcançáveis do grafo ponderado, 
representado na matriz de adjacências. 
public void menorCaminho() { // encontra o menor caminho
 int inicio = 0; // começa pelo vértice 0
 listaVertice[inicio].foiVisitado(); // primeiro vértice marcado como fechado
 numFechados = 1; // inclui o vértice inicial como fechado 
for(int j=0;j<=numVertices;j++) { // transfere as distâncias para o vetor menor
 // distância armazenada na matriz de adjacências
 int distancia = matriz[inicio][j];
 // pai recebe inicio=0 e a distância
 menor[j] = new DistanciaEstimada(inicio,distancia);
 } 
while( numFechados < numVertices ) { // até que todos os vértices estejam fechados
 // sempre trata o mínimo do vetor menor
 int indiceParaMinimo = pegaMinimo();
 // pega a distância mínima
 int minimaDistancia = menor[indiceParaMinimo].getDistancia();
 if(minimaDistancia == INFINITO) { // existe vértice não encontrado
 // só ocorre quando todos os vértices alcançáveis são fechados
 // e ainda existem vértices
 System.out.println(″Existem vértices não endereçados″);
 break; // termina o loop while 
109Grafos e multicaminhos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 } else { // vai redefinir o verticeAtual
 // passa a ser o vértice mais próximo a ser fechado
 verticeAtual = indiceParaMinimo;
 distParaAtual = menor[indiceParaMinimo].getDistancia(); // distância mínima
 }
 listaVertice[verticeAtual].foiVisitado(); // marca vértice atual como fechado
 numFechados++; // incrementa o número de vértices fechados
 ajustaMenor();
 }
 mostraMenor(); // mostra o conteúdo de menor[]
 numFechados = 0; 
// limpa o número de vértices 
fechados para a próxima busca
 for(int j=0; j<numVertices; j++) // reset flags
 listaVertice[j].naoFoiVisitado();
 } // final método menorCaminho 
O método pode ser tratado em três etapas distintas: inicialização, 
iteração e finalização. Na inicialização do método, o vértice 0 da lista 
de vértices é considerado o vértice inicial e marcado como fechado (já 
visitado), a contagem de vértices fechados é inicializada, e o vetor com 
as distâncias estimadas (menor) é carregado com as distâncias dos 
nós adjacentes ao vértice inicial. 
Na iteração, está a base do algoritmo, sendo que a repetição ocorre 
até que todos os vértices estejam marcados como fechados. Para cada 
repetição, é sempre tratado o vértice mais próximo ao inicial que ainda 
não esteja fechado (chamada ao método pegaMinimo), e, caso todos 
os vértices alcançáveis tenham sido fechados, a iteração termina. Em 
seguida, o vértice mais próximo encontradono início que já possui o 
menor caminho é fechado, e o ajuste do vetor com as distâncias esti-
madas é realizado, visando refletir esse novo vértice fechado. 
Terminada a iteração com todos os vértices fechados, o vetor com 
as distâncias mínimas agora fechadas é exibido, e os dados são prepa-
rados para uma eventual nova chamada do método. 
110 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
Para exemplificar o funcionamento do algoritmo, utilizaremos o grafo 
da figura 3, representando as ligações de transporte entre sete cidades 
genéricas, de Cid1 a Cid7, sendo que Cid1 é o ponto inicial (vértice A), 
com as arestas indicando o sentido de ligação e os pesos indicando as 
distâncias em quilômetros entre as cidades. Observe que as cidades 
Cid6 e Cid7 (vértices F e G) estão conectadas entre si, mas não podem 
ser alcançadas de Cid1. 
Figura 3 – Dígrafo representando ligações entre cidades 
Cid2 Cid3 
A 
B 
Cid1 
Cid4 Cid5 
D 
C 
50 
60 
50 
80 20 
70 
90 40 
E 
Cid6 Cid7 
20
F G 
Fonte: adaptado de Lafore (2004). 
O código a seguir apresenta o programa em Java que cria o grafo da 
figura 3 e executa o método do menor caminho. 
class ExemploMenorCaminho 
{
 public static void main(String[] args){
 Grafo g = new Grafo();
 g.adicVertice(″A″); // 0 (início)
 g.adicVertice(″B″); // 1
 g.adicVertice(″C″); // 2
 g.adicVertice(″D″); // 3
 g.adicVertice(″E″); // 4
 g.adicVertice(″F″); // 5
 g.adicVertice(″G″); // 6 
111Grafos e multicaminhos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 g.adicAresta(0, 1, 50); // AB 50
 g.adicAresta(0, 3, 80); // AD 80
 g.adicAresta(1, 2, 60); // BC 60
 g.adicAresta(1, 3, 90); // BD 90
 g.adicAresta(2, 4, 40); // CE 40
 g.adicAresta(3, 2, 20); // DC 20
 g.adicAresta(3, 4, 70); // DE 70
 g.adicAresta(4, 1, 50); // EB 50
 g.adicAresta(5, 6, 20); // FG 20
 System.out.println(″Menor Caminho″);
 g.menorCaminho();
 System.out.println();
 } // final main() 
} // final classe ExemploMenorCaminho 
A execução do programa resulta no conjunto de todas as menores 
distâncias entre o vértice A e os demais vértices do grafo. 
Menor Caminho 
Existem vértices não endereçados 
A=inf(A) B=50(A) C=100(D) D=80(A) E=140(C) F=inf(A) G=inf(A) 
Observe que o caminho de A para A é infinito, pois não tem razão de 
ser calculado. Tomando como exemplo, E=140(C) indica que o menor 
caminho partindo de A e chegando a E é de 140 unidades, que, antes 
de chegar, passou em C (pai), mas o resultado anterior C=100(D) forne-
ce os dados para a definição completa do menor caminho entre A e E 
(figura 4), ou seja: início em A, distância 80 até D, distância 20 até C, 
distância 40 até E e soma total igual a 80 + 20 + 40 = 140. 
112 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
Figura 4 – Indicação no grafo do menor caminho entre A e E 
Cid2 Cid3 
A 
B 
Cid1 
Cid4 Cid5 
D 
C 
50 
60 
50 
80 20 
70 
90 40 
E 
Cid6 Cid7 
20
F G 
 
 
 
Fonte: adaptado de Lafore (2004). 
Considerações finais 
Neste capítulo, foram apresentados os grafos ponderados, nos 
quais valores podem ser atribuídos às arestas, possibilitando uma 
significativa expansão nos tipos de problema a serem modelados e 
solucionados por grafos. 
O algoritmo de Dijkstra foi apresentado, junto a uma proposta de 
implementação em Java que trata o problema da determinação do 
menor caminho entre dois vértices em um grafo ponderado. O algorit-
mo, além de ser aplicável a diversos problemas cotidianos, possui um 
grau de complexidade razoável e exercita elementos de programação e 
computação fundamentais para a formação de bons profissionais de 
computação. 
Referências 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013. 
LAFORE, Robert. Estrutura de dados e algoritmos em Java. Rio de Janeiro: 
Ciência Moderna, 2004. 
113 
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
Capítulo 8 
Eficiência 
assintótica de 
algoritmos 
Na solução de problemas utilizando estruturas de dados, o progra-
mador deve estar atento aos aspectos de eficiência dos algoritmos em-
pregados, considerando sempre as restrições impostas quanto a me-
mória, processamento e esforço de desenvolvimento. 
Neste capítulo, serão tratados aspectos voltados a análise da com-
plexidade de algoritmos recursivos e não recursivos, visando oferecer 
instrumentos de comparação da eficiência dos algoritmos empregados 
nas soluções de problemas. 
114 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
1 Eficiência dos algoritmos recursivos e não 
recursivos aplicados às estruturas estudadas 
A capacidade de processamento e a quantidade de memória disponí-
vel nos equipamentos de computação vêm crescendo constantemente; 
com isso, diversas limitações e restrições encontradas no passado já 
não existem mais. Atualmente, um simples smartphone – plenamente 
acessível a grande parte dos usuários – oferece recursos de proces-
samento e armazenamento que sustentam a utilização de aplicativos 
sofisticados e complexos, além de permitir, de forma transparente e 
simplificada, o acesso a recursos quase ilimitados de processamento 
nas nuvens (cloud), devido ao crescente grau de conectividade. 
Entretanto, as necessidades dos usuários também passam a ser 
cada vez mais complexas, devido, principalmente, a exigências voltadas 
à experiência de uso, que se tornam cada vez mais marcantes, além da 
necessidade imperativa de integração entre as diversas soluções ofere-
cidas, não deixando de lado a possível questão mais delicada: o enor-
me volume de dados disponível e a crescente facilidade em amostrar 
novos dados. 
Nesse contexto, um programador que esteja desenvolvendo siste-
mas de computação, não importando se é um aplicativo para celular ou 
um artefato mecatrônico voltado à Internet das Coisas (IoT), deve estar 
atento a aspectos de eficiência – na maioria das vezes, conflitantes e 
antagônicos – na tomada de decisão sobre o tipo de solução mais ade-
quada para cada problema, sendo que: 
[...] três dos mais importantes aspectos incluem o tempo que 
será gasto pelo programador ao codificar determinado programa, 
o tempo de máquina necessário para executar o programa e o 
espaço necessário para o programa. (TENENBAUM; LANGSAM; 
AUGENSTEIN, 1995, p. 412) 
115 Eficiência assintótica de algoritmos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilhamento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
Considerando que um algoritmo é um procedimento definido capaz 
de realizar uma tarefa dentro de um intervalo de tempo específico e que 
a estrutura de dados é uma forma sistemática destinada ao acesso e 
organização dos dados, entendemos que esses são conceitos funda-
mentais em sistemas computacionais. Para o desenvolvimento de um 
bom projeto, é necessário que haja a alocação do algoritmo e da es-
trutura de dados adequados, sendo necessário definir uma forma de 
comparar e classificar os diversos algoritmos e tipos de estrutura de 
dados, visando sempre à escolha mais eficiente e aderente para a solu-
ção do problema que deve ser resolvido por um sistema computacional 
(GOODRICH; TAMASSIA, 2013). 
O tempo de execução de uma determinada solução é importante, 
sendo uma medida associada à qualidade do sistema. O tempo de exe-
cução de um algoritmo é crescente em relação ao tamanho do con-
junto de dados avaliado, mesmo considerando a possível variabilidade 
no ambiente de execução do sistema a ser desenvolvido em função da 
diversidade de recursos de hardware e de sistemas operacionais dis-
poníveis no mercado. Considerando que o crescimento do volume de 
dados é uma característica marcante nos sistemas contemporâneos e 
que o tempo de execução continua sendo um recurso precioso. É funda-
mental definir uma maneira ou método de caracterizar a performance 
de execução de uma solução de programação em função do volume 
de dados de entrada, visando oferecer instrumentos para a tomada de 
decisão quanto aos melhores algoritmos empregados no desenvolvi-
mento de sistemas computacionais (GOODRICH; TAMASSIA, 2013). 
Uma abordagem para a obtenção de um método de medida de efici-
ência de algoritmos, visando à escolha entre possíveis soluções, seria 
baseada em estudos experimentais avaliando o tempo de execução de 
uma solução aplicada a diversos conjuntos de dados e contabilizando 
o tempo real consumido a cada amostra (TENENBAUM; LANGSAM; 
AUGENSTEIN, 1995). 
116 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
Nesse processo experimental para determinar uma possível depen-
dência entre o tempo de execução e o volume de dados, faz-se necessá-
rio realizar diversos experimentos sobre amostras de dados diferencia-
das por meio de uma análise baseada em elementos gráficos e cálculos 
estatísticos, tanto em conjuntos de dados como no tamanho desses 
conjuntos, buscando afirmações razoáveis quanto ao tempo de execu-
ção de uma solução em função do tamanho dos dados. 
Esse processo experimental pode ser aplicado para a medida de efi-
ciência de algoritmos, mas apresenta grandes limitações, por exemplo 
(GOODRICH; TAMASSIA, 2013): 
• Os experimentos são realizados sobre um conjunto fixo de dados, 
deixando outros, que podem ser importantes, de fora da análise. 
• Dificuldade na comparação de algoritmos, quando considerados 
ambientes computacionais distintos. 
• Necessidade de implementar o sistema para realizar o 
experimento. 
Outra abordagem está associada à determinação de uma função 
matemática 𝑓(𝑛) que caracterize o tempo de execução de um algoritmo 
em função do tamanho 𝑛 do conjunto de dados, possibilitando descar-
tar entradas de dados, comparar a eficiência de solução sem conside-
rar o ambiente computacional e permitir a comparação entre algorit-
mos, mesmo sem a implementação completa da solução (GOODRICH; 
TAMASSIA, 2013). 
Essa abordagem é denominada “análise assintótica de algoritmos” 
e consiste em analisar um algoritmo e determinar, com base nas ope-
rações envolvidas na sua implementação, uma função matemática que 
represente o tempo de execução do algoritmo em função do tamanho 
do conjunto de dados, e encontrar uma outra função matemática básica 
e bem conhecida (constante, quadrática, exponencial, entre outras) que 
117 Eficiência assintótica de algoritmos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
se aproxime o melhor possível (de forma assintótica) da função definida 
para o algoritmo. 
Para apresentar informalmente essa abordagem matemática, será 
tratado um problema interessante de programação: a obtenção do valor 
resultante de um número 𝑥 elevado a uma potência 𝑛, ou seja, o cál-
culo da função 𝑝(𝑥, 𝑛) = 𝑥𝑛, para todo 𝑛 inteiro e não negativo. O algo-
ritmo para cálculo dessa função pode ser recursivo e definido assim 
(GOODRICH; TAMASSIA, 2013): 
 
 
 
1 se 𝑛𝑛 � 0
𝑝𝑝(𝑥𝑥, 𝑛𝑛) = � 𝑥𝑥 ∙ 𝑝𝑝(𝑥𝑥, 𝑛𝑛 � 1) se 𝑛𝑛 � 0 
O código em Java a seguir apresenta um método que implementa 
essa solução. 
public static double potencia1(double x, int n) { // função potência 1
 if (n <= 0) {
 return 1;
 }else{
 return x*potencia1(x,n-1);
 }
 } // final método potencia1 
Analisando de forma livre essa solução de implementação, nota-se 
facilmente que o comando condicional e o cálculo 𝑥*potencia1(𝑥, 𝑛 – 1) 
são executados 𝑛 vezes, ou seja, essa solução tem um tempo seme-
lhante (ou assintótico) a uma função linear 𝑓(𝑛) = 𝑛. 
Uma segunda forma recursiva para esse mesmo cálculo, um pouco 
menos intuitiva, mas que pode ser facilmente comprovada, é a seguinte: 
 
 
 
1 se � 0 
( , ) = � ( , ( – 1)/2)² se é ímpar 
( , ( – 1)/2)² se é par 
118 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 
 
 
 
 
 
 
O código em Java a seguir apresenta um método que implementa 
essa solução. 
public static double potencia2(double x, int n) { // função potência 2
 if (n <= 0) {
 return 1;
 }else{
 double y;
 if (n % 2 != 0) { //n é ímpar
 y = potencia2(x,(n-1)/2);
 return x*y*y;
 }else{ // n eh par
 y=potencia2(x,n/2);
 return y*y;
 }
 }
 } // final método potencia2 
Apesar de o código ser mais longo e aparentemente ter mais ope-
rações, observe que a chamada recursiva sempre divide o expoente 𝑛 
por dois, tanto quando é ímpar como quando é par, reduzindo significa-
tivamente o número de chamadas recursivas. Esse comportamento de 
divisão das operações por dois concede a esse algoritmo uma caracte-
rística matemática semelhante a uma função logarítmica (𝑙𝑜𝑔 𝑛) e pode 
ser comprovado matematicamente que é significativamente melhor que 
a função linear obtida na solução anterior (GOODRICH; TAMASSIA, 2013). 
A análise assintótica de algoritmos utiliza como base a Notação O 
(ou ordem de grandeza), na qual, dadas duas funções, 𝑓(𝑛) e 𝑔 (𝑛) , 𝑓(𝑛) 
é da ordem de 𝑔 (𝑛) ou 𝑓(𝑛) e 𝘖(𝑔 (𝑛) ) , se existirem dois valores intei-
ros positivos 𝑎 e 𝑏, tais que 𝑓(𝑛) é menor que 𝑎 . 𝑔 (𝑛) para todo 𝑛 > 𝑏. 
Para exemplificar a notação, seja em uma função 𝑓(𝑛) = 𝑛2 + 50 . 𝑛 e 
𝑔 (𝑛) = 𝑛2 . 𝑎 = 2 e 𝑏 = 50, a função 𝑓(𝑛) será da ordem de 𝑔 (𝑛) , ou seja, 
𝑛2 + 50𝑛 é da ordem 𝑛2, pois, para todo 𝑛 > 50, o resultado de 𝑓(𝑛) é sem-
pre menor que 2 . 𝑔 (𝑛) (TENENBAUM; LANGSAM; AUGENSTEIN, 1995). 
119 Eficiência assintótica de algoritmos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente.Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
O quadro 1 apresenta os dados associados ao exemplo anterior. 
Observe que, enquanto 𝑛 permanece menor que 𝑏 = 50, a função 𝑔 (𝑛) , 
multiplicada por 𝑎 = 2, também é menor. Entretanto, quando 𝑛 assume 
um valor maior que 𝑏, 𝑔 (𝑛) apresenta um valor sempre maior que 𝑓(𝑛) . 
Tabela 1 – Dados associados à análise assintótica 
n f(n) = n2 + 50 . n g(n) = n2 a b a . g(n) 
1 51 1 2 50 2 
2 104 4 2 50 8 
3 159 9 2 50 18 
4 216 16 2 50 32 
5 275 25 2 50 50 
6 336 36 2 50 72 
7 399 49 2 50 98 
8 464 64 2 50 128 
9 531 81 2 50 162 
10 600 100 2 50 200 
------ ------ ------ ------ ------ ------
------ ------ ------ ------ ------ ------
45 4275 2025 2 50 4050 
46 4416 2116 2 50 4232 
47 4559 2209 2 50 4418 
48 4704 2304 2 50 4608 
49 4851 2401 2 50 4802 
50 5000 2500 2 50 5000 
51 5151 2601 2 50 5202 
52 5304 2704 2 50 5408 
A utilização dos conceitos associados à análise assintótica e à nota-
ção de ordem de grandeza oferece uma poderosa ferramenta para com-
paração de algoritmos, pois, uma vez definida a função matemática que 
caracteriza um determinado algoritmo, esta pode ser enquadrada em 
120 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
 
 
 
um limitante superior de eficiência definido por uma outra função ma-
temática básica e com características de eficiência conhecidas. São 
sete as principais funções matemáticas básicas aplicáveis nesse caso 
(GOODRICH; TAMASSIA, 2013): 
• Função constante: 𝑓(𝑛) = c. Esta é a mais simples das funções 
básicas, e não importa qual o tamanho do conjunto de dados. O 
tempo de execução do algoritmo será sempre um valor constan-
te, e, na análise de algoritmos, é aplicada para caracterizar o tem-
po de execução de operações básicas como atribuições e com-
parações. No gráfico 1, a função constante utilizada é 𝑓(𝑛) = 1. 
• Função logaritmo: 𝑓(𝑛) = 𝑙𝑜𝑔 𝑏𝑎s𝑒𝑛. Com o valor da base sempre 
maior que 1, esta é uma das funções mais encontradas na análise 
de algoritmos, e o seu crescimento é o menor de todas as outras 
funções. No gráfico 1, a função logaritmo utiliza a base 2, ou seja, 
𝑓(𝑛) = 𝑙𝑜𝑔 2𝑛. 
• Função linear: 𝑓(𝑛) = 𝑛. Esta é uma função associada a algorit-
mos que executam apenas uma operação básica para o tratamen-
to de cada um dos 𝑛 elementos e apresenta um crescimento um 
pouco acima do apresentado pela função logaritmo (gráfico 1). 
• Função n-log-n: 𝑓(𝑛) = 𝑛 . 𝑙𝑜𝑔 2𝑛. Nesta função, o logaritmo é mul-
tiplicado pelo valor 𝑛, definindo um crescimento do tempo de exe-
cução mais acentuado (gráfico 1). 
• Função quadrática: 𝑓(𝑛) = 𝑛2. Esta é uma função, assim como a 
função logaritmo, muito comum na análise de algoritmos, princi-
palmente em algoritmo com vários laços de repetição aninhados, 
e seu crescimento é mais acentuado, superando em muito as fun-
ções apresentadas anteriormente (gráfico 1). 
• Função cúbica: 𝑓(𝑛) = 𝑛3. Semelhante à função quadrática com 
crescimento do tempo de execução significativamente mais 
121 Eficiência assintótica de algoritmos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
acentuado que as demais (gráfico 1), mas não muito comum na 
análise de algoritmos. 
• Função exponencial: 𝑓(𝑛) = 𝑏𝑛, onde 𝑏 > 0, sendo 2 a base mais 
comum. Como observado no gráfico 1, o crescimento dessa fun-
ção é o mais acentuado e, quando é considerado na análise de 
algoritmos, incorre em sérios problemas de eficiência que devem 
sempre ser considerados e evitados. 
O gráfico 1 apresenta a comparação de crescimento das sete fun-
ções básicas em relação ao crescimento do tamanho 𝑛 do conjunto de 
dados. De um modo geral, seria desejável que as operações básicas 
aplicadas às de estruturas de dados fossem executadas em tempos 
comparáveis (ordem de grandeza) à função constante ou à função lo-
garitmo; os algoritmos mais complexos fossem realizados em tempos 
lineares ou até 𝑛-𝑙𝑜𝑔 -𝑛; os algoritmos com ordem de grandeza exponen-
cial podem ser impraticáveis e devem sempre receber especial atenção 
para melhorias e busca de técnicas mais eficientes de implementação; 
os algoritmos comparáveis às funções quadrática e cúbica podem tam-
bém resultar em problemas, mas podem ocorrer. 
Gráfico 1 – Crescimento das sete funções básicas da análise assintótica (escala logarítmica) 
1,E+00 
1,E+05 
1,E+10 
1,E+15 
1,E+20 
1,E+25 
1,E+30 
1,E+35 
1,E+40 
1,E+45 
1,
E+
00
1,
E+
01
1,
E+
02
1,
E+
03
1,
E+
04
1,
E+
05
1,
E+
06
1,
E+
07
1,
E+
08
1,
E+
09
1,
E+
10
1,
E+
11
1,
E+
12
1,
E+
13
1,
E+
14
1,
E+
15
 
G F 
E 
D 
C 
B 
A 
A Constante B Log C Linear D n-log-n E Quadrática F Cúbica G Exponencial 
Fonte: adaptado de Goodrich e Tamassia (2013). 
122 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
PARA SABER MAIS 
Para um apr ofundamento conceitual sobre as características, pro-
priedades e definições das funções matemáticas básicas, procure a 
seção 4.1 do livro Estrutura de dados e algoritmos em Java (GOODRICH; 
TAMASSIA, 2013). 
 
A análise de tempo de execução de um algoritmo associado a uma 
estrutura de dados (por exemplo, uma inserção, remoção ou busca) 
pode ser realizada diretamente sobre a especificação em alto nível do 
algoritmo ou pseudocódigo. A análise pode ser feita baseada nas ope-
rações primitivas empregadas na construção do algoritmo, ficando in-
dependente do hardware, sistema operacional ou linguagem de progra-
mação utilizados na implementação. 
Um conjunto de operações primitivas pode ser definido, no qual cada 
uma das operações primitivas apresenta um tempo de execução cons-
tante, definido e que permite a contagem de quantas operações são 
realizadas no algoritmo, eliminando a necessidade de calcular o tempo 
específico do algoritmo, pois a ideia é comparar diversas soluções (ou 
algoritmos), e, como todas estarão sendo contadas com a mesma regra 
(quantidade de operações primitivas), a melhor eficiência fica para a so-
lução com menor contagem. Para simplificar o processo, pois o objetivo 
é obter uma ordem de grandeza, os tempos de execução de operações 
primitivas diferentes serão considerados sempre similares. Um con-
junto de operações primitivas pode ser da seguinte forma (GOODRICH; 
TAMASSIA, 2013): 
• Atribuição de variável. 
• Chamada de funções. 
• Operações aritméticas. 
• Comparações de valores. 
123 Eficiência assintótica de algoritmos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
• Acesso a variáveis estruturadas (arranjos). 
• Apontamentos de variáveis. 
• Retorno de funções. 
O conjunto de dados utilizado como entrada para um algoritmo pode 
apresentar características que privilegiem uma determinada solução 
e prejudiquem outra. Nesse sentido, para disciplinar a comparação, 
utiliza-se sempre a análisedo pior caso, ou seja, considerar o tempo de 
execução sempre para o pior caso, condição que pode ser detectada de 
forma mais simples analisando o algoritmo. Cabe destacar que, para 
um algoritmo apresentar bom desempenho para o pior caso de conjun-
to de dados de entrada, geralmente as demais entradas também serão 
executadas de forma eficiente (GOODRICH; TAMASSIA, 2013). 
Na prática, a determinação da função assintótica 𝑔 (𝑛) (notação or-
dem) que caracteriza o pior caso do tempo de execução de um algorit-
mo requer um entendimento do algoritmo e dos fundamentos matemá-
ticos, entretanto, diversos algoritmos associados à estrutura de dados 
já foram estudados e estão disponibilizados na literatura. 
A análise assintótica dos tempos de execução pode ser aplicada a 
uma estrutura de dados pilha, utilizando um vetor em memória e ofere-
cendo as operações push, pop, topo, tamanho e estaVazia. Observe que 
todas essas operações são implementadas com operações simples 
(atribuição, operação aritmética, comparação de valores, entre outras) 
que demandam tempo constante de execução, sendo assim, uma pilha 
implementada na forma de vetor tem o tempo de execução 𝑂(1) , ou 
seja, os algoritmos que implementam as operações do TAD pilha po-
dem ser considerados todos com tempo de execução de ordem cons-
tante e, consequentemente, são muito eficientes. 
Entretanto, a implementação de pilha utilizando vetores possui res-
trições, pois o número de elementos está limitado à declaração inicial 
124 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
 
 
 
 
do tamanho do vetor. A implementação utilizando a lista ligada resolve 
esse problema, pois é independente do tamanho do conjunto de en-
trada e praticamente ilimitado (definido pela quantidade de memória 
disponível). Nessa solução do TAD pilha, baseada em lista ligada com 
a inserção e remoção no início da lista, os tempos das operações tam-
bém são constantes 𝑂(1) , ou seja, de ordem constante (GOODRICH; 
TAMASSIA, 2013). 
Uma lista ou sequência de valores ordenados também pode ter 
a implementação baseada em uma lista ligada e conta com as ope-
rações tamanho, estaVazia, pegaValor, setaValor, adiciona e remove. 
Analogamente à análise dos tempos de execução realizada para a estru-
tura pilha, as operações tamanho e estaVazia possuem algoritmos basea-
dos em operações simples e sem repetição, ou seja, logo são constantes. 
No entanto, as demais operações (pegaValor, setaValor, adiciona e 
remove) necessitam buscar um elemento dentro da lista para ser con-
cluídas. No pior caso, podem percorrer a lista toda, com 𝑛 elementos 
para encontrá-lo. Sendo assim, essas operações do TAD sequencia 
apresentam tempo de execução 𝑂(𝑛) , ou seja, de ordem linear. 
A análise da eficiência dos algoritmos associados a árvores binárias 
pode ser aplicada à operação de caminhamento pré-fixado. O código 
em linguagem Java dessa operação está listado a seguir. 
private void preFixado(No atual) // caminhamento pré-fixado da árvore binária
 {
 if (atual != null) {
 System.out.println("Id: "+atual.getId()+" Elemento: "+atual.getElemento());
 preFixado(atual.getEsq());
 preFixado(atual.getDir());
 }
 } // final método preFixado 
125 Eficiência assintótica de algoritmos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
 
 
 
 
O algoritmo é recursivo e percorre a árvore binária completamente, 
ou seja, se a árvore tem 𝑛 nós, o tempo de execução será sempre igual 
a 𝑛, logo o tempo de execução é 𝑂(𝑛) . 
Para a análise da eficiência assintótica do algoritmo de Dijkstra para 
determinação do caminho mais curto entre os vértices de um grafo, 
assume-se um grafo com 𝑛 vértices e 𝑚 arestas e que as operações 
para somar e comparar os pesos das arestas podem são realizadas em 
tempo constante (GOODRICH; TAMASSIA, 2013). 
Para a análise desse algoritmo, é necessário definir os tipos de estru-
tura de dados que serão utilizados na implementação. As arestas serão 
representadas por uma lista de adjacências, que permite percorrer os 
adjacentes a um determinado vértice em tempo proporcional ao núme-
ro de adjacentes. Já a lista de valores, na qual são armazenados os 
menores caminhos parciais, a implementação não será em um simples 
vetor, mas, sim, em uma árvore binária, na qual o menor rótulo pode 
ser obtido com um tempo 𝑂(𝑙𝑜𝑔 . 𝑛) , ou seja, da ordem da função 𝑙𝑜𝑔 𝑛 
(GOODRICH; TAMASSIA, 2013). 
Por fim, de acordo com Goodrich e Tamassia (2013), a análise as-
sintótica para o algoritmo de Dijkstra utilizando essas estruturas (lista 
de adjacências e árvore binária) é 𝑂((𝑛 + 𝑚) . 𝑙𝑜𝑔 . 𝑛) , ou seja, para um 
grafo com 𝑛 vértices e 𝑚 arestas, a obtenção dos menores caminhos 
partindo de um determinado vértice tem o tempo de execução limitado 
à função (𝑛 + 𝑚) 𝑙𝑜𝑔 𝑛. O tempo de execução expresso apenas em 
função de 𝑛 (número de vértices) e considerando o pior caso para o 
conjunto de entrada seria 𝑂(𝑛2 . 𝑙𝑜𝑔 . 𝑛) . 
Uma outra implementação viável para a lista de valores do algoritmo 
de Dijkstra é a utilização de uma lista não ordenada, que apresenta tem-
po de execução 𝑂(𝑛) para a operação de retirar o menor valor, resultan-
do em um novo cálculo de tempo de execução 𝑂(𝑛2 + 𝑚) , equivalente a 
𝑂(𝑛2) , que é uma função quadrática. 
126 Estrutura de dados Ma
te
ria
l p
ar
a 
us
o 
ex
cl
us
ivo
 d
e 
al
un
o 
m
at
ric
ul
ad
o 
em
 c
ur
so
 d
e 
Ed
uc
aç
ão
 a
 D
is
tâ
nc
ia
 d
a 
Re
de
 S
en
ac
 E
AD
, d
a 
di
sc
ip
lin
a 
co
rre
sp
on
de
nt
e.
 P
ro
ib
id
a 
a 
re
pr
od
uç
ão
 e
 o
 c
om
pa
rti
lh
am
en
to
 d
ig
ita
l, s
ob
 a
s 
pe
na
s 
da
 L
ei
. ©
 E
di
to
ra
 S
en
ac
 S
ão
 P
au
lo
.
 
 
De acordo com o gráfico 1, que compara o comportamento das vá-
rias funções básicas, considerando que a implementação utilizando 
árvore binária e a implementação com lista não ordenada demandam 
esforços semelhantes de programação (esforço de trabalho dos progra-
madores, que também deve ser considerado) e comparando o tempo 
de execução utilizando árvore binária, 𝑂((𝑛 + 𝑚) . 𝑙𝑜𝑔 . 𝑛) , com o tempo 
utilizando lista, 𝑂(𝑛2) , a função quadrática demanda mais tempo que 
a função 𝑛-𝑙𝑜𝑔 -𝑛, sendo assim, a análise assintótica do algoritmo de 
Dijkstra é “em tempo 𝑂((𝑛 + 𝑚) . 𝑙𝑜𝑔 . 𝑛) no pior caso, ou alternativa-
mente, em tempo 𝑂(𝑛2) no pior caso” (GOODRICH; TAMASSIA, 2013, 
p. 641). 
Considerações finais 
O desenvolvimento de sistemas computacionais deve atender a um 
conjunto de necessidades tanto ligadas aos requisitos funcionais ine-
rentes ao problema a ser tratado pelo sistema como quanto aos requisi-
tos não funcionais de performance de execução, viabilidade econômica 
e capacidade evolutiva. Além disso, grande parte dos sistemas é desen-
volvida por uma equipe de profissionais com exigências de efetividade 
do esforço de programação devido a restrições de prazo e custo. 
Nesse contexto, diversos componentes do sistema necessitam de 
documentação adequada e validação quanto a eficiência, mesmo antes 
de serem colocados em produção, viabilizando e até exigindo que algo-
ritmos que implementam pontos críticos de performance dos sistemas 
sejam analisados com ferramentas que garantam a seleção adequada 
de soluções de implementação. 
Neste capítulo, foram apresentadas ferramentas e exemplos úteis e 
viáveis para a análise da complexidade e comparação de eficiência de 
algoritmos recursivose não recursivos calcados em conceitos matemá-
ticos para a representação do tempo de execução dos algoritmos. 
127 Eficiência assintótica de algoritmos
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
Referências 
GOODRICH, Michael T.; TAMASSIA, Roberto. Estrutura de dados e algoritmos 
em Java. 5. ed. Porto Alegre: Bookman, 2013. 
TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J. 
Estruturas de dados usando C. São Paulo: Makron Books, 1995. 
129 
M
aterial para uso exclusivo de aluno m
atriculado em
 curso de Educação a Distância da Rede Senac EAD, da disciplina correspondente. Proibida a reprodução e o com
partilham
ento digital, sob as penas da Lei. ©
 Editora Senac São Paulo.
 
Sobre o autor 
Valter Castelhano de Oliveira é doutor em engenharia mecânica 
pela Poli-USP, mestre em engenharia naval pela Poli-USP, mestre em ge-
renciamento de sistemas de informação pela PUC-Campinas e gradua-
do em ciência da computação pela UFSCAR. Possui pós-doutorado em 
engenharia mecatrônica pela Poli-USP. É cofundador e CKO do AgriFlix, 
plataforma de conhecimento sobre o agronegócio. Diretor da VCO-
Consultoria, especializada em projetos de P&D sustentados por fomen-
tos públicos e privados. Coordenador do curso de gestão de serviços 
da Fatec Indaiatuba. Tem certificação em gestão de projetos PMI-PMP. 
É pesquisador do DesignLab/Poli-USP com interesse de pesquisa em 
engenharia e design de sistemas de serviço automatizados. Possui ex-
periência profissional de 25 anos na área de gerenciamento de projetos, 
com ênfase em tecnologia da informação, atuando em projetos de au-
tomação, desenvolvimento de sistemas de informação e implantação 
de ERP. Possui experiência de oito anos como coordenador de cursos 
de pós-graduação presencial e EAD nas áreas de gestão de projetos e 
gestão da tecnologia da informação. Possui experiência de trinta anos 
como professor universitário em cursos de graduação e pós-graduação. 
	EST_DAD_01_ACE_2020
	EST_DAD_02_ACE_2020
	EST_DAD_03_ACE_2020
	EST_DAD_04_ACE_2020
	EST_DAD_05_ACE_2020
	EST_DAD_06_ACE_2020
	EST_DAD_07_ACE_2020
	EST_DAD_08_ACE_2020