03490

Prévia do material em texto

Técnica de buscas em grafos
Planaridade e percursos eulerianos e hamiltonianos, assim como suas aplicações. Buscas em grafos,
árvores geradoras, grafos ponderados e árvores geradoras mínimas, além de seus algoritmos de
determinação com aplicações.
Prof. Luiz Henrique da Costa Araujo
1. Itens iniciais
Propósito
Para diversos problemas do cotidiano, a modelagem em um grafo pode facilitar a vida ou reduzir o custo
operacional de uma empresa. Para um profissional de computação, é fundamental conhecer a teoria dos
grafos e saber o potencial de solução de problema de seus algoritmos, bem como suas principais aplicações
práticas.
Objetivos
Reconhecer os grafos planares e os percursos eulerianos e hamiltonianos.
Calcular percursos em grafos e suas especializações: os percursos em largura e profundidade.
Calcular as árvores geradoras mínimas de um grafo ponderado.
Identificar as principais aplicações dos algoritmos vistos.
Introdução
Dentre as diversas áreas de estudo das entidades matemáticas, a Teoria dos Grafos destaca-se por sua
aplicação prática. Diversos problemas do nosso cotidiano podem ser resolvidos com a modelagem
matemática que resulta em um grafo e a aplicação de um algoritmo sobre esse grafo.
Nesse contexto, malhas viárias, redes de comunicação de dados, rotas de navegação aérea ou marítimas,
podem ser modeladas em um grafo e a solução do problema associado é a obtenção de um percurso no grafo
que modela os dados do problema.
Com o objetivo de compreender os algoritmos de percursos em grafos, estudaremos os principais conceitos e
os principais resultados e algoritmos neste assunto, bem como alguns exemplos de aplicações.
• 
• 
• 
• 
1. Busca em grafos planos
Teoria dos grafos
Conceitos básicos
A teoria dos grafos é uma parte da matemática discreta que estuda a entidade matemática grafo. Um grafo
G=(V,E) constitui um par de conjuntos distintos e disjuntos V e E.
O conjunto V é denominado conjunto de vértices e E, o conjunto das arestas. Já os elementos do conjunto E
são pares de elementos do conjunto V.
Exemplo
Considere G = (V , E) um grafo, o conjunto V = {A, B, C, D, E} e o conjunto E = {(A, B), (A, C), (B, D), (C, E),
(D, E)}. Vale ressaltar que os elementos de E são pares de elementos de V e não há ideia de ordem entre
tais elementos, isto é, o par (A, B) é igual ao par (B, A). 
É comum chamar um elemento de V de vértice ou nó e um elemento de E de aresta ou arco.
Existe uma variação do conceito de grafo quando os elementos de E são pares ordenados. Sendo assim, o par
(A, B)≠(B, A). Nesse caso, chamamos de grafo direcionado ou digrafo a entidade G=(V,E).
Como existe uma distinção entre as entidades grafo e digrafo, é importante especificar qual delas se
está manipulando.
A definição formal de grafos e digrafos é importante, sem dúvida. Entretanto, é raro observar referências a um
grafo ou digrafo de forma textual.
O mais comum é ver uma representação pictórica da entidade. Para isso, os grafos são representados por
meio de seus vértices como circunferências e os arcos, como segmentos de retas conectando os vértices.
Citamos como exemplo o grafo G = (V, E), em que V = {A, B, C, D, E} e E = {(A, B), (A, C), (B, D), (C, E), (D, E)}.
Sua representação pictórica seria a da imagem a seguir:
Representação pictórica do grafo exemplo.
Atenção
É muito comum que as pessoas façam referência a uma representação pictórica como sendo o próprio
grafo. Entretanto, o grafo é uma entidade matemática abstrata, enquanto a imagem se trata apenas de
uma representação dessa entidade. 
Observe que, na imagem acima, os elementos do conjunto V (vértices) são representados como
circunferências e que os elementos de E (arestas) são representados como segmentos de retas ligando os
vértices.
Para que possamos desenvolver nosso estudo, precisamos definir alguns conceitos:
Caminho
Um caminho é uma sequência de vértices 
Ciclo
Um ciclo é um caminho no qual o vértice inicial
é o mesmo do vértice final.
Na imagem adiante, é um caminho, uma vez que 
Note que também é um caminho e que as arestas 
; entretanto, o vértice está repetido em . Pela
definição, isso não é proibido.
Grafo exemplo 1.
No primeiro exemplo, o caminho não continha repetição de vértices. Por isso, é
chamado de caminho simples, enquanto constitui um caminho.
Na imagem do grafo exemplo 1, o caminho se trata de um ciclo. Chamamos de
ciclo, uma vez que agrega duas propriedades inicia e termina no mesmo vértice, em , e é um
caminho.
Um ciclo é chamado de simples quando o único vértice que se repete é o inicial e o final. Desse modo, é
um ciclo simples.
Grafos planos
Como vimos, os grafos são entidades matemáticas abstratas. Entretanto, é muito comum representar um
grafo por meio de um diagrama. Via de regra, as pessoas referem-se à representação pictórica dele como o
próprio grafo. Apesar de incorreta, essa abstração é aceita.
Por isso, no decorrer de nosso estudo, vamos nos referir várias vezes ao grafo como um objeto contido em
uma figura.
Dado determinado grafo, é intuitivo pensar que não existe somente uma topologia para sua representação
gráfica. Pode-se desenhá-lo, afinal, de várias formas.
Atenção
O grafo K4, K4 é o grafo completo com 4 vértices. Já um grafo completo é todo grafo em que existe uma
aresta ligando cada par de vértices. 
Utilizamos a notação Kn para nos referirmos a um grafo completo com n vértices. Esta imagem representa K4:
Grafo completo de 4 vértices.
Observe que a entidade K4 é única, porém existem diversas formas de representar K4. A imagem adiante
exibe três possíveis representações para K4:
Múltiplas representações de K .
Observe que, mesmo sendo uma entidade única, há várias representações diferentes para K4. Além disso, as
três mostradas nessa figura não são as únicas: podemos idealizar outras.
Entretanto, existe uma diferença entre a representação "A" de K4 na figura para as representações em "B" e
"C". Nessas representações, o "desenho" do grafo não tem cruzamento das arestas. Além disso, nem todo
grafo admite uma representação pictórica sem cruzamentos delas. Grafo completo com cinco vértices, K5 não
admite.
A imagem a seguir demonstra a representação de K5. Não é possível desenhar esse grafo sem cruzamento
das arestas:
Grafo completo de cinco vértices.
A propriedade de que alguns grafos podem ser “desenhados” sem cruzamento de arestas induz a uma
classificação. Um grafo será denominado plano ou planar se sua representação gráfica puder ser feita de
forma que não haja cruzamentos das arestas, ou seja, todo grafo capaz de ser representado sem o
cruzamento delas. 
Reconhecer a planaridade e saber desenhar o grafo sem o cruzamento de arestas constituem um
problema com muitas aplicações. Pode-se destacar, por exemplo, o desenho de placas de circuitos
impressos em eletrônica.
Mas existem outras aplicações.
Uma malha viária é, via de regra, um grafo planar (desconsiderando, claro, as pontes, os viadutos e os túneis).
Além disso, o percurso otimizado de um itinerário também é um problema muito comum.
Hoje em dia, é fácil dirigir em uma cidade que não se conhece: basta, antes de ligar o carro, baixar um
aplicativo, como o Google Maps ou o Waze, e transitar sem maiores problemas. Mas você já se pergun-tou
como isso funciona?
Saiba mais
Um dispositivo GPS e um mapa associado a um modelo da cidade, que é um grafo. Dessa forma,
encontrar o caminho resume-se à aplicação de um algoritmo capaz de encontrá-lo entre um par de
vértices de um grafo. 
Alguns problemas envolvendo caminhos têm aplicação importante em logística. Dois deles destacam-se:
Percurso euleriano.
Percurso hamiltoniano.
Falaremos sobre ambos adiante.
Percurso euleriano
Alguns conceitos fundamentais
Antes de estudarmos o percurso euleriano, conheceremos algumas de suas definições. A primeira é a
definição de visita a um elemento do grafo.
Porém, antes de nos aprofundarmos na ideia, precisamos ter em mente que o grafo, para ser manipulado,
deve ser representado em memóriano computador. Basicamente, há duas formas de representá-lo em
memória, Observe a seguir:
Listas de adjacências Matriz de adjacências
Considere o grafo desta figura:
Grafo exemplo.
A estrutura de dados denominada listas de adjacência e que representa esse grafo é composta por listas,
em que é a cardinalidade do conjunto V. Cada lista é identificada pelo rótulo do nó origem da aresta.
Figuram nessa lista os nós destinos de cada aresta que parte do nó origem.
Para o grafo dessa imagem, teríamos a seguinte estrutura de dados:
Origem Lista de Destinos
A B,C
B A,D,G
C A,E,F
• 
• 
Origem Lista de Destinos
D B,E
E C,D,G
F C,H
G B,E,H
H G,F
Listas de adjacências.
Luiz Henrique da Costa Araujo.
A matriz de adjacências é uma matriz , em que é a cardinalidade de , sendo cada linha e coluna
de associada a um vértice do grafo. Assim, caso ; caso contrário, .
A matriz adiante é a matriz de adjacências para o grafo exemplo:
 A B C D E F G H
