Material de Estudos - Unidade 4 - Algoritmos para otimização de grafos

Prévia do material em texto

INTRODUÇÃO À TEORIA DOSINTRODUÇÃO À TEORIA DOS
GRAFOSGRAFOS
MODELOSMODELOS
COMPUTACIONAIS PARACOMPUTACIONAIS PARA
IMPLEMENTAÇÃO DEIMPLEMENTAÇÃO DE
GRAFOSGRAFOS
Autor: Me. Sergio Eduardo Nunes
Revisor : Emerson dos Santos Paduan
IN IC IAR
introdução
Introdução
Caro(a) aluno(a), conforme fomos avançando nas técnicas referentes à Teoria
dos Grafos, mas elas foram se tornando complexas. Até que chegamos a um
nível em que necessitamos de algoritmos para termos uma forma bem
de�nida de como as execuções devem acontecer sequencialmente, para
obtermos determinados resultados.
Porém, não necessariamente será necessária uma implementação
computacional por meio de linguagem de programação. Conforme forem
adicionados grafos com tamanhos grandes, a análise se torna mais difícil e a
tendência de ocorrerem erros será maior.
Nesta unidade de ensino, serão discutidos quatro algoritmos para análise de
grafos, sendo eles: o algoritmo de Floyd-Warshall, que permite utilizar grafos
direcionados para o cálculo do trajeto de menor custo; o algoritmo de
Bellman-Ford, que busca otimização de rotas levando em consideração os
custos negativos entre os vértices; o algoritmo Dijkstra, que também busca
otimização de trajeto entre os vértices, porém somente com valores positivos;
e, �nalmente, o algoritmo de Kruskal, que visa obter uma árvore com custos
mínimos. Parabéns por chegar até aqui, mas agora vamos �nalizar os estudos
acerca da Teoria dos Grafos?
Nesta etapa, já estamos em um nível dos estudos relacionados à Teoria dos
Grafos, em que as técnicas estudadas irão necessitar de aplicações
computacionais para a sua implementação. O mais importante neste
momento é que você possa compreender os processos e o funcionamento de
cada um dos algoritmos discutidos nesta unidade de ensino.
As demonstrações dos algoritmos serão feitas em pseudocódigo, por se tratar
de uma forma mais genérica de representar algoritmos, para, posteriormente,
ser implementada em uma linguagem de programação que mais se tenha
a�nidade, podendo ser: Python, C, PHP, Java, C++, CH, entre outras.
Inicialmente, discutiremos o algoritmo de Floyd-Warshall, que, em grande
parte das bibliogra�as, refere-se à técnica somente como algoritmo de Floyd
(Floyd’s Algorithm). Basicamente, deve-se efetuar o cálculo do caminho mais
curto entre os vértices, em que as arestas existentes possuem peso, podendo
estas serem direcionadas ou não.
A primeira publicação acerca desse tipo de grafo foi feita por Bernard Roy em
1959, porém houve uma releitura do algoritmo por Robert Floyd em 1962.
Algoritmo deAlgoritmo de
Floyd-WarshallFloyd-Warshall
Finalmente no mesmo ano de 1962, Stephen Warshall fez uma contribuição,
sendo descrito então o algoritmo de Floyd-Marshall. Esse algoritmo,
atualmente, possui três loops de repetição e foi proposto por Peter Ingerman
também no ano de 1962.
Como podemos perceber, não é possível atribuir as técnicas de algoritmos de
Floyd apenas a um pesquisador, uma vez que em praticamente durante os
anos de 1959 a 1962, existiram contribuições de quatro importantes
cientistas. É difícil a�rmar que um algoritmo tenha atingido o seu limite ou
maturidade, mas fato é que, após a contribuição proposta por Peter
Ingerman, não houve mais evolução do algoritmo.
Cormen e Leiserson (1989, p. 498) de�ne que “o objetivo do algoritmo de
Floyd é por meio de cálculos efetuados por algoritmos, encontrar o menor
caminho entre os pares de vértices de determinado grafo”. Sendo que as
arestas que ligam os vértices são valoradas, porém a sequência em que elas
serão percorridas não importa. O algoritmo visa fazer n interações,
correspondentes ao número de vértices existente no grafo, correspondendo a
uma matriz n x n. Para tal, deve ser utilizada uma programação dinâmica, em
que:
De�nam-se as premissas de uma solução ótima;
Calcule-se iterativamente (sucessivamente), a �m de se determinar
uma solução ótima; e
Calcule-se a solução ótima por meio de problemas menores,
modularmente.
Vale a pena salientar um termo que será utilizado ao longo das discussões
acerca do algoritmo de Floyd, tratando-se do vértice intermediário. Se temos
um caminho p = { , , , …, }, pode ser qualquer vértice, com exceção de
 e . Dessa forma, o subconjunto formado por p = { , , …, }.