A 0 1 1 0 0 0 0 0
B 1 0 0 1 0 0 1 0
C 1 0 0 0 1 1 0 0
D 0 1 0 0 1 0 0 0
E 0 0 1 1 0 0 1 0
F 0 0 1 0 0 0 0 1
G 0 1 0 0 1 0 0 1
H 0 0 0 0 0 1 1 0
Matriz de adjacências do grafo exemplo.
Luiz Henrique da Costa Araujo.
Diz-se que visitamos um elemento do grafo (vértice ou aresta) quando acessamos tal elemento e realizamos
alguma operação. 
Atenção
Observe que visitar é diferente de acessar. Acessar é simplesmente encontrar o objeto na estrutura de
dados. Visitar, no entanto, significa encontrar (ou seja, toda visita pressupõe um acesso) e realizar uma
operação. 
Naturalmente, surge esta pergunta: que operação? A resposta é: qualquer uma! A operação é definida na
semântica do problema que queremos resolver, isto é, visitar pode se tratar simplesmente de im-primir um
rótulo do objeto (nó ou aresta) ou de realizar uma operação matemática complexa que tem sentido no domínio
do problema que queremos resolver. 
No escopo de nosso estudo, a visita é a impressão do rótulo do nó, uma vez que queremos a
sequência que define um caminho no grafo.
Definidos os conceitos básicos – que servem não somente para o estudo do percurso euleriano, mas também
para qualquer percurso em um grafo –, vamos definir agora o que significa um percurso euleriano.
Formulação do problema
A primeira formulação para o problema da determinação do percurso euleriano surgiu como um quebra-
cabeça. Na cidade de Königsberg, atual Kaliningrado, havia, no século XVIII, sete pontes sobre o Rio Pregel.
O quebra-cabeça era: é possível sair de uma margem do rio, cruzar uma única vez as sete pontes e voltar para
mesma margem? A imagem a seguir mostra a geografia do lugar:
Pontes de Königsberg.
A solução matemática do problema ficou em aberto por algum tempo até que o matemático Leonard Euler
propôs uma solução empregando a entidade matemática grafo. No modelo proposto por Euler, cada margem é
um nó e cada ponte, uma aresta.
Atenção
Observe que, no caso das pontes de Königsberg, ocorre uma flexibilização do conceito de grafo, uma
vez que há mais de uma ponte ligando a mesma porção de terra da cidade. 
Esta imagem exibe o grafo resultante do modelo de Euler: 
Comentário
Foi dito que o modelo proposto por Euler flexibilizava o conceito de grafo. Isso ocorreu pelo fato de haver
duas arestas idênticas: (A,B) e (B,C). Na definição de grafo, isso não é possível, uma vez que as arestas
formam um conjunto, e conjuntos não permitem a multiplicidade de elementos. 
Proposta de solução por Euler
Como dissemos, o problema de Königsberg permaneceu em aberto, isto é, sem solução, até Euler provar que
o percurso não existe por meio da postulação e prova do Teorema de Euler.
Eis o teorema:
Um grafo admite um percurso euleriano, isto é, existe um ciclo , que
contém todas as arestas de , sendo cada aresta visitada uma única vez se e somente se o grau de todos os
vértices for par.
Reunimos quatro observações sobre esse teorema:
O grau de vértice é o número de arestas incidentes a esse vértice.
 
No percurso euleriano, a operação de visita confunde-se com o acesso à aresta. Por isso, o simples
fato de acessá-la já é uma visita.
 
O teorema não informa como obter o percurso, e sim se ele existe. Desse modo, para o problema das
pontes de Königsberg, é possível afirmar que o percurso não existe.
 
O ciclo euleriano não é necessariamente simples.
A aplicação do Teorema de Euler mostra que o grafo é euleriano, ou seja, que existe um percurso euleriano.
Entretanto, a determinação do percurso não é aplicação direta do teorema.
Algoritmo de determinação do percurso euleriano
Existe um algoritmo relativamente simples para a determinação do percurso euleriano. Por isso, veremos
agora a ideia do algoritmo por meio de um exemplo.
O primeiro passo é determinar se o grafo admite o percurso. Isso é feito pela aplicação direta do Teorema de
Euler. Vejamos então o grafo exemplo, que é euleriano pela aplicação direta do teorema.
• 
• 
• 
• 
Grafo euleriano.
Observe que o grafo é euleriano, isto é, que existe um ciclo euleriano, o que pode ser determinado pela
aplicação do teorema. Isso representa o primeiro passo do algoritmo: saber se o grafo admite o ciclo.
Determinaremos agora o ciclo. Para fins de exemplo, vamos partir do vértice A.
A ideia básica do algoritmo é percorrer as arestas não visitadas, não retornando à origem – a menos que seja
inevitável. Assim, partindo de A, há quatro opções indistintas: percorrer (A, B), (A, C), (A, D) ou (A, E).
Vamos escolher qualquer uma dessas opções, como (A, D), por exemplo. Escolhida a opção (A, D), nosso ciclo
euleriano é .
Observaremos agora as opções para cada caso, indicando suas possibilidades:
D
Percorrer (D, C), (D, F) e (D, E), mas não (D, A), que, afinal, já foi percorrido. Como a escolha é
indistinta, escolhemos (D, F), obtendo-se o ciclo pAA=A, D, F.
F
Percorrer (F, C), (F, G) e (F, H), mas não (F, D). Escolhendo (F, C), obtém-se o ciclo pAA = A, D, F, C.
C
Percorrer (C, B), (C, A) e (C, D), mas não (C, F). Evitaremos (C, A), já que essa aresta nos leva para a
origem. Escolhendo (C, B), obtém-se o ciclo pAA= A, D, F ,C, B.
B
Percorrer (B, C) e (B, A). A opção (B, C) é proibida, pois já foi percorrida; dessa maneira, só resta (B,
A), obtendo-se o ciclo pAA = A, D, F, C, B, A.
A
Percorrer (A, C) e (A, E). As opções (A, D) e (A, B) já foram percorridas. Escolhendo (A, C), obtém-se o
ciclo pAA = A, D, F, C, B, A, C.
C
Percorrer (C, D) e (C, F). As opções (C, B) e (C, A) já foram exploradas. Escolhendo (C, D), obtém-se o
ciclo pAA = A, D, F, C, B, A, D.
D
As opções (D, E), (D, F), (D, C) e (D, A) já foram exploradas; assim, obtém-se o ciclo pAA = A, D, F, C, B,
A, D, E.
E
As opções (E, G), (E, H) e (E, D) já foram exploradas, enquanto a opção (E, A) precisa ser evitada.
Escolhendo (E, G), obtém-se o ciclo pAA=A, D, F, C, B, A, D, E, G.
G
Só existe a opção (G, F), obtendo-se o ciclo pAA = A, D, F, C, B, A, D, E, G, F.
F
Só há a opção (F, H). As opções (F, G), (F, D) e (F, C) já foram exploradas, obtendo-se o ciclo pAA= A,
D, F, C, B, A, D, E, G, F, H.
H
Só existe a opção (H, E), pois (H, F) já foi explorada. Desse modo, obtém-se o ciclo pAA = A, D, F, C, B,
A, D, E, G, F, H, E.
E
Só há a opção de explorar (E, A), única aresta não explorada, obtendo-se o ciclo pAA = A, D, F, C, B, A,
D, E, G, F, H, E, A. Esse é o ciclo euleriano do grafo.
Observe que o algoritmo é simples e executa em 0(m), em que m é a cardinalidade do conjunto de arestas do
grafo.
Calculando o percurso euleriano de um grafo
Neste vídeo, vamos executar o algoritmo para a determinação do percurso euleriano passo a passo.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Percurso hamiltoniano
Formulação do problema
Outro problema importante na teoria dos grafos com origem em um quebra-cabeça é o do percurso
hamiltoniano. O matemático Willian Hamilton inventou um jogo baseado na planificação de um dodecaedro
(sólido perfeito de doze faces).
Cada vértice do dodecaedro planificado foi rotulado com o nome deuma cidade. O jogador tinha de encontrar
um caminho que, partindo de uma cidade arbitrária, visitasse todas as cidades uma única vez e, ao final,
voltasse para a cidade de origem.
Esta imagem ilustra o tabuleiro do jogo:
Tabuleiro do jogo de Hamilton.
Uma das possíveis soluções para o quebra-cabeça é a da imagem a seguir:
Solução do quebra-cabeça de Hamilton.
O ciclo pA, A = A, F, L, Q, R, S, T, P, K, J, O, I, N, H, M, G, B, C, D, E, A é um ciclo que atende às restrições do
quebra-cabeça. O próprio tabuleiro do jogo já remete a um grafo; assim, podemos modelá-lo em um grafo e
enunciar o problema como um problema de obtenção de um percurso em um grafo e enunciar o problema
como um problema de obtenção de um percurso em um grafo.
Sendo assim, enunciamos o problema como:
Considere G=(V, E) um grafo. Diz-se que um ciclo PAA simples de G será hamiltoniano se P existir e
contiver todos os vértices de G.
Observe que o ciclo pAA = A, F, L, Q, R, S, T, P, K, J, O, I, N, H, M, G, B, C, D, E, A obtido na solução do jogo de
tabuleiro de Hamilton atende a essa propriedade. Grafos que possuem ciclos hamiltonianos são ditos grafos
hamiltonianos.
Infelizmente, não se conhece um resultado matemático capaz de caracterizar um grafo hamiltoniano. Na
verdade, existem resultados para algumas famílias de grafos com propriedades específicas.
Exemplo
Sabe-se que os grafos resultantes da planificação dos sólidos perfeitos de Platão (tetraedro, cubo,
octaedro, dodecaedro e icosaedro) são hamiltonianos. 
Algoritmo para obtenção do ciclo hamiltoniano de um grafo
Conforme já citamos, não existe um resultado matemático capaz de determinar se um grafo possui ou não um
ciclo hamiltoniano. Além disso, não se conhece uma propriedade que, quando aplicada, seja capaz de
conduzir escolhas algorítmicas que resultem no ciclo hamiltoniano.
A falta desses resultados matemáticos coloca o problema da obtenção do ciclo hamiltoniano em uma classe
de problema da qual não se conhece a solução algorítmica que resolve o problema em tempo polinomial.
Dica
Lembre-se de que resolver um problema em tempo polinomial significa que o número de operações
necessárias para encontrar a solução é proporcional a uma função matemática polinomial. 
Observe que não dizemos que a solução não existe, e sim que ela não é conhecida! Desse modo, ainda é uma
conjectura a existência ou não da solução polinomial. O único método exato para obtenção do ciclo
hamiltoniano é o exaustivo. Esse método consiste em:
1
Calcular todas as permutações possíveis dos
elementos contidos no conjunto de vértices do
grafo.
2
Verificar quais permutações são ciclos.
3
Verificar, por consequência, como tais
permutações contêm todos os vértices (ciclos
hamiltonianos).
Em uma primeira análise, parece que o problema estaria resolvido, o que de fato ocorre; entretanto, o número
de permutações distintas de elementos distintos é . Assim, para um grafo com 20
vértices (nosso dodecaedro do exemplo), há permutações possíveis.
Exemplo
Suponha que um computador seja capaz de tratar de 1 trilhão de operações por segundo. Nessa única
operação, ele conseguiria calcular e determinar se a permutação é um ciclo. Ainda assim, seu
processamento levaria segundos, isto é, aproximadamente 11 dias e meio! 
Nosso exemplo conta com um grafo pequeno. Usando seu poder cognitivo, um ser humano seria capaz de
resolver o problema em alguns minutos. Se aumentássemos o problema para um grafo com 70 nós, por
exemplo, já haveria a ordem de permutações distintas.
Se usássemos o mesmo computador, já precisaríamos de um tempo maior que a idade do universo para
resolver o problema. Por causa de seu caráter exaustivo, é impossível resolver o problema para grafos com
muitos nós.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Percurso euleriano
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Percurso hamiltoniano
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
O resultado matemático que caracteriza um grafo euleriano, isto é, um grafo no qual existe um ciclo euleriano
é o seguinte: um grafo G = (V, E) é euleriano se e somente se o grau de todos os seus vértices é par.
 
Aponte a alternativa com a interpretação correta desse resultado.
A
Se G = (V, E) possui todos seus vértices com grau par, então G é euleriano, porém pode existir um grafo com
vértices com grau ímpar contendo ciclos eulerianos.
B
Se for conhecido o ciclo euleriano do grafo, não será possível afirmar que não existem vértices com grau
ímpar.
C
O resultado matemático do enunciado é equivalente a duas proposições: 1) se G é euleriano, então todos os
vértices têm grau par; 2) se todos os vértices têm grau par, então G é euleriano.
D
O resultado matemático caracteriza uma condição necessária, porém não suficiente. Por isso, ele não pode
ser utilizado como método de caracterização.
E
A aplicação direta do teorema viabiliza a obtenção do algoritmo que calcula o ciclo euleriano.
A alternativa C está correta.
A letra A é falsa, pois o teorema é uma condição necessária e suficiente (ou seja, a D também é falsa);
portanto, caso exista o ciclo euleriano, todos os vértices têm um grau par. A B é falsa pela mesma
justificativa. A letra E também o é, uma vez que o resultado é de caracterização, mas não induz como se
deve percorrer o grafo para obter o ciclo. A letra C é verdadeira, em lógica, A se e somente se B é
equivalente à A, então B e B então A.
Questão 2
Analise as afirmativas a seguir que se referem a um grafo hamiltoniano:
 
Não existe resultado matemático para a caracterização de grafos hamiltonianos.
Não existe algoritmo polinomial que determine o ciclo hamiltoniano de um grafo.
A única forma conhecida e exata de se obter o ciclo hamiltoniano é por exaustão em tempo não
polinomial.
 
A
1, 2 e 3 são verdadeiras.
B
1 e 2 são falsas e 3 verdadeira.
C
1 é falsa e 2 e 3 verdadeiras.
D
1 e 3 são falsas e 2 verdadeira.
1. 
2. 
3. 
E
Todas são falsas.
A alternativa B está correta.
A opção 1 é falsa, pois o correto seria afirmar que não se conhece o resultado matemático para a
caracterização de grafos hamiltonianos. A 2 também é falsa, já que o problema é NP-difícil, o que significa
dizer que não se conhece o algoritmo: ele pode existir e, ainda assim, ser desconhecido. Não existe prova
da não existência do algoritmo. Por fim, a 3 é verdadeira: a busca exaustiva é a única forma conhecida por
enquanto.
2. Busca em grafos
Percursos em grafos
Base conceitual
Já verificamos que os grafos são utilizados para modelar redes ou malhas de quaisquer tipos.
Exemplo
É composta por um conjunto de ruas, cruzamentos de ruas e entroncamentos, a malha viária de uma
cidade pode ser facilmente modelada em um grafo e, com base nesse grafo modelo, utilizada para
resolver um problema de logística. 
Grande parte dos problemas em grafos é resolvido com o auxílio de um algoritmo computacional. Desse
modo, é necessário representar o grafo na memória do computador e manipular a informação contida.
Existem diversas formas de representar um grafo na memória do computador. Já vimos duas delas: as listas
de adjacências e a matriz de adjacências.
Como a informação está representada em memória, é necessário um método organizado para acessá-la.
Veremos agora dois métodos:
Percurso em largura. Percurso em profundidade.
Segundo Szwarcfiter (1986, p. 85) essa busca visa a resolver um problema básico: explorar um grafo, isto é,
um processo sistemático de como se caminha pelos vértices até as arestas do grafo.
Veremos, portanto, o algoritmo básico para se percorrer um grafo. O perfeito entendimento do processo
algorítmico, porém, demanda a definição e a fixação de alguns conceitos:
Vértice marcado
É o vértice visitado na busca. Lembre-se de que, como já definimos, a visita consiste em realizar uma
operação na semântica do problema. A semântica aqui significa associarum indicador (flag) ao
vértice, sinalizando a visita.
Aresta selecionada
É a aresta que, partindo de um vértice marcado v, atinge um vértice w adjacente a v (marcado ou
não). Dessa maneira, a operação de selecionar uma aresta constitui uma operação de visita, enquanto
a operação de seleção marca tanto a aresta (flag) quanto o vértice w adjacen-te a v (caso w ainda
não tenha sido marcado).
Algoritmo genérico de percurso
A operação de marcação dos vértices e de seleção das arestas divide os conjuntos e do grafo 
 em dois subconjuntos distintos: e . Trata-se respectivamente do subconjunto dos
vértices marcados e dos não marcados.
Já o conjunto das arestas divide-se em dois subconjuntos disjuntos: e . Eles são respectivamente os
subconjuntos das arestas selecionadas e não selecionadas.
Desse modo, inicialmente, temos que: , e . O primeiro passo do algoritmo
é escolher arbitrariamente um vértice não marcado e adicioná-lo ao conjunto . Vejamos agora o passo
geral do algoritmo. Enquanto , deve-se fazer o seguinte:
1° passo
Escolha uma aresta não selecionada que parte de um vértice marcado x, sendo (x,y) essa aresta.
2° passo
Remova-a do conjunto E′′ e a adicione em E′.
3° passo
Remova, em seguida y de V′′, adicionando-o ao conjunto V′′.
Ao final do algoritmo, todos os vértices estarão marcados; todas as arestas, selecionadas; e o grafo,
percorrido.
O algoritmo de percurso é genérico e não define uma única forma de explorar o grafo.
Vejamos um exemplo com o grafo a seguir:
Grafo exemplo.
Observemos a aplicação do algoritmo:
1 - Passo inicial:
2 - Primeiro passo do passo geral: trata-se de escolher uma aresta com origem em A não marcada. Considere
(A, B) essa aresta. Em seguida, deve-se marcar B caso ele não esteja marcado. Com isso, passamos a ter:
Como , continuamos. Agora podemos escolher qualquer aresta não marcada com origem em ou 
.
Considere a aresta escolhida. Como não está marcado, marca-se . Assim, passamos a ter:
Como , continuamos. Agora podemos escolher qualquer aresta não marcada com origem em 
ou .
 