Observe a Figura 4.1, para a melhor compreensão dos vértices intermediários.
v1 v2 v3 vn
v1 vn v2 v3 vn−1
Na Figura 4.1, os vértices intermediários são representados pelos nós na cor
verde. Sendo o vértice “D” o nó n -1. Ou seja, o subconjunto dos nós
intermediários é composto por p = {B, C, D}. Com isso de�nido, vamos de
forma textual, entender o funcionamento e objetivo do algoritmo de Floyd,
conforme descrito nos pontos a seguir:
Com base na estrutura de uma matriz, considere cada posição
sendo os vértices i, j.
Se a aresta entre i, j existir, ou ainda;
Se no caminho entre i e j, existir um vértice intermediário, ou
ainda;
Se no caminho entre i e j, existir um conjunto de vértices
intermediários.
Com base nisso e no custo encontrado entre o relacionamento de i e j,
determinar o menor custo entre os pontos i e j. O algoritmo de Floyd, em sua
representação matemática, pode ser descrito por:
Figura 4.1 - Vértices intermediários 
Fonte: Elaborada pelo autor.
=   Wij
⎧
⎩
⎨
⎪
⎪
0
w (i, j)
∞
se  i  =  j
se i ≠  j e  (i,  j)   ∈  A
e i ≠  j e  (i,  j)   ∉  A
Onde,
Wij é a representação da matriz dos valores de custo entre os
vértices, dadas as condições.
Para os valores de cada i, j da matriz: 
○ Deve ser valorado por 0 (zero), caso a posição de i seja igual a j.
Isso garante que não se tenha a incidência de laço no grafo. 
○Para todo vértice intermediário diferente de i igual a j, receberá
o seu custo correspondente. 
○ Caso o vértice intermediário estiver em i diferente de j e não
houver aresta, então o seu valor será expresso como in�nito.
O algoritmo com a expressão matemática com tais descrições textuais é
expresso por:
Para que a expressão matemática possa ser implementada
computacionalmente, observe a Figura 4.2, que demonstra o algoritmo escrito
em pseudocódigo.
reflita
Re�ita
Os algoritmos são sequências
organizadas de execuções que devem
ser seguidas para se resolver
problemas. Esse termo sempre está
relacionado a aplicações
computacionais, porém não
necessariamente necessita ser
implementado em uma aplicação. Nas
discussões dos algoritmos que
propõem soluções em grafos, indica-
se que, para melhores análises, deva
ser utilizada alguma linguagem de
programação para esse �m. Qual o
motivo? Por que isso ocorre?
Fonte: Nunes (2016).
di = min  {di + dk , di }jk kk−1 jk−1 jk−1
Essa representação computacional por meio do pseudocódigo visa
demonstrar o que foi descrito no texto anteriormente e, ainda, servir como
orientação para que o algoritmo possa ser escrito em uma linguagem de
programação, se assim for necessário. Porém, vale a pena salientar um
artifício utilizado nas linhas 16 e 27 chamado “pred”. Trata-se de um
mecanismo dentro do algoritmo, que tem a função de, a cada vértice
encontrado durante a busca, apontar para o seu predecessor. Ou seja, será
apontado para o vértice que o precedeu durante a execução do algoritmo.
Dessa forma, a “varredura” que o algoritmo de Floyd-Warshall efetua tem a
capacidade de visitar todos os vértices.
Para compreensão absoluta do funcionamento do algoritmo de Floyd, vamos
tomar como base o grafo representado na Figura 4.3.
Figura 4.2 - Pseudocódigo do algoritmo de Floyd-Warshall 
Fonte: Elaborada pelo autor.
Para isso, observe a matriz formada com o grafo:
Obs.: Vale ressaltar que o método explicado deve ignorar o valor quando na
linha e coluna for encontrado o símbolo de in�nito, como é o do custo entre a
coluna C com a linha B, pois temos nos dois casos um vértice com valor
in�nito e isso torna o valor impossível de ser calculado.
Acompanhe textualmente cada uma das interações feitas pelo algoritmo de
Floyd:
Figura 4.3 - Grafode exemplo para o algoritmo de Floyd 
Fonte: Elaborada pelo autor.
A B C D
A 0 8 ∞ 1
B ∞ 0 1 ∞
C 4 ∞ 0 ∞
D ∞ 2 9 0
1. Primeira interação: na primeira interação com o k = 1. A linha e a
coluna de A devem ser ignoradas, bem como a diagonal principal
da matriz que recebe o valor 0 (a,a; b,b; c,c; d,d). Dessa forma,
existem duas interações possíveis, que estão na linha C e coluna
B, como também linha C coluna D. Vamos veri�car se a soma dos
nós 4 + 8 é maior que in�nito (tenha o in�nito como valor
indeterminado), 12 é maior que in�nito e, dessa forma, o valor é
substituído em . O mesmo vale para , que 5 é maior que
in�nito.
2. Segunda interação: na primeira interação com o k = 2. A segunda
linha e segunda coluna devem ser ignoradas, assim como a
diagonal principal, e onde houver in�nito. Dessa forma, a
interação ocorre em e . Para isso, devem ser
substituídos os valores 9 e 3 nas respectivas posições da matriz.
3. Terceira interação: na primeira interação com o k = 3. A terceira
linha e terceira coluna devem ser ignoradas, assim como a
diagonal principal, e onde houver in�nito. Dessa forma, a
interação ocorre em , e . Para isso, devem ser
substituídos os valores 5, 6 e 7 nas respectivas posições da
matriz.
4. Quarta interação: na primeira interação com o k = 4. A quarta
linha e quarta coluna devem ser ignoradas, assim como a
diagonal principal, e onde houver in�nito. Dessa forma, a
interação ocorre em e . Para isso,
devem ser substituídos os valores 3, 4, 5, 1, 4 e 7 nas respectivas
posições da matriz.
Com isso, após as interações foi gerada uma matriz com os valores mínimos
expressos, como se pode observar:
wc,b wc,d
wa,c wd,c
wb,a wb,d wd,a
wa,b,wa,c,wb,a,wa,c,wc,a, wc,b
⎡
⎣
⎢⎢⎢⎢⎢⎢
      A  B  C  D