Considere a aresta escolhida. O vértice já está marcado; por isso, ele não será marcado mais uma
vez. Com isso, obtém-se:
Como , continuamos a poder escolher uma aresta com origem em ou . Considere a
aresta escolhida.
O vértice não está marcado. Desse modo, obtemos:
Como , continuamos. Agora podemos escolher qualquer aresta com origem ou . Vamos
escolher .
O vértice não está marcado. Dessa forma, marca-se , obtendo:
Como , continuamos. Agora só temos a opção de escolher a aresta , pois todas as outras já
estão marcadas. Isso resulta em:
Como , o algoritmo para.
Observe que o algoritmo de percurso visita sistematicamente todos os vértices e arestas do grafo sem
repetição. Isso é feito em um tempo proporcional a , em que é a cardinalidade de e , a
cardinalidade de .
Percurso em largura
Definição
No item anterior, mostramos um algoritmo que executa o percurso de um grafo. No entanto, vimos que o
resultado obtido pelo algoritmo não é único, já que o critério para a escolha da próxima aresta a ser visitada é
fraco.
A ideia do percurso em largura é tornar o critério de escolha da aresta mais rígido. Para isso, usaremos uma
fila, ou seja, a próxima aresta a ser explorada no percurso será a primeira da fila.
Algoritmo de percurso em largura
Observe que a aplicação da fila é uma pequena alteração no algoritmo de percurso genético, ficando da
seguinte forma:
O passo inicial é particionar o conjunto de vértices em dois conjuntos disjuntos: e . Em
seguida, deve-se fazer o mesmo com , obtendo .
Além desses conjuntos, teremos uma fila inicialmente vazia. Ainda no passo inicial, escolhemos
arbitrariamente um elemento de como o primeiro nó visitado e inserimos todas as arestas incidentes a 
 em .
Dica
Lembre-se de que F é uma fila, ou seja, uma lista com a política FIFO (First in, first out, ou seja, o
primeiro a entrar na fila é o primeiro a sair dela). 
Vamos escolher, por exemplo, como o vértice inicial. São incidentes ao vértice as arestas e 
. Inserindo na fila nessa ordem, teremos a fila .
Assim, ao final do passo inicial, vemos que:
Observemos agora o passo geral do algoritmo. Enquanto , vamos fazer o seguinte:
Remover de a aresta do início da fila.
Inserir e em .
Caso , inserir em , vamos fazer:
Analisar todas as arestas incidentes a e
As não visitadas, Inserir em e removê-las de .
Caso contrário, isto é: , a operação está completa.
Vamos executar a busca em largura neste grafo exemplo:
Grafo exemplo.
Escolhendo o vértice A como inicial, teremos:
Como , removemos o primeiro elemento de F, que é o arco (A,B).
O vértice não está marcado. Após marcar , inserem-se as arestas não visitadas incidentes a em ,
obtendo o seguinte:
Como , removemos o primeiro elemento de , que é o arco .
O vértice não está marcado. Após marcar , as arestas não visitadas incidentes a em são
inseridas, obtendo isto:
Como , removemos o primeiro elemento de , que é o arco . vértice não está
marcado. Após marcar , inserem-se as arestas não visitadas incidentes a em , obtendo o seguinte:
Como , removemos o primeiro elemento de , que é o arco .
O vértice está marcado; logo, a operação está concluída:
Como , removemos o primeiro elemento de , que é o arco . vértice não está
marcado. Após marcar , são inseridas as arestas não visitadas incidentes a em , obtendo:
Removemos o primeiro elemento de , que é o arco . O vértice está marcado, e isso finaliza a
operação.
Como , então o percurso finalizou.
A imagem adiante exibe a ordem de visitação de arestas e vértices. Colorimos o vértice e a aresta de
vermelho à medida que eles são visitados.
 e 
 e 
 e 
Percurso em largura (passo a passo).
Calculando o percurso largura de um grafo
Neste vídeo, vamos executar o algoritmo para a determinação do percurso em largura passo a passo.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Percurso em profundidade
Definição
Assim como o percurso em largura, o percurso em profundidade é o estabelecimento de um critério mais
rígido para escolha da próxima aresta visitada. Nesse percurso, a estrutura de dados utilizada para organizar a
ordem de visita das arestas é a pilha.
Dica
A pilha é a estrutura de dados linear que permite duas operações: PUSH (inserir na pilha) e POP (remover
da pilha). Sua política de operação é a LIFO (Last in, first out, isto é, o primeiro elemento a ser removido
da pilha é o último que foi inserido). 
Algoritmo do percurso em profundidade
Vejamos então o algoritmo do percurso em profundidade de um grafo.
O passo inicial é particionar o conjunto de vértices em dois conjuntos disjuntos: e 
É preciso fazer o mesmo com , obtendo . Além desses conjuntos, teremos uma pilha 
inicialmente vazia.
Ainda no passo inicial, escolhemos arbitrariamente um elemento de como o primeiro nó visitado e
inserimos todas as arestas incidentes a em .
Grafo exemplo.
Tomando o grafo dessa figura como exemplo e escolhendo A como vértice inicial, veremos que as estruturas
de dados serão inicializadas da seguinte forma: 
Atenção
Para que a pilha esteja na configuração acima, a ordem de inserção das arestas foi a seguinte: 1ª a ser
inserida (A, B) e 2ª a ser inserida (A, C). Entretanto, essa escolha foi arbitrária, uma vez que não existe
ordem no conjunto de arestas incidentes em um nó. 
Vejamos o passo geral. Enquanto , vamos remover uma aresta da pilha e inserir em 
.
Caso não esteja marcado, isto é, , teremos de inserir todas as arestas não marcadas incidentes a 
em e removê-las de . Em seguida, vamos inserir em .
Continuando nosso exemplo, removemos da pilha. O vértice não está marcado. Por isso, vamos
marcar , isto é, remover de e inseri-lo em .
Em seguida, inserimos na pilha todas as arestas incidentes a não marcadas. Com isso, obteremos esta
configuração:
Como , continuamos o algoritmo.
A próxima aresta removida de é . O vértice não está marcado; assim, marcamose inserimos
todas as arestas não marcadas incidentes a , isto é, pertencentes ao conjunto na pilha.
Obteremos, desse modo, a configuração adiante:
No próximo passo, removemos (E, D) da pilha. O vértice D não está marcado; portanto, marcamos D. A única
aresta incidente a D não marcada é (B,D). 
Lembre-se de que (B,D)=(D,B)! Dessa forma, inserimos (B,D) na pilha, obtendo o seguinte:
Ao remover da pilha, observamos que não está marcado. Por isso, devemos marcá-lo.
Como não existem arestas não marcadas e , continuamos o algoritmo com base nos dados:
Removemos da pilha. Como todos os vértices ao qual é incidente estão marcados, marcamos
somente a aresta como visitada e continuamos o algoritmo com base nos dados:
Em seguida, removemos da pilha. e estão marcados; assim, nada é executado e ,
concluindo o algoritmo. Desse modo, obtemos este resultado:
A figura a seguir mostra a ordem de visitação das arestas e dos vértices. Como já frisamos, colorimos de
vermelho o vértice e a aresta já visitados.
Percurso em profundidade (passo a passo).
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Base conceitual – percursos em grafos
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
O percurso em profundidade
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Vimos que o percurso ou a busca no grafo é um método sistemático de acesso aos elementos do grafo.
Analise as afirmativas a seguir e determine se são verdadeiras em relação à busca.
 
Na busca, as arestas são acessadas uma única vez.
Na busca, os vértices são acessados uma única vez.
Na busca, os vértices e as arestas são visitados uma única vez.
 
A
I e II são verdadeiras.
B
Somente a I é verdadeira.
C
I e III são verdadeiras.
D
Somente a III é verdadeira.
E
II e III são verdadeiras.
A alternativa D está correta.
1. 
2. 
3. 
Verificamos que o acesso é diferente da visita. O acesso ocorre quando a aresta ou o vértice é manipulado
pelo algoritmo sem sofrer uma operação. Lembre-se ainda de que a operação é definida na semântica do
problema. Sendo assim, existem pelo menos dois acessos aos vértices e às arestas durante o percurso,
porém a visita é feita uma única vez.
Questão 2
No algoritmo básico de percurso, não existe um critério de escolha da próxima aresta a ser visitada. A escolha
dela, portanto, é arbitrária. Essa característica faz com que possa haver múltiplas formas de percurso com o
algoritmo básico. Para mitigar isso, são empregadas estruturas de dados auxiliares: a pilha e a fila. O emprego
dessas estruturas deriva o algoritmo básico em dois outros algoritmos de percurso: a busca em largura e a
busca em profundidade. Analise as afirmativas adiante e determine quais são verdadeiras.
 
I - A busca em largura utiliza a fila como estrutura de organização de escolha das arestas a serem visitadas, e
a fila tem uma política de acesso FIFO.
 
II - A busca em largura usa a pilha como estrutura de organização de escolha das arestas a serem visitadas, e
a fila tem uma política de acesso LIFO.
 
III - A busca em profundidade emprega a fila como estrutura de organização de escolha das arestas a serem
visitadas, e a fila tem uma política de acesso FIFO.
 
IV - A busca em profundidade utiliza a pilha como estrutura de organização de escolha das arestas a serem
visitadas, e a fila tem uma política de acesso LIFO.
 
V - A busca em profundidade ou a busca em largura pode escolher a pilha ou a fila como estrutura de dados
auxiliar, e isso não impacta no resultado final.
 
A
Somente a V é correta.
B
I e III são corretas.
C
I e IV são corretas.
D
II e III são corretas.
E
Todas estão corretas.
A alternativa C está correta.
A I é correta: a fila é a forma de organizar o acesso às arestas na busca em largura. A II é falsa por
consequência de I. Já a III é falsa pelo fato de a busca em profundidade utilizar uma pilha para organizar o
acesso às arestas. A IV é verdadeira por consequência da III. Por fim, a V é falsa, porque cada algoritmo de
busca tem seu critério.
3. Propriedades elementares de árvores em grafos
Árvores, subgrafos e árvores geradoras
Definição
Apresentamos nos módulos anteriores o conceito de grafo e de ciclos. Também vimos que os caminhos em
grafos são importantes abstrações, tendo diversas aplicações na solução de problemas reais.
Nesse contexto, existe uma família de grafos com a propriedade de não possuir ciclos. Assim, diz-se que um
grafo conexo G=(V, E) que não possui ciclos é uma árvore.
Esta imagem ilustra uma árvore:
Árvore.
O teorema adiante caracteriza as principais propriedades das árvores:
Sendo um grafo com , são equivalentes as seguintes afirmações:
G é sem ciclos e conexo, ou seja, G é uma árvore.
G é sem ciclos e tem n-1 arestas.
G é conexo e tem n-1 arestas.
G é sem ciclos, e a adição de uma aresta qualquer cria um ciclo único.
 é conexo, mas é não conexo .
Sejam e vértices distintos de , existe um caminho único entre .
Observe que todas as propriedades acima valem para a árvore exemplo. No grafo da figura exemplo acima:
1
Primeiro
O grafo é conexo e sem ciclos.
2
Segundo
Ele tem n−1 arestas, uma vez que n=5, e o grafo possui 4 arestas.
1. 
2. 
3. 
4. 
5. 
6. 
3 Terceiro
G é conexo e tem 4 arestas.
4
Quarto
A adição de qualquer aresta cria um ciclo.
5
Quinto
A remoção de qualquer aresta desconecta o grafo.
6
Sexto
Existe caminho único entre qualquer par de vértices.
A análise de tais propriedades nos mostra que as árvores são as estruturas mais simples capazes de conectar
um conjunto de vértices. Não é possível, portanto, conectar vértices com menos que arestas.
A propriedade de as árvores possuírem arestas faz com que o grafo conexo com o mínimo de
elementos, isto é, com valor mínimo, seja uma árvore. Desse modo, a forma mais econômica de
construir uma rede (seja de distribuição logística ou de dados) é construir uma árvore. Dessa forma, vamos
introduzir adiante o conceito de subgrafo:
Muito se pode falar dos subgrafos de um grafo. Mas são as árvores que nos interessam; assim, se é um
grafo conexo, existe ao menos um subgrafo de , que é uma árvore. Caso seja subgrafo de e 
, uma árvore, dizemos que será uma árvore geradora de . A imagem adiante ilustra em vermelho
uma árvore geradora de um grafo :
Subgrafo de um grafo.
Sendo um grafo, um subgrafo de é o grafo tal que e 
.
Observe que o grafo da figura acima é conexo, porém não é uma árvore, uma vez que tem
ciclos. Em vermelho, destacamos um subgrafo de .
Observe que . Como vimos, , pelas propriedades das árvores, é uma árvore e , um
subgrafo de . Desse modo, é árvore geradora de .
Algoritmo de obtenção de uma árvore geradora do grafo
Podemos obter uma árvore geradora de um grafo por meio de seu percurso. Tanto o algoritmo de
percurso em largura quanto o de percurso em profundidade podem fornecer uma árvore geradora do grafo 
 .