A    0   3   4   1
B    5   0   1   6
C    4   7   0   5
D    7   2   3   0
⎤
⎦
⎥⎥⎥⎥⎥⎥
Para ajudar a compreender esses resultados, vamos observar no grafo
representado na Figura 4.3, os possíveis caminhos para ir do vértice A até C,
em que temos que:
De A para B, de B para C, com custo igual a 9.
De A para D, de D para C, com custo igual a 10.
De A para D, de D para B, de B para C, com custo igual a 4.
Com a minimização demonstrada na matriz, a posição e é igual a 4.
Dessa forma, demonstrando o caminho com o menor custo para o grafo todo.
praticar
Vamos Praticar
O algoritmo de Floyd-Warshall teve uma grande contribuição na Teoria dos Grafos,
uma vez que proporcionou a otimização das rotas em determinado trajeto
composto por n vértices. É claro que a sua implementação se torna mais e�ciente
em uma aplicação computacional, já que, para efetuar o seu cálculo completo, são
necessárias algumas checagens e interações.
Com base no exposto, assinale a alternativa que descreve corretamente o objetivo
principal do algoritmo de Floyd-Warshall.
a) O número de vértices mínimos.
Feedback: alternativa incorreta , pois o algoritmo não visa estudar o número
de vértices mínimos de determinado grafo.
b) O número de arestas mínimas.
Feedback: alternativa incorreta , pois o algoritmo não visa buscar o número
mínimo de arestas que um grafo pode ter.
wa,c wc,a
c) Encontrar o caminho de maior custo, a �m de evitá-lo.
Feedback: alternativa incorreta , pois o objetivo do algoritmo é encontrar, por
meio de comparações, o trajeto de menor custo.
d) Encontrar o caminho de menor custo entre dois vértices valorados.
Feedback: alternativa correta , pois o algoritmo de Floyd faz interações
comparativas, a �m de se determinar o menor custo entre dois vértices,
tornando a análise de trajeto mais e�ciente.
e) Evitar que ocorra cruzamento das arestas na representação do grafo.
Feedback: alternativa incorreta , pois, já que o cruzamento das arestas é
irrelevante, o objetivo é encontrar o trajeto entre dois vértices com o menor
custo.
Todos os grafos trabalhados até o momento, quando possuíam valoração,
esta era positiva. Nesse momento, iremos ampliar as possibilidades de
abstração das análises e aplicação dos grafos em que o peso (custo) das
arestas entre os vértices utilize valores negativos. Esse algoritmo foi
produzido por meio de métodos propostos por três autores: Lester Ford
(1956), Edward Moore (1957) e Richard Bellman (1958). Para tal, alguns
autores atribuem ao algoritmo o nome Ford-Moore-Bellman, devido às
contribuições propostas pelos três matemáticos, basicamente em dois anos
de pesquisa.
Segundo Cormen e Leiserson (1989), o algoritmo de Bellman-Ford visa buscar
uma solução para o problema e encontrar o menor caminho entre dois
vértices em um grafo valorado, podendo esse ser expresso por valores
negativos.
Certamente, neste momento você deve estar se perguntando por que são
utilizados valores negativos entre dois vértices? Pois bem, para situações
encontradas no cotidiano, podemos salientar:
Algoritmo deAlgoritmo de
Bellman-FordBellman-Ford
A de um caminhoneiro que recebe um valor pelo frete, porém, se o
gasto com combustível e pedágio for maior do que o recebido.
A do câmbio do mercado de ações pode gerar lucro ou prejuízo
conforme a atualização do mercado �nanceiro e as escolhas de
compra ou venda das ações.
A de reações químicas que a energia consumida pode ser maior do
que aquela gerada durante determinada reação.
Com isso, podemos compreender as três partes do algoritmo de Bellman-
Ford, em que:
Inicialização: faz a padronização das distâncias (custos) dos vértices
sem relacionamentos, antes de iniciar a resolução do problema em
si.
Relaxamento: tem a função de calcular o caminho mínimo, dentro do
cenário do grafo.
Veri�cação de ciclos negativos: faz a veri�cação se é possível efetuar
o cálculo do caminho mínimo, bem como se não ocorre ciclos
negativos.
Como podemos observar, para que o cálculo seja efetuado, não deve ocorrer
ciclo negativo da origem do grafo até o seu destino. Para a utilização desses
três pontos apresentados, o algoritmo utilizado pode ser observado na Figura
4.4. 
Com isso, para exempli�car o funcionamento desse algoritmo vamos utilizar o
grafo representado na Figura 4.5.
Para tal, o algoritmo inicia no vértice S, com duas arestas sendo A com peso
10, e para E com peso 8. Gerando a matriz a seguir:
Figura 4.4 - Algoritmo de Bellman-Ford 
Fonte: Elaborado pelo autor.
Figura 4.5 - Grafo para aplicação do algoritmo de Bellman-Ford 
Fonte: Elaborada pelo autor.
O início em S sempre terá o valor 0 (zero). O algoritmo visa testar o peso dos
caminhos e substituir o valor mais baixo na matriz. Por exemplo, para chegar
em sair do vértice S e chegar em A, é possível utilizar o caminho: E(8) - D(1) -
A(-4). Com isso, a matriz recebe os valores:
Repare que D recebeu o valor 9, pois S para E tem peso 8, de E para D tem
peso 1, dessa forma, 8 + 1 = 9; já para o vértice A foi efetuado o trajeto E + D +
A, respectivamente 8 + 1 + (- 4) = 5. Esse processo se repete até que tenha
sido encontrado o menor valor entre os vértices.
Do grafo utilizado no exemplo, após todas as interações possíveis, foi gerada
a matriz otimizada, conforme pode ser observado:
Com isso, podemos perceber como �caria inviável se fossem adicionados
muitos nós para ser calculado o menor caminho entre os vértices
manualmente. Porém, compreender o funcionamento do algoritmo permitirá
que você efetue implementações computacionais, testes e simulações.
S A B C D E
0 10 INFINITO INFINITO
INFINITO-
--
8
S A B C D E
0 5 INFINITO INFINITO 9 8
S A B C D E
0 5 5 7 9 8
praticar
Vamos Praticar
O algoritmo de Bellman-Ford possibilita que sejam analisadas as possibilidades de
trajetos, a �m de se encontrar o menor caminho entre os vértices. Para isso, as
arestas que ligam os vértices são direcionadas e possuem os seus respectivos
valores.
Com base no exposto, assinale a alternativa que descreve a diferença do algoritmo
de Bellman-Ford para os demais grafos e algoritmos de análise de minimização de
trajeto.
a) O algoritmo de Bellman-Ford não necessita de custo �xo entre os vértices,
podendo ser gerados valoresaleatórios conforme as interações ocorrem.
Feedback: alternativa incorreta , pois o custo dos vértices é �xado conforme
um valor menor é encontrado pelo algoritmo. Dessa forma, não �ca variando
aleatoriamente.
b) O algoritmo de Bellman-Ford não permite análise de menor custo com
mais de seis vértices.
Feedback: alternativa incorreta , pois não importa a quantidade de vértices
para a análise com o algoritmo de Bellman-Ford. É lógico que, quanto mais nós
existirem no grafo, maior será o tempo de execução do algoritmo.
c) O algoritmo de Bellman-Ford efetua cálculo de menor trajeto com valores
negativos.
Feedback: alternativa correta , pois a diferença do algoritmo de Bellman-Ford
trabalha com valores negativos, sendo esse o diferencial em relação às demais
técnicas.
d) O algoritmo de Bellman-Ford visa atribuir cores aos vértices, conforme os
menores valores encontrados nas interações.
Feedback: alternativa incorreta , pois as técnicas de problema de coloração
não são tratadas pelo algoritmo de Bellman-Ford.
e) O algoritmo de Bellman-Ford tem o objetivo de eliminar o cruzamento de
arestas no grafo.
Feedback: alternativa incorreta , pois o objetivo do algoritmo de Bellman-Ford
é encontrar caminhos mínimos.
Uma vez que você tenha compreendido as discussões acerca do algoritmo de
Bellman-Ford, a compreensão do algoritmo de Dijkstra será mais fácil. A
diferença entre os dois algoritmos é que não é possível utilizar valores
negativos entre os vértices.
O cientista da computação Edsger W. Dijkstra publicou, no ano de 1959, um
algoritmo simples, porém muito poderoso, que permite uma análise e�ciente
do caminho mínimo entre os vértices. Para tal, pode ser escolhido qualquer
dos vértices de determinado grafo e calculado o custo mínimo desse trajeto
em especí�co ou, ainda, calcular o menor custo de determinado vértice para
todos os demais.
O algoritmo possui diversas aplicações, mas vale lembrar que, em caso do
custo encontrado nas arestas que ligam os vértices possuírem valores
negativos, o algoritmo não funcionará corretamente, podendo, então, gerar
valores de saída errados. No algoritmo de Dijkstra, os seguintes passos devem
ser seguidos:
Algoritmo deAlgoritmo de
DijkstraDijkstra
Deve ser de�nido o valor in�nito para todos os vértices, exceto o
vértice inicial.
O ponto inicial do trajeto “S” deve ser atribuído o valor 0 (zero).
A cada interação, encontrar um vértice que não foi processado,
ou seja, que possui valor in�nito.
Se encontrado o vértice não processado, atribua a ele um valor.
Se o valor a ser atribuído for menor que o �xado ao vértice,
então efetue a substituição.
Os passos descritos podem ser implementados seguindo o algoritmo
representado pelo pseudocódigo na Figura 4.6. 
Para que você possa compreender melhor o funcionamento desse algoritmo,
considere o grafo da Figura 4.7 para demonstrar as etapas que compõem o
algoritmo de Dijkstra.
Figura 4.6 - Algoritmo de Dijkstra 
Fonte: Elaborada pelo autor.
Com base no grafo, considere um trajeto que parte do vértice A e deve chegar
ao vértice F, com o objetivo de encontrar o caminho de menor custo com o
algoritmo de Dijkstra. Para isso, inicialmente vamos utilizar a matriz a seguir:
Inicialmente, foi atribuído o valor 0 (zero) ao vértice inicial, e ligado em A para
B com o custo 2, e de A para B com o custo 3. Observando a matriz, já temos
Figura 4.7 - Grafo para demonstração do algoritmo de Dijkstra 
Fonte: Elaborada pelo autor.
Passo
1
Passo
2
Passo
3
Passo
4
Passo
5
Passo
6
A (0, A)
B (2, A)
C (3, A)
D ∞
E ∞
F ∞
dois valores de�nitivos, sendo o inicial de A para B, pois, como o grafo é
dirigido, existem outros caminhos. Porém, o custo é maior e, por isso, não
ocorrerá o relaxamento. Dessa forma, a matriz é representada como:
Inicialmente, podemos perceber que o caminho de A para C é de�nitivo, e o
trajeto A - B - D é igual a 7, já A - B - E é igual a 4. O terceiro passo é
demonstrado na matriz a seguir:
Passo
1
Passo
2
Passo
3
Passo
4
Passo
5
Passo
6
A (0, A) *** *** *** *** ***
B (2, A) (2, A) *** *** *** ***
C (3, A) (3, A)
D ∞ (7, B)
E ∞ (4, B)
F ∞ ∞
Com isso, podemos perceber que a linha “E” já possuí um caminho mínimo e,
portanto de�nitivo. Agora, podemos passar para o quarto passo, conforme
matriz a seguir:
Passo
1
Passo
2
Passo
3
Passo
4
Passo
5
Passo
6
A (0, A) *** *** *** *** ***
B (2, A) (2, A) *** *** *** ***
C (3, A) (3, A) (3, A) *** *** ***
D ∞ (7, B) (7, B)
E ∞ (4, B) (4, B)
F ∞ ∞ ∞
Passo
1
Passo
2
Passo
3
Passo
4
Passo
5
Passo
6
A (0, A) *** *** *** *** ***
B (2, A) (2, A) *** *** *** ***
C (3, A) (3, A) (3, A) *** *** ***
D ∞ (7, B) (7, B) (5, E)
E ∞ (4, B) (4, B) (4, B) *** ***
F ∞ ∞ ∞ (8, E)
Certamente, o custo de D para B é maior que D para E. Portanto, já é um valor
de�nitivo no próximo passo, como pode ser observado a seguir:
Finalmente, do vértice D para o vértice �nal F com o custo de 7, e valor
de�nitivo, conforme pode ser observado a seguir:
Passo
1
Passo
2
Passo
3
Passo
4
Passo
5
Passo
6
A (0, A) *** *** *** *** ***
B (2, A) (2, A) *** *** *** ***
C (3, A) (3, A) (3, A) *** *** ***
D ∞ (7, B) (7, B) (5, E) (5, E) ***
E ∞ (4, B) (4, B) (4, B) *** ***
F ∞ ∞ ∞ (8, E) (7, D)
Logo, podemos perceber que o algoritmo de Dijkstra veri�ca o caminho mais
curto e faz as substituições conforme encontra o caminho de valores menores
nas interações.
praticar
Vamos Praticar
O algoritmo de Dijkstra tem diversas aplicações, inclusive em serviços utilizados
diariamente. Provavelmente, as pessoas acabam usufruindo de sua técnica, sem
sequer saberem o que ocorre por trás de determinadas execuções. Um exemplo
disso está na rede de computadores, que, por meio de seus protocolos, utiliza tal
Passo
1
Passo
2
Passo
3
Passo
4
Passo
5
Passo
6
A (0, A) *** *** *** *** ***
B (2, A) (2, A) *** *** *** ***
C (3, A) (3, A) (3, A) *** *** ***
D ∞ (7, B) (7, B) (5, E) (5, E) ***
E ∞ (4, B) (4, B) (4, B) *** ***
F ∞ ∞ ∞ (8, E) (7, D) (7, D)
algoritmo a �m de se obter o caminho mais curto entre roteadores espalhados na
topologia da rede mundial de computadores.
Com base no exposto, assinale a alternativa que descreve a restrição encontrada no
algoritmo de Dijkstra.
a) Não consegue calcular o caminho mais curto, com quantidade de vértices
par.
Feedback: alternativa incorreta , pois a quantidade ser par não interfere na
possibilidade de calcular o caminho mais curto com o algoritmo de Dijkstra.
b) Não consegue calcular o caminho mais curto, se não existir ao menos um
laço no grafo.
Feedback: alternativa incorreta , pois o fato de ter laço não é um impeditivo
para o funcionamento do algoritmo de Dijkstra.
c) Não consegue calcular o caminho mais curto, com quantidade de vértices
ímpar.
Feedback: alternativa incorreta , pois a quantidade ser ímpar não interfere na
possibilidade de calcular o caminho mais curto com o algoritmo de Dijkstra.
d) Não consegue calcular o caminho mais curto, com custos negativos.
Feedback: alternativa correta , pois o algoritmo de Dijkstra não consegue
efetuar cálculo quando encontrados valores negativos.
e) Não consegue calcular o caminho mais curto, se utilizar grafos direcionais.
Feedback: alternativa incorreta , pois é possível utilizar os grafos direcionais
com o algoritmo de Dijkstra.
Os algoritmos discutidos até o momento tinham como objetivo encontrar o
menor caminho entre dois vértices, de forma que poderiam ser utilizados
cruzamento de arestas, custo entre os vértices com valores positivos e
negativos, com grafos direcionados ou não. Agora, se adicionarmos uma
restrição em que, para encontrar o melhor caminho, antes teríamos de
eliminar os ciclos?
Segundo Netto e Jurkiewicz (2017), o ciclo hamiltoniano exige que o trajeto
seja fechado, isto é, ocorre um circuito. Para exempli�car um grafo com esse
per�l, observe a Figura 4.8.
Algoritmo deAlgoritmo de
KruskalKruskal
Repare que é possível fazer alguns circuitos com o grafo apresentado,por
exemplo:
A - B - C - A.
A - B - C - D - E - A.
A - D - E - A.
Assim, podemos encontrar diversos circuitos, passando por alguns vértices,
ou todos os vértices, dependendo da análise que se deseja fazer. Mas, a�nal
de contas, quem foi Kruskal?
O algoritmo foi desenvolvido pelo Ph.D Joseph Bernard Kruskal Júnior (1928-
2010), que era matemático, estatístico e cientista da computação. Ele veio de
uma família em que todos tiveram sucesso em sua carreira acadêmica, sendo
isso um grande motivador para as contribuições por ele propostas. Seu
trabalho mais famoso é o algoritmo de Kruskal, que permite o cálculo da
árvore geradora mínima de um grafo valorado.
O seu funcionamento enquanto algoritmo tem uma sequência de execução
bem simples, conforme descrito a seguir:
1. Selecione a aresta externa com o menor custo;
2. Considere “α” a aresta selecionada;
Figura 4.8 - Grafo com ciclo. 
Fonte: Elaborada pelo autor.
3. Considere A a árvore mínima geradora; e
4. Acrescente “α” em A.
Isso posto, é possível observar a sequência de atividades expostas no
algoritmo escrito em pseudocódigo, como pode ser observado na Figura 4.9.
Para explicar o seu funcionamento, vamos tomar o grafo demonstrado na
Figura 4.10, para aplicação do algoritmo de Kruskal, conforme pode ser
observado a seguir.
1. Deve ser selecionada a aresta de menor peso no grafo. Se ela não formar
um ciclo, então deve compor a árvore geradora mínima. O menor custo está
em B para C, com custo 2, não forma ciclo, pois são os primeiros vértices
selecionados. Gerando, na primeira etapa, o grafo demonstrado na Figura
4.10.
Figura 4.9 - Algoritmo de Kruskal em pseudocódigo 
Fonte: Elaborada pelo autor.
Atente-se que os vértices e as arestas que farão parte da árvore mínima
estarão na cor vermelha.
2. Repete-se o processo com a aresta de menor peso e que não forme ciclo.
Existem duas possibilidades: B para A, com peso 4, ou, ainda, C para A, com
peso 4, podendo ser escolhido qualquer um dos dois casos. Para o exemplo,
serão escolhidos os vértices B para A. Gerando o grafo demonstrado na
Figura 4.11.
Figura 4.10 - Primeira etapa do algoritmo de Kruskal 
Fonte: Elaborada pelo autor.
Figura 4.11 - Segunda etapa do algoritmo de Kruskal 
Fonte: Elaborada pelo autor.
3. A próximo vértice selecionado será entre A e C, com o custo 4. Porém, essa
seleção fere uma premissa do algoritmo de Kruskal, que é de não formar
ciclo. Desse modo, a aresta não fará parte da árvore.
4. Selecionando a aresta de menor custo, existem duas possibilidades, sendo
de A para E, com custo 6, e A para D, com custo 6 também. Inicialmente,
vamos optar por A para E (pode ser escolhida qualquer uma das opções, pois
não formam ciclos). Sendo gerado o novo grafo descrito na Figura 4.12.
5. O próximo trajeto selecionado é de A para D, com custo 6, e não formando
ciclo, apresentando o grafo da Figura 4.13.
Figura 4.12 - Quarta etapa do algoritmo de Kruskal 
Fonte: Elaborada pelo autor.
6. Repare que tanto a aresta que vai de C para D quanto a de D para E
poderão ser selecionadas. Isso feito, estaremos fechando um ciclo.
A árvore mínima geradora que o algoritmo de Kruskal resolve está
representada na Figura 4.14.
Podemos concluir que o algoritmo de Kruskal tem uma sequência de
execução bem simples e de�nida. De forma que se propõe, de maneira bem
Figura 4.13 - Quinta etapa do algoritmo de Kruskal 
Fonte: Elaborada pelo autor.
Figura 4.14 - Grafo de uma árvore geradora mínima 
Fonte: Elaborada pelo autor.
e�ciente, a gerar uma árvore mínima com grafos não direcionais e valorados
até que retorne um novo grafo otimizado.
Algoritmo de PRIM
Esse algoritmo foi publicado por Robert C. Prim em 1957 e, anos depois, teve
uma contribuição de Dijskra. Segundo Neto (2017), trata-se de um grafo
conexo, não dirigido e com custos nas arestas. Sendo esse custo arbitrário,
saibamais
Saiba mais
O grafo em árvore é mais comum do que se
imagina. Ele está disponível em hierarquia
dentro das empresas, quando se faz uma
árvore genealógica com toda a estrutura
familiar, entre diversas outras aplicações. As
técnicas de Teoria dos Grafos também
utilizam essa estrutura a �m de propor
otimização de trajetos entre os vértices. No
entanto, uma aplicação que nos favorece a
compreensão de uma estrutura em árvore é
o desenvolvimento de uma árvore
genealógica familiar. Para isso, você pode
utilizar o site (gratuito) conhecido por
GeneaNet. Além de compreender uma
estrutura em árvore, será interessante poder
visualizar a estrutura e o tamanho da sua
família.
ACESSAR
https://pt.geneanet.org/criar-a-sua-arvore/
pode conter valores positivos ou negativos. É utilizado para encontrar uma
árvore geradora mínima.
Basicamente, o algoritmo de PRIM possui uma subárvore de G até que ela
consiga se tornar uma árvore geradora (MST). Contudo, para de�nir o
funcionamento do algoritmo de PRIM, devem ser utilizados os seguintes
passos:
1. Escolha um vértice inicial;
2. Escolha a aresta com o custo mínimo, que não forme ciclo;
3. Considere x-y a aresta escolhida, com x contido na subárvore (T); e
4. Acrescente a aresta x-y e o vértice y a T, que é o subconjunto de G.
Para compreender o funcionamento desse algoritmo, observe o grafo
representado na Figura 4.15.
A primeira etapa consiste em determinar um ponto inicial. Para isso,
tomaremos o vértice A. O único caminho possível é B. Após isso, saindo de B
pode-se ir para E ou C, porém o custo de C é menor. Observe na Figura 4.16 o
grafo após essas interações.
Figura 4.15 - Grafo para algoritmo de PRIM (I) 
Fonte: Elaborada pelo autor.
Partindo do vértice E, temos D com custo 7 e F com custo 2. Dessa forma, o
menor custo é de E para F. Partindo do vértice F, o menor custo está em I com
6. Partindo do vértice I, o menor custo é 3 para o vértice J. Observe como está
o grafo após esses passos na Figura 4.17.
Perceba que, nesse ponto, não podemos fazer o caminho J para F, pois assim
será feito um ciclo. Dessa forma, temos de procurar a aresta de menor custo,
sendo selecionado C para D (custo 5). Porém, mais uma vez, não poderá ser
Figura 4.16 - Grafo para algoritmo de PRIM (II) 
Fonte: Elaborada pelo autor.
Figura 4.17 - Grafo para algoritmo de PRIM (III) 
Fonte: Elaborada pelo autor.
utilizado, já que não existem arestas selecionadas até o momento que
incidam em algum vértice do processo de minimização.
Na sequência, o vértice de menor custo está de E para D, com custo 7. Agora,
partindo do vértice D, o menor custo estará em C, com 5. Partindo de C, o
único caminho é para B, que não pode ser selecionado, pois forma um ciclo.
Dessa maneira, observe na Figura 4.18 como está o grafo até o momento.
O próximo vértice selecionado com o menor custo está de D para G, com
custo 11. Partindo de G, não pode ser selecionado F, pois forma ciclo. Resta
apenas o vértice H, que pelo menor custo se liga a F. Na Figura 4.19, foram
eliminados os vértices que formam ciclos, conforme pode ser observado.
Figura 4.18 - Grafo para algoritmo de PRIM (III) 
Fonte: Elaborada pelo autor.
Como podemos perceber, foram utilizados os menores custos que não
formam ciclos. Para representar o funcionamento do algoritmo de PRIM para
uma implementação computacional, deve ser observado o pseudocódigo na
Figura 4.20.
Como podemos observar, o algoritmo de PRIM escolhe, a partir de
determinado vértice, a aresta de menor custo, porém esta não pode formar
ciclo.
Figura 4.19 - Grafo para algoritmo de PRIM (Final) 
Fonte: Elaborada pelo autor.
Figura 4.20 - Algoritmo de PRIM em Pseudocódigo 
Fonte: Elaborada pelo autor.
praticar
Vamos Praticar
O algoritmo de Kruskal tem o seu mecanismo de funcionamento bem de�nido, com
instruções bem claras. É uma das formas de encontrar caminhos mínimos, com
grafos com diversas arestas, vértices, pesos e com variados formatos e quantidades.
Com base nos conceitos do algoritmo de Kruskal, assinale a alternativa que
descreve corretamente o seu funcionamento.a) O algoritmo de Kruskal visa encontrar uma árvore com valores mínimos e
que não forme circuito.
Feedback: alternativa correta , pois, no algoritmo de Kruskal, são selecionados
os vértices com o menor custo, porém o grafo não pode conter ciclos com esses
vértices que o compõem.
b) O algoritmo de Kruskal visa eliminar os vértices que não contenham
valoração.
Feedback: alternativa incorreta , pois, para utilizar o algoritmo de Kruskal, o
grafo deve ser valorado, ou seja, possuir pesos (custo).
c) O algoritmo de Kruskal visa encontrar uma árvore com valores máximos e
que não formem ciclo.
Feedback: alternativa incorreta , pois o algoritmo de Kruskal busca os custos
mínimos entre os vértices.
d) O algoritmo de Kruskal visa encontrar uma árvore com valores mínimos e
que formem ciclo.
Feedback: alternativa incorreta , pois, no algoritmo de Kruskal, são buscados
aqueles vértices que possuam o menor valor (custo) e não formem ciclo na
árvore geradora.
e) O algoritmo de Kruskal visa eliminar os vértices inúteis.
Feedback: alternativa incorreta , pois não existe vértice inútil, mas, sim,
vértices que, se selecionados pelo algoritmo de Kruskal, estariam fechando um
ciclo; e o objetivo do algoritmo é construir uma árvore mínima sem ciclos.
indicações
Material
Complementar
FILME
Sunspring
Ano: 2016
Comentário: O vídeo não aborda o conceito de
computadores ou sequer fala a respeito de grafos. Os
diálogos entre os personagens são um tanto quanto
confusos, mas a grande inovação está no seu roteiro,
pois é o primeiro �lme “escrito” por um computador,
por meio de um algoritmo. Vale a pena assistir! É, no
mínimo, curioso e diferente. Também é possível ativar
as legendas.
TRA ILER
LIVRO
Aprendendo Lógica de Programação
(VisuAlg)
Editora: Hope
Autor: Sergio Eduardo Nunes
ISBN: 978-85-5788-006-11
Comentário: Os algoritmos podem ser representados
de algumas formas. Uma delas é o pseudocódigo, que é
uma das preferidas por diversos autores e
pesquisadores. Essa ferramenta permite que se
compreenda como o algoritmo deve ser estruturado,
sendo possível, posteriormente, efetuar uma
implementação por meio de uma linguagem de
programação.
conclusão
Conclusão
Os algoritmos são formas bem e�cientes para chegar a algumas conclusões
que se deseja obter acerca dos grafos. Embora muitas vezes a compreensão
do seu funcionamento seja tranquila, para obter resultados mais precisos e
poder adicionar mais vértices aos experimentos, possam ser necessárias
implementações computacionais.
Os algoritmos vistos ao longo desta unidade de ensino são implementáveis
em diversas linguagens de programação. Algumas delas, possuem bibliotecas
que já fazem algumas execuções automaticamente; em outras, as soluções
devem ser construídas pelo desenvolvedor.
As análises feitas pelos algoritmos discutidos permitem observações
interessantes. Todavia, para total experimentação, comparativo do tempo de
respostas dos algoritmos e demais observações, elas necessitam de uma
linguagem de programação para que os experimentos sejam efetuados por
meio de uma aplicação.
referências
Referências
Bibliográ�cas
CORMEN, T. H.; LEISERSON, R. L. Introdução a algoritmos . Rio de Janeiro:
Editora Campus, 1989.
NETTO, Boaventura; JURKIEWICZ, Samuel. Grafos : Introdução e Prática. São
Paulo: Blucher, 2017.
NUNES, E. Sergio. Aprendendo Lógica de Programação . São Paulo: Hope,
2016.