As árvores determinadas com percursos diferentes serão diferentes entre si; logo, dado um grafo conexo,
pode existir mais de uma árvore geradora desse grafo. Para mostrarmos a obtenção da árvore geradora de um
grafo, vamos aplicar o percurso em largura.
Falamos sobre o algoritmo no módulo anterior. Relembrando, ele é composto por dois passos. O primeiro
passo é inicializar a estrutura de dados da seguinte forma:
Conjunto dos vértices marcados .
Conjunto dos vértices não marcados .
Fila .
Conjunto das arestas marcadas .
Conjunto das arestas não marcadas .
Escolher arbitrariamente um vértice e o inserir no conjunto dos vértices marcados .
Remover todas as arestas incidentes a de e inserir na fila .
Vejamos agora o passo geral. Enquanto , vamos fazer o seguinte:
1
Remover de F a aresta e=(x,y) do início da fila.
2
Inserir e em EM.
3
Inserir, caso y ∉ VM, y em VM.
4
Analisar todas as arestas incidentes a y e aquelas não visitadas.
5
Inserir em F e removeressas arestas de ENM caso y ∈ VM.
• 
• 
• 
• 
• 
• 
• 
A operação está completa.
Após relembrarmos o algoritmo, vamos agora analisá-lo. Observe que, a cada passo dele, visitamos uma
aresta do grafo .
Na visita da aresta , duas coisas podem acontecer:
Apenas um dos vértices x ou y foi
visitado.
Os dois vértices x e y já foram visitados.
Podemos usar esse fato para separar o conjunto de arestas em dois subconjuntos disjuntos: o conjunto 
(contém as arestas da árvore geradora de ) e o (conta com as arestas não pertencentes à árvore
geradora de .
Faremos isso da seguinte forma:
Observe que a primeira vez que um vértice é acessado significa que ele foi visitado.
Consequentemente, ele é inserido no conjunto de vértices visitados.
Isso aponta que, considerando os vértices e as arestas já visitados, a aresta não fecha um ciclo
em . Desse modo, pertence a uma árvore geradora de . Caso contrário
(em que e já tenham sido visitados), a aresta fecha um ciclo e, por isso, não pode pertencer
à árvore geradora de .
No módulo anterior, executamos passo a passo o algoritmo em um grafo exemplo. O resultado está expresso
na imagem a seguir:
Percurso em largura.
Nessa imagem, as arestas visitadas foram marcadas de vermelho. As arestas sólidas são as do caso 1,
atingindo um vértice ainda não marcado; as tracejadas, as do caso 2, alcançando um vértice já visitado. 
O subgrafo composto pelas arestas sólidas compõe, assim, uma árvore geradora do grafo original. Um
raciocínio análogo pode ser feito com o percurso em profundidade. No entanto, a árvore geradora obtida é
diferente.
Percurso em profundidade.
Assim como no exemplo estudado no percurso em largura, as arestas em vermelho sólido compõem, no
percurso em profundidade, uma árvore geradora de .
Árvores geradoras mínimas
Conforme estudamos, todo grafo conexo tem, pelo menos, uma árvore geradora. Caso haja mais de uma
árvore, não haverá distinção entre elas, já que todas têm exatamente arestas e nós.
Observe que a árvore geradora pode não ser única, isto é, dado um grafo, pode haver diversas árvores com
topologias diferentes. Entretanto, todas terão exatamente arestas e nós.
Verificamos ainda que, para um grafo qualquer, existem várias árvores geradoras mínimas e que todas têm as
mesmas propriedades. Mas o que ocorre se associarmos um peso às arestas?
Saiba mais
Um peso é um número que denota determinada grandeza. Ele pode ser, por exemplo, a distância entre
dois nós caso o grafo modele uma malha viária ou uma capacidade de canal se ele modelar uma rede de
telecomunicações. Para nós, porém, o peso é simplesmente um número associado à aresta. 
Esta imagem representa um exemplo de grafo ponderado:
Grafo ponderado.
Nessa figura, por exemplo, a aresta tem peso 3 e a aresta , peso 5. Vejamos agora a definição
matemática de grafo ponderado.
O grafo será chamado de grafo ponderado quando:
1
 for o conjunto de vértices.
2
 for o conjunto de arestas.
3
 for uma função definida, como, por exemplo,
.
Considere uma aresta de . Chamamos de peso de o valor de .
Para os grafos ponderados, não é verdade que todas as árvores geradoras são iguais. Vamos analisar o grafo
ponderado exemplo.
Na imagem adiante, destacamos duas árvores geradoras: uma, em vermelho; outra, em azul.
Árvores geradoras de um grafo ponderado.
As árvores em vermelho e azul têm topologia diferente. Mas será essa sua única diferença? A resposta é não.
Observe que, se somarmos os pesos das arestas da árvore vermelha, teremos o valor 12; se somarmos os da
árvore azul, o valor 14. Como a soma dos pesos da aresta da vermelha é menor que a da azul, dizemos que o
peso da vermelha é menor que o da azul.
Dessa forma, definimos o peso de uma árvore geradora de um grafo ponderado como a soma de
todos os pesos das arestas da árvore geradora do grafo.
Vimos também que o peso de árvores geradoras diferentes pode ser distinto. Se elencarmos todas as árvores
geradoras de determinado grafo ponderado, a de menor peso será chamada de árvore geradora mínima.
Veremos no próximo módulo que existem diversas aplicações das árvores geradoras mínimas. Antes dessas
aplicações, contudo, vamos entender como se determina a árvore geradora mínima de um grafo.
Algoritmo de Prim
O algoritmo de Prim pode ser descrito como o processo de, dado um grafo ponderado e um vértice inicial,
determinar a árvore geradora mínima do grafo em questão. O algoritmo de Prim é um algoritmo guloso.
Algoritmo guloso
Algoritmos gulosos são aqueles que constroem a solução do problema iterativamente, escolhendo a
opção mais promissora a cada iteração. Porém, no caso da árvore geradora mínima, pode-se provar que
essa abordagem funciona, isto é, que o resultado do algoritmo é, de fato, a árvore geradora mínima.
Conforme dissemos, o algoritmo de Prim é iterativo. Considere, por exemplo, o grafo
ponderado para o qual se deseja determinar a árvore geradora mínima.
A ideia básica do algoritmo é particionar o conjunto de vértices em dois subconjuntos disjuntos:
V’
Conjunto dos vértices que já pertence à árvore
geradora mínima.
V’’
Conjunto dos vértices que ainda não pertence à
árvore geradora mínima.
Note ainda que e .
O algoritmo de Prim é iniciado da seguinte forma: o conjunto é inicializado com um vértice arbitrário de 
.
Dica
Não fará diferença no resultado final do algoritmo qual vértice foi escolhido na inicialização. Isso se deve
ao fato de que não importa a ordem: de qualquer forma, o vértice inicial fará parte da árvore gera-dora
mínima. 
Desse modo, temos:
O passo geral do algoritmo de Prim é definido por: enquanto faça: Sejam os vértices e 
.
As arestas da forma conectam a partição de vértices já pertencentes à árvore geradora, que são os
vértices pertencentes a , com os vértices ainda não pertencentes à árvore, que são os vértices contidos
em , escolhendo a aresta de menor peso. Após essa escolha, devemos remover de e inserir em 
.
Vamos acompanhar a execução do algoritmo no grafo exemplo desta imagem:
, em que e 
Grafo exemplo.
Façamos a inicialização do algoritmo. Vamos inicializar os conjuntos e 
, o que indica que o algoritmo não acabou. No passo geral, escolhemos a aresta de menor peso entre
os nós de e .
As candidatas são:
A abordagem gulosa escolhe a aresta de menor peso, que é , que tem peso 2. A aresta é
inserida no conjunto , que é o conjunto de arestas da árvore geradora mínima.
Assim, ao final da execução do passo, verificamos que:
Graficamente, o resultado intermediário é apresentado no grafo a seguir. Os vértices e as arestas em vermelho
pertencem à árvore geradora mínima.
 
Prim (primeiro passo).
Como , o algoritmo continua. Agora temos:
Já as arestas candidatas são:
A aresta de menor peso é , que tem peso Desse modo, temos isto:
O resultado intermediário é apresentado a seguir:
 
 
 
Prim (segundo passo).
Como , o algoritmo continua. Agora temos:
Já as arestas candidatas são:
Duas arestas têm menor peso: e . Podemos escolher qualquer uma das duas.
Vamos escolher . Com isso, verificamos que:
O resultado intermediário é apresentado a seguir:
 
 
 
Prim (terceiro passo).
Como , o algoritmo continua.
Agora temos:
Já as arestas candidatas são: 
A de menor peso é . Dessa forma, temos o seguinte:
Veja agora o resultado intermediário nesta imagem: 
 
 
Prim (quarto passo).
Como, ao final desse passo, , o algoritmo para, e a árvore geradora é a destacada em vermelho nessa
figura. Observe ainda que o custo dessa árvore é 12 , que corresponde à soma de:
Calculando a árvore geradora mínima de um grafo pelo algoritmo de Prim
Neste vídeo, vamos executar o algoritmo de Prim passo a passo.
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Algoritmo de Kruskal
Assim como o Prim, o algoritmo de Kruskal encontra a árvore geradora mínima de um grafo. Esse algoritmo
pode ser descrito de forma bastante simples.
Para entendê-lo, basta:
Ordenar o conjunto de arestas de forma crescente pelos seus pesos.Analisar uma a uma, escolhendo a aresta para compor a árvore geradora mínima (caso ela não feche
um ciclo com os vértices já selecionados nos passos anteriores).
Para saber se a aresta analisada fecha um ciclo, só é preciso verificar se ela conecta dois vértices distintos
pertencentes à mesma componente conexa do grafo.
1. 
2. 
Essa verificação pode ser feita de forma simples. Só é necessário:
1
Criar um vetor de inteiros de tamanho n, em
que n é a cardinalidade do conjunto de vértices.
2
Associar cada posição do vetor com um vértice
distinto do grafo.
3
Inicializar os vértices com os valores 0, 1, 2, ... ,
n (já que, inicialmente, todos os vértices da
árvore geradora mínima estão desconectados).
Ao aceitar uma aresta na árvore geradora mínima, o valor armazenado no vetor, relativo aos vértices
conectados, com o menor valor armazenado no vetor para os vértices conectados pela aresta selecionada.
Vamos ilustrar o funcionamento do algoritmo com o grafo exemplo desta imagem:
Grafo exemplo.
Considere o grafo ponderado para o qual queremos encontrar a árvore geradora mínima.
Utilizaremos, nesse caso, dois conjuntos:
V'
Conjunto dos vértices pertencentes à árvore
geradora mínima.
V''
Conjunto dos vértices não alcançados ainda.
O vetor C controla as componentes conexas da futura árvore geradora a Os conjuntos e o vetor serão
inicializados assim: . O vértice é associado ao
índice , ao índice 1 - e assim por diante. Por fim, a lista
Dica
Os números que se seguem após a aresta são o peso da aresta. 
Na primeira iteração, retiramos da lista. Os dois vértices não estão contidos em ; assim, ambos
são inseridos em e , em , que é o conjunto de arestas da árvore geradora mínima.
Além disso e o menor valor armazenado para cada vértice é 0 , a aresta conecta
as componentes conexas de e , assim todos os elementos que armazenam 1 no vetor deverão
armazenar 0.
Ao final do passo, temos:
Já a lista .
A imagem adiante ilustra o passo 1:
 
 
Algoritmo de Kruskal: passo 1.
No próximo passo, a lista de arestas está configurada deste modo:
Removemos a aresta de menor peso, que é , de peso 2 . Verificamos, em seguida, se ela pode ser
inserida na árvore. Isso é feito mediante a análise do vetor .
 vértice corresponde à posição 1 e , à posição 2 . Como e , a aresta 
conecta componentes conexos distintos; logo, pertence à árvore geradora mínima.
Ao final do passo, temos:
Já a lista .
A imagem adiante, ilustra o passo 2.
 
Algoritmo de Kruskal: passo 2.
Mas o algoritmo não terminou, uma vez que . A lista de arestas está configurada como a seguir:
Removemos a aresta de menor peso, que é , de peso 3 . Verificamos depois se ela pode ser inserida
na árvore, o que é feito pela análise do vetor .
O vértice corresponde à posição 2 e , à posição 3 . Como , a aresta 
conecta componentes conexos distintos; por isso, pertence à árvore geradora mínima.
Já a lista .
A imagem adiante ilustra o passo 3:
 
Algoritmo de Kruskal: passo 3.
A lista está configurada da seguinte forma: .
A próxima aresta a ser analisada é , que é de peso 3. O vértice corresponde à posição e 
, à posição .
Como as duas posições contêm o valor zero armazenado, a aresta fecha um ciclo em um componente
conexo. Por isso, ela não pertence à árvore geradora mínima. 
Ao final do passo, temos o seguinte:
Já a lista . O mesmo ocorre com a próxima aresta da fila (B,D). Sendo
assim, essa aresta não pertence à árvore geradora mínima. Ao final do passo, a estrutura de dados contém o
seguinte:
Já a lista .
No próximo passo, será analisada a aresta cujo peso é 5 . O vértice corresponde à posição 
; o vértice , à posição . Dessa maneira, a aresta conecta componentes
desconexos e será utilizada na árvore geradora mínima.
Ao final do passo, teremos:
 
 
Já a lista .
A imagem adiante ilustra o resultado do passo 6:
Algoritmo de Kruskal: passo 6.
Como , o algoritmo para. A árvore acima é a árvore geradora mínima do grafo.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Árvores, subgrafos e árvores geradoras
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Árvores geradoras mínimas
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Analise as afirmativas a seguir:
 
Todo grafo possui uma árvore geradora.
A árvore geradora de um grafo com n vértices, se existir, possui exatamente n-1 arestas.
A árvore geradora de um grafo, se existir, pode não ser única.
 
A
Todas são verdadeiras.
B
Somente a I é verdadeira.
C
Somente a II é verdadeira.
D
II e III são verdadeiras.
E
I e III são verdadeiras.
A alternativa D está correta.
A afirmativa I é falsa: todo grafo conexo possui uma árvore geradora. A II é verdadeira, pois uma árvore com
n vértices possui sempre n-1 arestas. Tal afirmativa deriva diretamente do teorema de caracterização das
árvores. A III também é verdadeira, uma vez que a árvore geradora de um grafo só é única quando o grafo
já é uma árvore. Nessa situação, a árvore geradora da árvore é ela mesma.
Questão 2
Considere G um grafo conexo ponderado e analise as afirmativas a seguir:
 
1 - A aplicação do algoritmo de Kruskal fornece sempre a mesma árvore geradora mínima...
 
Porque
1. 
2. 
3. 
 
2 - Um grafo ponderado G sempre possui uma árvore geradora mínima única.
 
A
I e II são falsas.
B
I é falsa, e II é verdadeira
C
I é verdadeira, e II é falsa.
D
I e II são verdadeiras, porém II não justifica I.
E
I e II são verdadeiras, e II justifica I.
A alternativa A está correta.
A afirmativa I é falsa, pois, em determinada iteração do algoritmo, pode haver um empate na escolha da
aresta que vai compor a árvore geradora mínima; assim, o mesmo algoritmo pode dar resultados diferentes.
A II também é falsa, porque um grafo pode ter mais de uma árvore geradora mínima. O exemplo deste
módulo ilustra tal situação.
Isaac Newton.
4. Aplicações de algoritmos de busca em grafos
Teoria dos grafos e a vida prática
A importância da matemática discreta no cotidiano
Não é novidade para nós que a matemática habita o nosso cotidiano. Nas atividades mais simples, como, por
exemplo, uma compra no mercado, até as mais complexas, como os cálculos estruturais de um edifício. Esses
exemplos são aplicações da matemática dos números reais e das funções contínuas.
Por outro lado, os grafos são entidades discretas e finitas. Trata-se de uma matemática um pouco diferente
com que estamos acostumados, mas isso não significa que ela seja menos importante.
O segmento da matemática que estuda a teoria de grafos e conjuntos discretos é chamada de
matemática discreta. Tal segmento tem aplicações em diversas áreas importantes na vida moderna.
Neste módulo, vamos nos concentrar em problemas que podem ser resolvidos pela teoria dos grafos – mais
especificamente, por percursos em grafos. Essa teoria tem aplicações em diversas áreas, como, por exemplo,
logística, otimização combinatória, redes de computadores e fluxos de dados ou veículos. 
A importância da modelagem matemática
Sem dúvida, o primeiro passo para a solução de
um problema é construir um modelo
matemático que nos ajude a explicar o
fenômeno que queremos entender. Um dos
primeiros a fazer isto foi Isaac Newton, que
teve de “inventar” o cálculo para modelar o
movimento de corpos na cinemática.
 
Newton usou um conjunto de equações
matemáticas para descrever o movimento de
um corpo que se move em velocidade
constante ou com aceleração constante. O
modelo da cinemática newtoniana tornou-se a
base para diversas conquistas tecnológicas da
humanidade.
Os grafos na vida prática
Os grafos são candidatos naturais para modelar redes, seja essa rede de comunicação de dados viária, de
relacionamentos ou social. A modelagem de uma rede em um grafo é praticamente natural.
Exemplo
Pode-se facilmente transformar um mapa das ruas de uma cidade, que é uma malha, em um grafo.Para
fazê-lo, basta transformar os cruzamentos das ruas em nós; as ruas, em arestas; e os pesos das arestas,
nas distâncias físicas entre as esquinas. 
A figura adiante mostra um exemplo dessa modelagem:
GPS com software de navegação embarcado.
Grafo modelando malha viária.
Aplicações práticas
Roteamento em vias públicas
Talvez você não lembre, mas, há quinze ou vinte anos, era praticamente impossível dirigir um automóvel em
uma cidade grande, como Rio de Janeiro ou São Paulo, se você não morasse nesse local. A sinalização
deficiente e o crescimento urbano desordenado faziam das ruas dessas cidades verdadeiros labirintos.
A evolução tecnológica tornou o GPS (sistema de posicionamento global) um dispositivo barato. Hoje em dia,
todo os celulares têm um dispositivo GPS embarcado em seu hardware. A consequência disso é que
facilmente obtemos nossa localização com uma precisão de metros.
Aliada à modelagem da malha viária em um
grafo, a georreferenciação (localização do
objeto no mapa) permitiu a aplicação de
algoritmos de caminhos em grafos para
viabilizar a navegação assistida pelas ruas da
cidade.
Os principais produtos foram os aparelhos de
GPS popularizados nos anos 2000.
O algoritmo utilizado pelo dispositivo é o LGS
(Level graph search, ou seja, busca em grafos
em níveis), aponta Shapiro (1992). Esse
algoritmo é uma variante do algoritmo de Dijkstra, que encontra o menor caminho em um grafo direcionado
ponderado.
O LGS modela a malha viária em níveis. Ele opera basicamente três níveis:
Caminhão de transporte de mercadorias.
Primeiro nível
É associado às vias locais de uma cidade e às
pequenas ruas (normalmente, residenciais),
esse é o mais baixo.
Segundo nível
É associado às vias de acesso da cidade, que
são vias secundárias que conectam as vias
locais às preferenciais.
Terceiro nível
É associado às vias preferenciais, que são as
grandes avenidas dela.
A ideia do LGS é levar alguém rapidamente até uma via preferencial, navegando pelas preferenciais até chegar
o mais próximo possível ao destino. Em seguida, o algoritmo faz o reverso, conduzindo a pessoa a uma via de
acesso; se o destino dela for uma via local, ele a conduzirá até a via desejada.
Como funcionam os sistemas de navegação GPS
Como funcionam os aplicativos de navegação urbana?
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Distribuição de mercadorias
Mais uma vez, imagine que você disponha da malha viária da sua cidade modelada em um grafo. Suponha
ainda que você tenha uma empresa que fornece seus bens vendidos em domicílio, como uma distribuidora de
bebidas, por exemplo.
Você recebe o pedido de seus clientes e faz a
distribuição com um pequeno caminhão.
Uma forma de reduzir os custos operacionais é
fazer com que ele rode o menos possível, isto
é, que o caminhão saia de seu depósito e faça o
circuito de entrega percorrendo a menor
distância possível.
O problema em questão chama-se PRV. Do
ponto de vista de um grafo, tal problema pode
ser enunciado da seguinte forma:
Sendo G=(V,E) um grafo cujo conjunto de vértices é composto por um vértice especial “D”, que é o
depósito, enquanto os outros vértices, que vão de “C1” até “CN”, constituem os clientes que
receberão as mercadorias. O conjunto de arestas de G são as distâncias entre os clientes. Além
disso, existe uma frota com k veículos com capacidade de transporte conhecida.
Resolver o PRV é equivalente a encontrar o percurso hamiltoniano mínimo do grafo modelo.
Infelizmente, o problema é NP-completo, isto é, não se conhece um algoritmo que execute em tempo
polinomial capaz de resolver o problema. Entretanto, existem métodos heurísticos para a solução dele. O
algoritmo de Clarke e Wright (1964) é um exemplo de algoritmo heurístico para a solução do PRT.
Método heurístico
Um método heurístico é uma abordagem não exata que encontra um solução viável do problema, porém
sem a garantia de otimalidade.
Spanning tree em redes locais
As redes locais de computadores são compostas basicamente por três componentes:
Comutadores (ou switches) Cabos de comunicação
Terminais
A topologia típica de uma rede é uma árvore. Normalmente, um switch é o switch raiz. Todos os outros
switches se conectam direta ou indiretamente com o raiz.
Normalmente, uma rede local não tem loops, ou seja, não é um grafo. Porém, por questões de redundância,
certos protocolos permitem a conexão dos ativos em loop para fins de redundância.
Contudo, se as portas com conexão redundante se comunicassem como as outras, a rede replicaria pacotes
de forma indefinida, levando ao colapso da comunicação. Para resolver esse problema, os fa-bricantes de
switchs implementaram um protocolo de comunicação denominado STP (Spanning tree protocol ou protocolo
de árvore geradora) que calcula a árvore geradora do grafo e coloca em “stand-by” as portas que fecham
ciclos.
Vem que eu te explico!
Os vídeos a seguir abordam os assuntos mais relevantes do conteúdo que você acabou de estudar.
Como funcionam os sistemas de navegação GPS
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Spanning tree em redes locais
Conteúdo interativo
Acesse a versão digital para assistir ao vídeo.
Verificando o aprendizado
Questão 1
Problemas de roteamento, em geral, podem ser resolvidos modelando a malha na qual se deseja estabelecer a
rota em um grafo. Analise as afirmativas a seguir e determine se são verdadeiras.
 
1 - Toda e qualquer malha pode ser modelada em um grafo.
 
Por isso...
 
2 - Todos os problemas de roteamento podem ser resolvidos em tempo polinomial.
 
A
Ambas são verdadeiras, e II justifica I.
B
Ambas são verdadeiras, porém II não justifica I.
C
I é verdadeira, e II é falsa.
D
I é falsa, e II é verdadeira.
E
Ambas são falsas.
A alternativa C está correta.
Malhas ou redes são modeladas naturalmente em um grafo, porém o problema estar modelado em um grafo
não garante que haja um algoritmo que resolva o problema em tempo polinomial. O PRV é um exemplo
disso.
Questão 2
As redes locais de computadores têm a topologia de funcionamento em árvore, isto é, não é possível haver
redundâncias de enlace, uma vez que, caso as redundâncias existissem, haveria a replicação des-controlada
de pacotes na rede.
 
1 - O problema do enunciado só pode ser resolvido manualmente, ou seja, com a manobra de cabos do
operador...
 
Porque
 
2 - Não existe algoritmo que execute em tempo polinomial capaz de, dado um grafo, calcular a árvore
geradora do grafo.
 
A
As duas afirmativas são falsas.
B
I é falsa, e II é verdadeira.
C
I é verdadeira, e II é falsa .
D
I e II são verdadeiras, porém II não justifica I.
E
I e II são verdadeiras, e II justifica I.
A alternativa A está correta.
Os fabricantes de equipamentos de rede local implementam o protocolo STP, que calcula a árvore geradora
de um grafo e desabilita a conexão redundante na rede. Associado ao protocolo, o algoritmo roda
continuamente; caso ocorra uma falha em um enlace pertencente à árvore geradora do grafo, a
redundância é acionada automaticamente.
5. Conclusão
Considerações finais
Acabamos de estudar os principais algoritmos de percursos em grafos, analisando sua importância prática e
até mesmo histórica. Iniciamos pelos problemas de percursos originais, os chamados percur-sos eulerianos e
hamiltonianos.
Vimos também que o percurso euleriano pode ser resolvido com um algoritmo que executa em tempo
polinomial. Entretanto, não se conhece um que execute nesse tempo para calcular o percurso hamilto-niano
de determinado grafo.
Em seguida, abordamos o conceito e o algoritmo básico de percursos em grafos. Verificamos ainda que,
devido à sua definição, há várias formas de se percorrer um grafo. Por isso, introduzimos os percursos em
largura e profundidade, já que eles mitigam a variedade dos percursos que podem ser calculados com o
algoritmo geral de percursos.
Pontuamos também o conceito de árvore geradora de um grafo e o conceito de grafo ponderado. Nesse
ponto, concluímos que, casoo grafo seja ponderado, haverá diferenças do peso total das árvores geradoras.
Sendo assim, falamos sobre o conceito de árvore geradora mínima e descrevemos os algoritmos de Prim e
Kruskal, que são algoritmos gulosos que calculam as árvores geradoras mínimas de um grafo.
Por fim, apontamos algumas aplicações práticas dos conceitos estudados, destacando a importância da
matemática discreta no cotidiano e da teoria dos grafos.
Podcast
Ouça o podcast. Nele, falaremos sobre a importância da teoria dos grafos na vida das pessoas.
Conteúdo interativo
Acesse a versão digital para ouvir o áudio.
Explore +
O Waze é um aplicativo de navegação urbana por GPS muito popular. Além de calcular a rota entre sua origem
e seu destino, ele leva em consideração o atraso devido ao trânsito.
 
Acesse o site Wazeopedia para saber mais sobre o funcionamento do algoritmo de rotas do Waze e entender
o motivo do sucesso do aplicativo.
Referências
BOAVENTURA NETTO, P. O. Grafos: teoria, modelos, algoritmos. 5. ed. Rio de Janeiro: SBM, 2013.
 
CLARKE, G.; WRITGHT, J. W. Scheduling of vehicles from a central depot to a number of delivery points.
Operations research, v. 12, n. 4, jul.-ago., 1964. p. 568-581.
 
SHAPIRO, J.; WAXMAN, J. N. D. Level graphs and approximate shortest path algorithms. Networks, n. 22, 1992.
p. 691-717.
 
SZWARCFITER, J. Grafos e algoritmos computacionais. 2. ed. Rio de Janeiro: Campus, 1986.
	Técnica de buscas em grafos
	1. Itens iniciais
	Propósito
	Objetivos
	Introdução
	1. Busca em grafos planos
	Teoria dos grafos
	Conceitos básicos
	Exemplo
	Atenção
	Caminho
	Ciclo
	Grafos planos
	Atenção
	Saiba mais
	Percurso euleriano
	Alguns conceitos fundamentais
	Listas de adjacências
	Matriz de adjacências
	Atenção
	Formulação do problema
	Atenção
	Comentário
	Proposta de solução por Euler
	Algoritmo de determinação do percurso euleriano
	D
	F
	C
	B
	A
	C
	D
	E
	G
	F
	H
	E
	Calculando o percurso euleriano de um grafo
	Conteúdo interativo
	Percurso hamiltoniano
	Formulação do problema
	Exemplo
	Algoritmo para obtenção do ciclo hamiltoniano de um grafo
	Dica
	1
	2
	3
	Exemplo
	Vem que eu te explico!
	Percurso euleriano
	Conteúdo interativo
	Percurso hamiltoniano
	Conteúdo interativo
	Verificando o aprendizado
	2. Busca em grafos
	Percursos em grafos
	Base conceitual
	Exemplo
	Percurso em largura.
	Percurso em profundidade.
	Vértice marcado
	Aresta selecionada
	Algoritmo genérico de percurso
	1° passo
	2° passo
	3° passo
	Percurso em largura
	Definição
	Algoritmo de percurso em largura
	Dica
	Calculando o percurso largura de um grafo
	Conteúdo interativo
	Percurso em profundidade
	Definição
	Dica
	Algoritmo do percurso em profundidade
	Atenção
	Vem que eu te explico!
	Base conceitual – percursos em grafos
	Conteúdo interativo
	O percurso em profundidade
	Conteúdo interativo
	Verificando o aprendizado
	3. Propriedades elementares de árvores em grafos
	Árvores, subgrafos e árvores geradoras
	Definição
	Primeiro
	Segundo
	Terceiro
	Quarto
	Quinto
	Sexto
	Algoritmo de obtenção de uma árvore geradora do grafo
	1
	2
	3
	4
	5
	Apenas um dos vértices x ou y foi visitado.
	Os dois vértices x e y já foram visitados.
	Árvores geradoras mínimas
	Saiba mais
	1
	2
	3
	Algoritmo de Prim
	V’
	V’’
	Dica
	Calculando a árvore geradora mínima de um grafo pelo algoritmo de Prim
	Conteúdo interativo
	Algoritmo de Kruskal
	1
	2
	3
	V'
	V''
	Dica
	Vem que eu te explico!
	Árvores, subgrafos e árvores geradoras
	Conteúdo interativo
	Árvores geradoras mínimas
	Conteúdo interativo
	Verificando o aprendizado
	4. Aplicações de algoritmos de busca em grafos
	Teoria dos grafos e a vida prática
	A importância da matemática discreta no cotidiano
	A importância da modelagem matemática
	Os grafos na vida prática
	Exemplo
	Aplicações práticas
	Roteamento em vias públicas
	Primeiro nível
	Segundo nível
	Terceiro nível
	Como funcionam os sistemas de navegação GPS
	Conteúdo interativo
	Distribuição de mercadorias
	Spanning tree em redes locais
	Comutadores (ou switches)
	Cabos de comunicação
	Terminais
	Vem que eu te explico!
	Como funcionam os sistemas de navegação GPS
	Conteúdo interativo
	Spanning tree em redes locais
	Conteúdo interativo
	Verificando o aprendizado
	5. Conclusão
	Considerações finais
	Podcast
	Conteúdo interativo
	Explore +
	Referências