Teoria dos Grafos(do basico ao avançado, completo) (Ciência da computação (coreu pucminas tarde)

Prévia do material em texto

CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM 
GRAFOS 
DEFINIÇÕES E 
REPRESENTAÇÃO 
 
Prof. Alexei Machado 
PUC MINAS 
O Material desta disciplina foi confeccionado 
em conjunto com os professores João Caram, 
Max Machado e Raquel Mini 
Agradecimentos 2 
3 
Problema das Pontes de Königsberg 
No século XVIII havia na cidade de Königsberg um conjunto de sete pontes que 
cruzavam o rio Pregel. Elas conectavam duas ilhas (A e D) entre si e as ilhas com as 
margens (B e C) 
 
 
 Por muito tempo os habitantes daquela cidade perguntavam-se se era possível 
cruzar as sete pontes numa caminhada contínua sem passar duas vezes por 
qualquer uma delas 
4 
O Problema das 3 Casas e 3 Serviços 
¨  Suponha que tenhamos três casas e três serviços, a exemplo de: 
 
 É possível conectar cada serviço a cada uma das três casas sem 
que haja cruzamento de tubulações? 
5 
Problemas de Transporte 
¨  Problema de Conectividade: dadas as direções das vias, é 
possível ir da cidade A até a cidade B, sem andar na contramão? 
¨  Problema de Fluxo Máximo: dada a capacidade de fluxo em cada 
via, qual é a quantidade de mercadoria que podemos mandar de 
uma cidade A a uma cidade B? 
¨  Problema de Menor Caminho: Dados os comprimentos de cada 
via, qual o percurso mais rápido para sair de uma cidade A e 
chegar a uma cidade B? 
Grafo 
¨  Um par G = (V, E), sendo V um conjunto finito e E um 
conjunto de subconjuntos de dois elementos de V 
(Scheinerman, 2011) 
¨  Chamamos os elementos de V de vértices 
¨  Chamamos os elementos de E de arestas (edges) 
6 
Grafo 
¨  Modelo que formaliza relações de interdependência 
entre os elementos de um conjunto (Goldbarg,2012) 
¨  Vértices são objetos simples que podem ter nomes e 
outros atributos 
¨  Arestas são conexões entre dois vértices 
7 
Grafo 
¨  V = { A, B, C, D } 
¨  E = { (A;B), (A;D), (B;C), (B;D), (C;D) } 
8 
Grafo 
¨  V = { A, B, C, D } 
¨  E = { (A;B), (A;D), (B;C), (B;D), (C;D) } 
9 
A
C D
B 
Grafo 
¨  V = { A, B, C, D } 
¨  E = { (A;B), (A;D), (B;C), (B;D), (C;D) } 
¨  Vértices: cidades 
¨  Arestas: rodovias entre as cidades 
10 
A
C D
B 
Grafo 
¨  V = { A, B, C, D } 
¨  E = { (A;B), (A;D), (B;C), (B;D), (C;D) } 
¨  Vértices: autores 
¨  Arestas: autores que publicaram 
livros ou artigos em conjunto 
11 
A
C D
B 
Ordem e tamanho 
¨  A ordem de um grafo G é a cardinalidade de V 
¨  O tamanho de um grafo G é a cardinalidade de E 
12 
Ordem e tamanho 
¨  A ordem de um grafo G é a cardinalidade de V 
¨  O tamanho de um grafo G é a cardinalidade de E 
13 
Grafo valorado / ponderado 
¨  Um grafo G é dito valorado se existem valores 
associados a seus vértices ou arestas 
¨  Tais valores são denominados pesos 
14 
Grafo valorado / ponderado 
¨  Ex: custo de se 
movimentar entre 
dois pontos 
15 
Grafo não direcionado / não orientado 
¨  Por padrão, duas arestas (va, vb) e (vb, va) são 
consideradas a mesma 
16 
Grafo direcionado / orientado / digrafo 
¨  Já em um grafo direcionado, o conjunto E de arestas 
é uma relação binária em V 
¨  (va, vb) ≠ (vb, va) e podem ter significados diferentes 
¨  O sentido da aresta importa e é indicado 
¨  Arestas, neste caso, podem ser chamadas de arcos 
17 
Grafo direcionado / orientado / dígrafo 
18 
Grafo direcionado / orientado / dígrafo 
¨  Se há correspondência em ambos os sentidos, duas 
arestas 
19 
Vértices sucessores e antecessores 
¨  Em grafos direcionados, podemos falar de 
sucessores e antecessores de um vértice 
¨  B é sucessor de A 
¨  A é antecessor de B 
20 
Incidência 
¨  Quando um vértice vi é o vértice final de 
alguma aresta ei, vi e ei são incidentes 
21 
Laço (Loop) 
¨  Aresta que liga um vértice a si mesmo (vi, vi) 
22 
Arestas paralelas 
¨  Duas ou mais arestas associadas ao mesmo par de 
vértices 
23 
Grafo simples 
¨  Não possui nem arestas paralelas nem laços 
24 
Vértices adjacentes (vizinhos) 
¨  Dois vértices são ditos adjacentes se existe uma 
aresta que os liga 
25 
Arestas adjacentes 
¨  Duas arestas não paralelas são adjacentes se 
elas são incidentes a um vértice comum 
26 
Arestas adjacentes 
¨  Cuidado!! 
27 
Paralelas, 
Não adjacentes! 
Grau de um vértice 
¨  O número de arestas incidentes a um vértice vi é 
chamado de grau, d(vi), do vértice i 
28 
Vértice 1: 
Vértice 2: 
Vértice 3: 
Vértice 4: 
Vértice 5: 
Graus e vértices 
¨  Vértices com grau 0 são chamados isolados 
29 
Graus e vértices 
¨  Grafos que possuem somente vértices isolados são 
chamados de grafos nulos 
30 
Graus e vértices 
¨  Um vértice de grau 1 é chamado de pendente 
31 
Teorema 
¨  A soma dos graus de todos os vértices de um 
grafo G é duas vezes o número de arestas de G 
32 
∑
i= 1
n
d (vi )= 2 e
Teorema 
¨  Demonstre! 
33 
∑
i= 1
n
d (vi )= 2 e
Teorema 
¨  Ao contar os graus dos vértices, contamos cada 
extremidade de aresta uma vez. Como cada aresta tem 
duas extremidades, cada aresta foi contada duas vezes. 
34 
∑
i= 1
n
d (vi )= 2 e
Teorema 
¨  O número de vértices de grau ímpar em um 
grafo é par 
¤ Prove o teorema! 
35 
Provando... 
36 
37 
Graus e vértices 
¨  Em um grafo orientado, o grau de saída de um vértice é o número 
de arestas que saem dele, e o grau de entrada de um vértice é o 
número de arestas que entram nele. O grau de um vértice em um 
grafo orientado é seu grau de entrada somado a seu grau de saída 
grau do vértice 2 é 4 
grau de entrada do vértice 5 é 2 
grau de saída do vértice 5 é 1 
Grafo regular 
¨  Um grafo no qual todos os vértices possuem o 
mesmo grau é chamado de grafo regular 
38 
Grafo completo 
¨  Um grafo G=(V,E) é dito completo se para 
cada par de vértices va e vb existe uma aresta 
entre va e vb 
¨  Em um grafo completo quaisquer dois vértices 
distintos são adjacentes 
¨  Um grafo completo com n vértices é dito Kn 
39 
40 
Grafos completos 
Fonte: 
https://pt.wikipedia.org/wiki/Grafo_completo 
Grafos completos 
¨  Qual é o grau dos 
vértices de um 
grafo Kn ? 
¨  Qual é o número 
de arestas de um 
grafo Kn ? 
41 
Grafo complementar 
¨  Seja G = (V,E) um grafo simples, seu grafo 
complementar, C(G) ou G, é um grafo formado da 
seguinte maneira: 
¤  Os vértices de C(G) são todos os vértices de G 
¤  As arestas de C(G) são exatamente as arestas que 
faltam em G para formarmos um grafo completo 
42 
Grafo complementar 
43 
Representação de Grafos 44 
Grafo 
¨  Como representar um grafo computacionalmente, de 
modo que possamos executar algoritmos e resolver 
problemas diversos ? 
45 
Representação de Grafos 
¨  Principais estruturas de dados: 
¤ Matriz de adjacências 
¤ Listas de adjacências 
46 
Matriz de adjacências 
¨  Dado n = |G|, criar uma matriz n x n. 
¨  A posição [u,v] da matriz conterá 0 se não há aresta 
entre vu e vv, ou um valor não nulo se houver 
47 
48 
Matriz de adjacências 
 1 2 3 4 5 6 
 1 0 1 0 0 1 1 
 2 1 0 0 1 1 0 
 3 0 0 0 1 0 0 
 4 0 1 1 0 1 1 
 5 1 1 0 1 0 0 
 6 1 0 0 1 0 0 
49 
Matriz de adjacências 
 1 2 3 4 5 6 
 1 0 4 0 0 1 1 
 2 4 0 0 1 1 0 
 3 0 0 0 3 0 0 
 4 0 1 3 0 8 1 
 5 1 1 0 8 0 0 
 6 1 0 0 1 0 0 
 
Se as arestas tivessem 
pesos, suas posições 
poderiam ter estes valores 
 
4 
3 
8 
1 
1 
1 
1 
1 
Listas de adjacências 
¨  Cada vértice é um elemento de uma lista 
¨  Cada vértice contém uma lista de arestas, indicando 
o outro par que a compõe 
50 
51 
Listas de adjacências 
2 4 
1 3 
2 4 4 
1 3 3 
1 1 
2 
3 
4 
52 
Listas de adjacências 
2 4 
1 3 
2 4 4 
1 3 3 
1 1 
2 
3 
4 
 
Se as arestas tivessem 
pesos, isto poderia ser 
armazenado nos elementos 
das listas 
 
Representação de digrafos 
¨  Matriz de incidência 
¤ Valor positivo: indica direção linha à coluna 
¤ Valor negativo: indica direção coluna àlinha 
53 
Representação de digrafos 
¨  Matriz de incidência 
54 
 1 2 3 4 5 6 
 1 0 1 0 0 -1 -1 
 2 -1 0 0 1 1 0 
 3 0 0 0 -1 0 0 
 4 0 -1 1 0 -1 1 
 5 1 -1 0 1 0 0 
 6 1 0 0 -1 0 0 
1 
4 
2 
5 
6 
3 
Representação de digrafos 
¨  Matriz de incidência 
¤ Valor positivo: indica direção linha à coluna 
¤ Valor negativo: indica direção coluna à linha 
¨  Listas de incidência 
55 
56 
Estruturas de Dados para Dígrafos 
Lista de Adjacências Matriz de Adjacências 
Considerações 
¨  Matrizes x listas 
¤ Espaço 
¤ Complexidade de busca 
¨  Estruturas de dados otimizadas para busca de 
vértices e/ou arestas 
57 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM 
GRAFOS 
 
DEFINIÇÕES – PARTE 2 
Prof. Alexei Machado 
PUC MINAS 
Grafo conexo 
¨  Grafo em que existe pelo menos um caminho 
entre todos os pares de vértices de G 
2 
Uma dúvida 
¨  Estamos vendo um ou dois grafos? 
3 
Grafo desconexo 
¨  Consiste de dois ou mais grafos conexos. Cada 
um dos subgrafos conexos é chamado de 
componente 
4 
Isomorfismo 
¨  Dois grafos G e H são ditos isomorfos se existir uma 
correspondência um-para-um entre seus vértices e 
entre suas arestas, de maneira que as relações de 
incidência são preservadas 
5 
Isomorfismo 
6 
Isomorfismo 
¨  Condições necessárias mas não suficientes para que 
G e H sejam isomorfos: 
¤ mesmo número de vértices 
¤ mesmo número de arestas 
¤ mesmo número de componentes 
¤ mesmo número de vértices com o mesmo grau 
7 
Isomorfismo 
¨  Infelizmente, não existe um algoritmo eficiente para 
determinar o isomorfismo entre dois grafos 
¤ Considerando as estruturas estudadas, o que você 
proporia fazer para verificar o isomorfismo? 
8 
Grafo bipartido / bipartite 
¨  Grafo não orientado em que o conjunto de vértices V 
pode ser particionado em 2 subconjuntos, V1 e V2, 
tais que não existem arestas entre dois vértices de um 
mesmo subconjunto. 
9 
Grafo bipartido / bipartite 
¨  Estes são grafos bipartidos? 
10 
Subgrafos 
¨  Um grafo g é dito ser um subgrafo de um grafo G se 
todos os vértices e todas as arestas de g estão em G 
11 
Subgrafos 
¨  Todo grafo é subgrafo de si próprio 
¨  O subgrafo de um subgrafo de G é subgrafo de G 
¨  Um vértice simples de G é um subgrafo de G 
¨  Uma aresta simples de G (com suas extremidades) é 
subgrafo de G 
12 
Subgrafos 
¨  Todo grafo é subgrafo de si 
próprio 
¨  O subgrafo de um subgrafo 
de G é subgrafo de G 
¨  Um vértice simples de G é um 
subgrafo de G 
¨  Uma aresta simples de G 
(com suas extremidades) é 
subgrafo de G 
13 
Subgrafos 
¨  Todo grafo é subgrafo de si 
próprio 
¨  O subgrafo de um subgrafo 
de G é subgrafo de G 
¨  Um vértice simples de G é um 
subgrafo de G 
¨  Uma aresta simples de G 
(com suas extremidades) é 
subgrafo de G 
14 
Exercício 
¨  Quais são todos os subgrafos de G abaixo? 
15 
1 
2 
a 
Subgrafos induzidos por arestas 
16 
Subgrafos induzidos por vértices 
17 
Subgrafos disjuntos de arestas 
¨  Dois (ou mais) subgrafos g1 e g2 de um grafo G são 
disjuntos de arestas se g1 e g2 não tiverem arestas 
em comum 
¤  g1 e g2 podem ter vértices em comum? 
18 
Subgrafos disjuntos de arestas 
19 
Subgrafos disjuntos de vértices 
¨  Dois (ou mais) subgrafos g1 e g2 de um grafo G são 
disjuntos de vértices se g1 e g2 não tiverem vértices 
em comum 
¤ g1 e g2 podem ter arestas em comum? 
20 
Subgrafos disjuntos de vértices 
21 
Operações com grafos 
¨  Sejam G1 = (V1,E1) e G2 = (V2,E2), tem-se: 
 
Gunião = G1 U G2 = (V1 U V2 , E1 U E2) 
 
Ginterseção = G1 ∩ G2 = (V1 ∩ V2 , E1 ∩ E2) 
22 
União 
¨  Mostre o grafo resultante da união 
23 
U = 
União 
¨  Mostre o grafo resultante da união 
24 
U = 
Interseção 
¨  Mostre o grafo resultante da interseção: 
25 
= ∩ 
Interseção 
¨  Mostre o grafo resultante da interseção: 
26 
= ∩ 
“Ring sum” 
¨  Gring sum = G1 G2 = (V1 V2, E1 E2) 
¨  A operação ring sum consiste na união dos grafos G1 
e G2, de modo que a interseção entre eles não seja 
incluída 
27 
Ring sum 
¨  Mostre o grafo resultante da “ring sum”: 
28 
= 
Ring sum 
¨  Mostre o grafo resultante da “ring sum”: 
29 
= 
Propriedades das operações 
¨  Propriedades: 
¨  G1 U G2 = G2 U G1 
¨  G1 ∩ G2 = G2 ∩ G1 
¨  G1 G2 = G2 G1 
¨  G U G = G ∩ G = G 
¨  G G = Ø 
30 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM GRAFOS 
 
CAMINHAMENTOS 
 BUSCA EM LARGURA 
 
Prof. Alexei Machado 
PUC MINAS 
Caminhamentos 
¨  Caminhar em um grafo é mover-se entre seus vértices, 
verificando propriedades enquanto se caminha 
2 
Caminhamentos 
¨  Algoritmos de busca em grafos procuram caminhos 
com objetivos específicos: 
Conectividade Busca de um vértice específico (estado) 
Caminho mínimo Existência de um caminho 
3 
Busca em grafos 
¨  A busca em grafos tenta encontrar uma sequência de 
caminhos/ações que leve até a um objetivo 
¨  Uma vez encontrado este objetivo, um programa 
pode executar tal sequência de ações para atingi-lo 
4 
Busca em grafos 
¨  Aplicações 
¤ Rotas em redes de computadores 
¤ Caixeiro viajante e variações 
¤ Jogos digitais 
¤ Navegação de robôs 
¤  ... 
5 
Busca em largura 
¨  Em inglês, Breadth First Search (BFS) 
¨  Consiste em, a partir de um vértice de origem, 
explorar primeiramente todos os seus vizinhos e, em 
seguida repetir o procedimento para cada vizinho 
¨  Base para diversos algoritmos importantes que 
iremos estudar 
6 
Busca em largura 
¨  Calcula a distância do vértice de origem até 
qualquer vértice que possa ser alcançado 
¨  Produz uma árvore que indica todos os vértices que 
podem ser alcançados 
¨  Usado para grafos e digrafos 
7 
Busca em largura 
¨  Produz uma árvore primeiro na extensão com raiz em s 
que contém todos os vértices acessíveis 
¨  Visita todos os vértices à distância k a partir de s, antes 
de visitar quaisquer vértices à distância k+1 
8 
Busca em largura 
¨  Propriedades de um vértice 
¤ Antecessor ou pai 
¤ Estado: branco, cinza, preto 
¤ Distância até o vértice de origem 
9 
Busca em largura 
¨  Estados dos vértices 
¤ Branco: ainda não explorado 
¤ Cinza: explorado, mas com vizinhos não-explorados 
¤ Preto: explorado e sem vizinhos não explorados 
10 
Busca em largura 
¨  Utiliza uma lista para definir as próximas visitas 
¨  Pode armazenar a árvore de busca e/ou a 
sequência percorrida até um objetivo 
11 
12 
Algoritmo BFS - inicialização 
Para	cada	vértice	u	diferente	da	origem	s	faça	
	u.cor	=	branco;	
	u.distância	=	max_value;	
	u.pai	=	null;	
Fim	para	
s.cor	=	cinza;	
s.distância	=	0;	
s.pai	=	null;	
Q	=	nova	Fila	vazia;	
	
13 
Algoritmo BFS – busca principal 
Q.enfileirar(s);	
Enquanto	(!Q.vazia)	
	u	=	Q.desenfileirar();	
	Para	cada	vértice	v	adjacente	a	u	
	 	se	v.cor	==	branco	
	 	 	v.cor	==	cinza;	
	 	 	v.distância	=	u.distância+1;	
	 	 	v.pai	=	u	
	 	 	Q.enfileirar(v)	
	Fim	para	
	u.cor	=	preto;	
Fim	enquanto	
	
14 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
- - - - - - - - 
Distâncias 
Fila Q 
a b c d e f g h 
- - - - - - - - 
Pais 
15 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
- 0 - - - - - - 
Distâncias 
b 
Fila Q 
a b c d e f g h 
- - - - - - - - 
Pais 
Vértice: 
16 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
- 0 - - - - - - 
Distâncias 
Fila Q 
a b c d e f g h 
- - - - - - - - 
Pais 
Vértice: b 
17 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - - - - - 
Distâncias 
a 
Fila Q 
a b c d e f g h 
b - - - - - - - 
Pais 
Vértice: b 
18 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - - 1 - - 
Distâncias 
a f 
Fila Q 
a b c d e f g h 
b - - - - b - - 
Pais 
Vértice: b 
19 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - - 1 - - 
Distâncias 
a f 
Fila Q 
a bc d e f g h 
b - - - - b - - 
Pais 
Vértice: b 
20 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - - 1 - - 
Distâncias 
f 
Fila Q 
a b c d e f g h 
b - - - - b - - 
Pais 
Vértice: a 
21 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - 2 1 - - 
Distâncias 
f e 
Fila Q 
a b c d e f g h 
b - - - a b - - 
Pais 
Vértice: a 
22 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - 2 1 - - 
Distâncias 
f e 
Fila Q 
a b c d e f g h 
b - - - a b - - 
Pais 
Vértice: a 
23 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - 2 1 - - 
Distâncias 
e 
Fila Q 
a b c d e f g h 
b - - - a b - - 
Pais 
Vértice: f 
24 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 - - 2 1 2 - 
Distâncias 
e g 
Fila Q 
a b c d e f g h 
b - - - a b f - 
Pais 
Vértice: f 
25 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 - 2 1 2 - 
Distâncias 
e g c 
Fila Q 
a b c d e f g h 
b - f - a b f - 
Pais 
Vértice: f 
26 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 - 2 1 2 - 
Distâncias 
e g c 
Fila Q 
a b c d e f g h 
b - f - a b f - 
Pais 
Vértice: f 
27 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 - 2 1 2 - 
Distâncias 
g c 
Fila Q 
a b c d e f g h 
b - f - a b f - 
Pais 
Vértice: e 
28 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 - 2 1 2 - 
Distâncias 
g c 
Fila Q 
a b c d e f g h 
b - f - a b f - 
Pais 
Vértice: e 
29 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 - 2 1 2 - 
Distâncias 
c 
Fila Q 
a b c d e f g h 
b - f - a b f - 
Pais 
Vértice: g 
30 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 - 
Distâncias 
c d 
Fila Q 
a b c d e f g h 
b - f g a b f - 
Pais 
Vértice: g 
31 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
c d h 
Fila Q 
a b c d e f g h 
b - f g a b f g 
Pais 
Vértice: g 
32 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
c d h 
Fila Q 
a b c d e f g h 
b - f g a b f g 
Pais 
Vértice: 
33 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
d h 
Fila Q 
a b c d e f g h 
b - f g a b f g 
Pais 
Vértice: c 
34 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
h 
Fila Q 
a b c d e f g h 
b - f g a b f g 
Pais 
Vértice: d 
35 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
Fila Q 
a b c d e f g h 
b - f g a b f g 
Pais 
Vértice: h 
36 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
Fila Q 
a b c d e f g h 
b - f g a b f g 
Pais 
Fila vazia: fim 
37 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
a b c d e f g h 
b - f g a b f g 
Pais 
Caminho até o vértice h: 
h 
38 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
a b c d e f g h 
b - f g a b f g 
Pais 
Caminho até o vértice h: 
g-h 
39 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
a b c d e f g h 
b - f g a b f g 
Pais 
Caminho até o vértice h: 
f-g-h 
40 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
a b c d e f g h 
b - f g a b f g 
Pais 
Caminho até o vértice h: 
b-f-g-h 
41 
Algoritmo BFS 
a 
h 
g 
e 
f 
d 
b 
c a b c d e f g h 
1 0 2 3 2 1 2 3 
Distâncias 
a b c d e f g h 
b - f g a b f g 
Pais 
Caminho até o vértice h: 
b-f-g-h 
42 
Árvore BFS 
a 
h 
g e 
f 
d 
b 
c 
Busca em profundidade 
¨  Em inglês, Depth First Search (DFS) 
¨  A partir de um vértice de origem, busca 
recursivamente um vértice adjacente, até que não 
existam mais vértices a visitar 
¨  Pode gerar várias árvores de profundidade (floresta 
de busca) 
43 
Busca em profundidade 
¨  Utiliza a estratégia de procurar “mais fundo” no grafo sempre 
que possível. As arestas são exploradas a partir do vértice v 
mais recentemente visitado que ainda tem arestas inexploradas 
saindo dele 
¨  Quando todas as arestas de v são exploradas, a busca 
“regressa” para explorar as arestas que deixam o vértice a 
partir do qual v foi visitado 
¨  Esse processo continua até que visitamos todos os vértices 
acessíveis a partir do vértice de origem inicial 
44 
Busca em profundidade 
¨  Mantidas as propriedades de estado 
¨  Nova propriedade: timestamps (tempo da busca) 
¤ Timestamp de descoberta 
¤ Timestamp de término 
45 
46 
Algoritmo DFS - inicialização 
Para	cada	vértice	u	faça	
	u.cor	=	branco;	
	u.pai	=	null;	
Fim	para	
timestamp	=	0	
Para	cada	vértice	u	faça	
	se	u.cor	==	branco	
	 	Visitar(u);	
	Fim	se	
Fim	Para	
	
47 
Algoritmo DFS – principal (visita) 
timestamp	=	timestamp	+	1;	
u.descoberta	=	timestamp;	
u.cor	=	cinza;	
Para	cada	vértice	v	vizinho	de	u	faça	
	se	v.cor	==	branco	
	 	v.pai	=	u;	
	 	Visitar(v);	
	Fim	se	
Fim	Para	
u.cor	=	preto;	
timestamp	=	timestamp+1;	
u.término	=	timestamp;	
	
48 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 - - - - - 
Descoberta 
Timestamp: 1 
a b c d e f 
- - - - - - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
49 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 - - - - - 
Descoberta 
Timestamp: 1 
a b c d e f 
- - - - - - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
50 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 - - - - - 
Descoberta 
Timestamp: 1 
a b c d e f 
- a - - - - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
51 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - - - - 
Descoberta 
Timestamp: 2 
a b c d e f 
- a - - - - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
52 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - - - - 
Descoberta 
Timestamp: 2 
a b c d e f 
- a - - - - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
53 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - - - - 
Descoberta 
Timestamp: 2 
a b c d e f 
- a - - b - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
54 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - - 3 - 
Descoberta 
Timestamp: 3 
a b c d e f 
- a - - b - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
55 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - - 3 - 
Descoberta 
Timestamp: 3 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
56 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 4 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- - - - - - 
Finalização 
57 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 5 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- - - 5 - - 
Finalização 
58 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 5 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- - - 5 - - 
Finalização 
59 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 6 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- - - 5 6 - 
Finalização 
60 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 6 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- - - 5 6 - 
Finalização 
61 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 7 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- 7 - 5 6 - 
Finalização 
62 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 7 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
- 7 - 5 6 - 
Finalização 
63 
Algoritmo DFS 
f d 
ae 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 8 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
8 7 - 5 6 - 
Finalização 
64 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 - 4 3 - 
Descoberta 
Timestamp: 8 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
8 7 - 5 6 - 
Finalização 
65 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 9 4 3 - 
Descoberta 
Timestamp: 9 
a b c d e f 
- a - e b - 
Pais 
a b c d e f 
8 7 - 5 6 - 
Finalização 
66 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 9 4 3 - 
Descoberta 
Timestamp: 9 
a b c d e f 
- a - e b c 
Pais 
a b c d e f 
8 7 - 5 6 - 
Finalização 
67 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 9 4 3 10 
Descoberta 
Timestamp: 10 
a b c d e f 
- a - e b c 
Pais 
a b c d e f 
8 7 - 5 6 - 
Finalização 
68 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 9 4 3 10 
Descoberta 
Timestamp: 11 
a b c d e f 
- a - e b c 
Pais 
a b c d e f 
8 7 - 5 6 11 
Finalização 
69 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 9 4 3 10 
Descoberta 
Timestamp: 11 
a b c d e f 
- a - e b c 
Pais 
a b c d e f 
8 7 - 5 6 11 
Finalização 
70 
Algoritmo DFS 
f d 
a 
e 
c b 
a b c d e f 
1 2 9 4 3 10 
Descoberta 
Timestamp: 12 
a b c d e f 
- a - e b c 
Pais 
a b c d e f 
8 7 12 5 6 11 
Finalização 
71 
Floresta DFS 
f 
d 
a 
e 
c 
b 
Busca em profundidade 
¨  Enquanto a Busca em largura usa uma fila como 
estrutura auxiliar, uma versão não-recursiva da Busca 
por profundidade utilizaria qual estrutura de dados? 
72 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM 
GRAFOS 
CAMINHOS E 
CIRCUITOS 
 
Prof. Alexei Machado 
PUC MINAS 
Sequência de arestas 
¨  Sequência alternada de vértices e arestas 
começando e terminando com um vértice. 
2 
3 
4 
2 
5 
1 
a 
b 
c 
d e f 
g 
h 
Sequência de arestas 
¨  Sequência alternada de vértices e arestas 
começando e terminando com um vértice. 
¤ v1 a v2 a v1 g v3 
3 
3 
4 
2 
5 
1 
a 
b 
c 
d e f 
g 
h 
Caminho 
¨  Sequência de arestas no qual nenhuma aresta 
aparece mais de uma vez 
¤ v1 a v2 b v3 c v3 d v4 e v2 f v5 
4 
3 
4 
2 
5 
1 
a 
b 
c 
d e f 
g 
h 
Caminho 
¨  Um caminho de comprimento k de um vértice u até um vértice u’ 
em um grafo G=(V,E) é uma sequência <V0,V1,V2,...,Vk> de 
vértices tais que u=V0, u’=Vk e (Vi-1,Vi)∈ E para i=1,2,...,k 
¨  O comprimento de um caminho é o número de arestas no 
caminho 
¨  Se existe um caminho de u até u’ dizemos que u’ é acessível a 
partir de u 
5 
Caminho aberto 
¨  Vértices inicial e final são diferentes 
¤ v1 a v2 b v3 c v3 
6 
3 
4 
2 
5 
1 
a 
b 
c 
d e f 
g 
h 
Caminho fechado 
¨  Começa e termina no mesmo vértice 
¤ v1 g v3 b v2 e v4 h v5 f v2 a v1 
7 
3 
4 
2 
5 
1 
a 
b 
c 
d e f 
g 
h 
Caminho simples 
¨  Caminho aberto no qual nenhum vértice aparece mais 
de 1 vez 
¤ v1 a v2 b v3 
8 
3 
4 
2 
5 
1 
a 
b 
c 
d e f 
g 
h 
Circuito 
¨  Caminho fechado no qual nenhum vértice (exceto o 
primeiro e o último) aparece mais de uma vez 
¤ v1 a v2 b v3 g v1 
9 
3 
4 
2 
5 
1 
a 
b 
c 
d e f 
g 
h 
Ciclos 
¨  Um caminho <V0,V1,V2,...,Vk> forma um ciclo se 
V0=Vk e o caminho contém pelo menos uma aresta 
¨  Ciclo simples é um ciclo no qual os vértices 
V1,V2,...,Vk são distintos 
¨  Um autoloop é um ciclo de comprimento 1 
¨  Um grafo sem ciclos é acíclico 
10 
Resumo 
Repete vert. interno Repete aresta V0=Vn Tam 
Sequência S/N S/N S/N >=1 
Caminho S/N N S/N >=1 
Caminho aberto S/N N N >=1 
Caminho fechado* S/N N S >=1 
Caminho simples N N N >=1 
Circuito** N N S >=1 
Ciclo* S/N N S >=1 
Ciclo simples** N N S >=1 
Autoloop NA N S 1 
11 
12 
Diagrama de Venn 
sequência de arestas 
caminho 
Aberto 
Fechado 
(ciclo) 
caminho 
simples 
Circuito 
(ciclo simples) 
 Auto- 
loop 
 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM 
GRAFOS 
 
GRAFOS EULERIANOS E 
UNICURSAIS 
 
Prof. Alexei Machado 
PUC MINAS 
Grafos Eulerianos 
¨  As pontes de Königsberg. 
¨  É possível sair de um 
ponto, passar por todas 
as pontes uma única vez e 
retornar ao ponto inicial? 
2 
Grafos Eulerianos 
¨  Vértices: regiões da 
cidade 
¨  Arestas: pontes 
3 
A 
B 
C D 
Grafos Eulerianos 
¨  Vértices: regiões da 
cidade 
¨  Arestas: pontes 
4 
A 
B 
C D 
B 
C 
A 
D 
Grafos Eulerianos 
¨  É possível sair de uma região, 
passar por todas as pontes uma 
única vez e retornar ao ponto 
inicial? 
¨  Problema: encontrar um caminho 
fechado que passe por todas as 
arestas uma única vez 
5 
B 
C 
A 
D 
Grafos Eulerianos 
¨  Problema do Explorador: um explorador deseja explorar 
todas as estradas entre um número de cidades. É possível 
encontrar um roteiro que passe por cada estrada apenas uma 
vez e volte a cidade inicial? 
¨  Vértices: cidades 
¨  Arestas: estradas 
6 
1
3
5
4
2
7
6
Grafos Eulerianos 
¨  Problema: encontrar um caminho fechado que 
passe por todas as arestas uma única vez 
7 
(a) (b) (c) (d) 
Grafos Eulerianos 
¨  Em grafos conexos, se é possível encontrar um 
caminho fechado que passe por todas as arestas uma 
única vez, dizemos que G é um grafo euleriano 
8 
Grafos Eulerianos 
¨  Em grafos conexos, se é possível encontrar um 
caminho fechado que passe por todas as arestas uma 
única vez, dizemos que G é um grafo euleriano 
¨  TEOREMA: Um grafo conexo é euleriano se, e 
somente se, todos os seus vértices tiverem grau par 
9 
Exercício 
¨  Encontre um caminho fechado que passe por todos os 
arcos. Se não for possível, induza um subgrafo para 
que ele se torne euleriano com o menor número de 
alterações possível 
10 
(a) (b) (c) (d) 
Algoritmo de Hierholzer (1873) 
¨  Partindo do princípio que um grafo G é euleriano 
¤ Escolher um vértice v aleatório de G 
¤ Atravessar uma aresta aleatória v,w 
¤ Repetir o processo a partir de w até formar um caminho 
fechado C 
¤ Remover as arestas pertencentes a C 
¤ Se não sobram arestas, encontramos o caminho euleriano 
11 
Algoritmo de Hierholzer (1873) 
¨  Caso contrário, escolher um vértice v’ pertencente a C 
e com grau > 0 e repetir o processo para achar um 
novo caminho fechado C’ 
¨  Unir C’ a C 
¨  Repetir os passos até não sobrarem arestas 
12 
13 
3 6 
2 1 
4 5 
CAMINHO: 
C: 
14 
3 6 
2 1 
4 5 
CAMINHO: 
C: 
15 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2 
16 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3 
17 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4 
18 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4-5 
19 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4-5 
20 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4-5 
 
C’: 2 
21 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4-5 
 
C’: 2-1 
22 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4-5 
 
C’: 2-1-4 
23 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4-5 
 
C’: 2-1-4-2 
24 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-3-4-5 
 
C’: 2-1-4-2 
25 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-4-2-3-4-5 
 
26 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-4-2-3-4-5 
 
C’:1 
27 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-4-2-3-4-5 
 
C’:1-6 
28 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-4-2-3-4-5 
 
C’:1-6-5 
29 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-4-2-3-4-5 
 
C’:1-6-5-1 
30 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-4-2-3-4-5 
 
C’:1-6-5-1 
31 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-6-5-1-4-2-3-4-5 
 
C’:1-6-5-1 
32 
3 6 
2 1 
4 5 
CAMINHO: 
C: 5-2-1-6-5-1-4-2-3-4-5 
 
33 
Mapa do Departamento de Matemática 
¨  A figura abaixo ilustra o mapa do Departamento de Matemática de 
uma importante Universidade. A entrada principal está na parte 
norte do Departamento. Determine se é possível que uma pessoa 
possa andar pelo Departamento passando através de cada porta 
exatamente uma vez e terminando onde começou. 
Grafos semieulerianos ou unicursais 
¨  Um grafo é dito semieuleriano se existe um caminho 
aberto que passe por todas as arestas 
34 
3 
1 
4 
2 
5Grafos unicursais 
¨  TEOREMA: um grafo é unicursal se e somente se 
existem exatamente dois vértices com grau ímpar 
35 
3 
1 
4 
2 
5 
Grafos unicursais 
¨  TEOREMA: um grafo é unicursal se e somente se 
existem exatamente dois vértices com grau ímpar 
36 
3 
1 
4 
2 
5 
6 
Grafos unicursais 
¨  TEOREMA: Em um grafo conexo G com exatamente 
2K vértices de grau ímpar, existem K subgrafos 
disjuntos de arestas, todos eles unicursais, de maneira 
que juntos eles contêm todas as arestas de G 
37 
Grafos unicursais 
38 
Grafos unicursais 
39 
Grafos, em resumo 
¨  Grafo euleriano: todos os vértices de grau par 
¨  Grafo unicursal: dois vértices de grau ímpar 
¨  Grafo qualquer: 2K vértices de grau ímpar 
(k-traçável) 
40 
Grafos unicursais 
¨  É possível fazer o desenho abaixo sem retirar o lápis 
do papel e sem retroceder? 
41 
Grafos unicursais 
¨  É possível fazer o desenho abaixo sem retirar o lápis 
do papel e sem retroceder? 
¨  É possível fazer a mesma coisa 
terminando no ponto de 
partida? 
42 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM 
GRAFOS 
 
GRAFOS HAMILTONIANOS 
 
Prof. Alexei Machado 
PUC MINAS 
Grafos hamiltonianos 
¨  Um Circuito de Hamilton em um grafo conexo é um 
circuito que passa por todos os vértices do grafo uma 
única vez, voltando ao vértice inicial 
¨  Um grafo que possui um Circuito Hamiltoniano é 
chamado de grafo hamiltoniano 
2 
Grafos hamiltonianos 
¨  O Circuito de Hamilton de um grafo com n vértices 
contém n arestas 
3 
Caminho de Hamilton 
¨  Um Caminho de Hamilton em um grafo conexo é um 
caminho simples que passa por todos os vértices do 
grafo exatamente uma única vez 
4 
Considerações – Grafos hamiltonianos 
¨  O grafo deve ser conexo 
¨  Se um grafo é hamiltoniano, então a inclusão de 
qualquer aresta não atrapalha essa condição 
¨  Logo, loops e arestas paralelas podem ser 
desconsideradas (para n ≥ 3) 
 
5 
Grafos hamiltonianos 
¨  Infelizmente, não é simples decidir se um grafo é 
hamiltoniano 
¨  Há alguns teoremas que proveem condições 
suficientes, mas não necessárias, para isto 
6 
Grafos hamiltonianos 
¨  TEOREMA: Seja G um grafo simples com n vértices (n 
≥ 3). Se para todo par de vértices não adjacentes v 
e w, a soma de seus graus for maior ou igual a n, 
então G é hamiltoniano 
7 
Grafos hamiltonianos 
¨  TEOREMA: Seja G um grafo simples com n vértices (n 
≥ 3). Se o grau de cada vértice for n/2 no mínimo, 
G é hamiltoniano 
8 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM GRAFOS 
 
CAMINHAMENTOS 
 ALGORITMO DE DIJKSTRA 
 
Prof. Alexei Machado 
PUC MINAS 
Edsger Wybe Dijkstra (1930 – 2002) 
¨  Algoritmos, grafos, linguagens de 
programação, compiladores, sistemas 
operacionais e distribuídos, 
programação concorrente... 
¨  A pronúncia aproximada em português 
para Edsger Dijkstra é étsrrar déikstra. 
 https://pt.wikipedia.org/wiki/Edsger_Dijkstra 
2 
Algoritmo de Dijkstra 
¨  Baseado na busca em largura 
¨  Encontra a menor distância entre dois vértices de um 
grafo ponderado 
¤  encontra o menor caminho entre um vértice vi e todos os 
demais vértices do grafo 
3 
Algoritmo de Dijkstra 
¨  Definir um vértice de origem vo 
¨  Utiliza um vetor de distâncias a partir de vo 
¨  Utiliza um vetor de caminhos a partir de vo 
¨  Utiliza um vetor de vértices não visitados do grafo 
4 
Algoritmo de Dijkstra 
¨  Inicializações do algoritmo 
¤ d[vo] = 0 
¤ Se existe a[vo, vi], d[vi] = peso(vo, vi) 
n  Inserir vo- vi no vetor de caminhos 
¤ Se não existe a[vo, vi], d[vi] = max_value 
 
5 
6 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
Distâncias 
A B C D E F G 
Caminhos 
7 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
8 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
9 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
10 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
11 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
12 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
São os 
vértices C e E 
13 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitadode x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
Começando 
por C 
14 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(A,B) + aresta(B,C) < d(A,C) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
15 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(A,B) + aresta(B,C) < d(A,C) 
 faça 
 (i) d(A, C) = d(A, B) + aresta(B,C) 
 (ii) c(C) = c(B) + C 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 - 3 - - - 
Distâncias 
A B C D E F G 
A AB AD 
Caminhos 
16 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(A,B) + aresta(B,C) < d(A,C) 
 faça 
 (i) d(A, C) = d(A, B) + aresta(B,C) 
 (ii) c(C) = c(B) + C 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 - - - 
Distâncias 
A B C D E F G 
A AB ABC AD 
Caminhos 
17 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(A,B) + aresta(B,C) < d(A,C) 
 faça 
 (i) d(A, C) = d(A, B) + aresta(B,C) 
 (ii) c(C) = c(B) + C 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 - - - 
Distâncias 
A B C D E F G 
A AB ABC AD 
Caminhos 
Agora, para E 
18 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(A,B) + aresta(B,E) < d(A,E) 
 faça 
 (i) d(A, E) = d(A, B) + aresta(B,E) 
 (ii) c(E) = c(B) + E 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 - - - 
Distâncias 
A B C D E F G 
A AB ABC AD 
Caminhos 
19 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(A,B) + aresta(B,E) < d(A,E) 
 faça 
 (i) d(A, E) = d(A, B) + aresta(B,E) 
 (ii) c(E) = c(B) + E 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 - - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE 
Caminhos 
20 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 - - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE 
Caminhos 
21 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 - - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE 
Caminhos 
22 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 - - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE 
Caminhos 
23 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 - - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE 
Caminhos 
24 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 8 - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE ABCF 
Caminhos 
25 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 8 - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE ABCF 
Caminhos 
26 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitadosvoltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 6 8 - 
Distâncias 
A B C D E F G 
A AB ABC AD ABE ABCF 
Caminhos 
27 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 5 8 - 
Distâncias 
A B C D E F G 
A AB ABC AD ADE ABCF 
Caminhos 
28 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 5 8 - 
Distâncias 
A B C D E F G 
A AB ABC AD ADE ABCF 
Caminhos 
29 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 5 8 - 
Distâncias 
A B C D E F G 
A AB ABC AD ADE ABCF 
Caminhos 
30 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 5 6 - 
Distâncias 
A B C D E F G 
A AB ABC AD ADE ADEF 
Caminhos 
31 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 5 6 - 
Distâncias 
A B C D E F G 
A AB ABC AD ADE ADEF 
Caminhos 
32 
Algoritmo de Dijkstra 
(1)  Inicializações 
(2)  Escolher um vértice não visitado x 
cuja distância mínima para V0 seja a 
menor conhecida. Se x for NULO, 
termine o algoritmo 
(3)  Marcar x como visitado 
(4)  Para cada vizinho i não visitado de x 
se d(V0,x) + aresta(x,i) < d(V0, i) 
 faça 
 (i) d(V0, i) = d(V0, x) + aresta(x,i) 
 (ii) c(i) = c(x) + i 
(5)  Se existirem vértices não visitados 
voltar para o passo (2) 
A 
B C 
F 
D E 
G 
2 
3 
1 
4 
2 
5 
1 
A B C D E F G 
0 2 3 3 5 6 - 
Distâncias 
A B C D E F G 
A AB ABC AD ADE ADEF 
Caminhos 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM GRAFOS 
 
CAMINHAMENTOS 
 ALGORITMO DE FLOYD-WARSHALL 
 
Prof. Alexei Machado 
PUC MINAS 
Algoritmo de Floyd-Warshall 
¨  Calcula o menor caminho entre todos os pares de 
vértices em um digrafo 
¨  Envolve publicações de Robert Floyd (em 1962), 
Bernard Roy (em 1959) e Stephen Warshall (em 
1962) 
2 
Algoritmo de Floyd-Warshall 
¨  Peter Ingerman (em 1962) deu a forma atual ao 
algoritmo 
¨  É um exemplo de programação dinâmica 
¤ Técnica que utiliza cálculos previamente realizados no 
cálculo da solução atual. 
3 
Algoritmo de Floyd-Warshall 
¨  Premissa: um caminho entre dois vértices, vi e vl, passa 
por um vértice vk. Logo, o caminho pode ser visto 
como c(vi,vk)+c(vk,vl) 
¨  Tenta minimizar as partes do caminho 
4 
Algoritmo de Floyd-Warshall 
¨  Para todo caminho (i, l), o algoritmo verifica se existe 
outro menor que passa por um vértice k, ou seja, se 
c(i, l) é menor que c(i, k) + c(k, l) para cada vértice k 
do grafo 
¨  Insere um ou mais vértices nos caminhos quando for 
uma vantagem fazer isso 
5 
Estruturas de dados 
¨  Matriz de entrada, inicializada com 
¤  Se i = l, matrizEntrada(i, l) = 0 
¤  Se i ≠ l e (i, l) ϵ E, matrizEntrada(i,l) = getPeso(i, l) 
¤  Senão, matrizEntrada(i, j) = ∞ 
6 
Estruturas de dados 
¨  Matriz de saída D|V|x|V| , na qual cada célula dil 
contém a distância mínima entre os vértices i e l 
7 
Algoritmo de Floyd-Warshall 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
8 
k: intermediário 
i: origem 
l: destino 
9 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
10 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo Matriz de entrada 
0 8 5 
3 0 ∞ 
∞ 2 0 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
11 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo Matriz de entrada 
0 8 5 
3 0 ∞ 
∞ 2 0 
k:0 i:0 l:0 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
12 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo v0 como intermediário 
0 8 5 
3 0 ∞ 
∞ 2 0 
k:0 i:0 l:0 
=		min([0][0]=0	,	[0][0]=0	+	[0][0]=0)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
13 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 ∞ 
∞ 2 0 
k:0 i:0 l:1 
=		min([0][1]=8	,	[0][0]=0	+	[0][1]=8)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
14 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 ∞ 
∞ 2 0 
k:0 i:0 l:2 
=		min([0][2]=5	,	[0][0]=0	+	[0][2]=5)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
15 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 ∞ 
∞ 2 0 
k:0 i:1 l:0 
=		min([1][0]=3	,	[1][0]=3	+	[0][0]=0)	
 
Algoritmo deFloyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
16 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 ∞ 
∞ 2 0 
k:0 i:1 l:1 
=		min([1][1]=0	,	[1][0]=3	+	[0][1]=8)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
17 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 8 
∞ 2 0 
k:0 i:1 l:2 
=		min([1][2]=∞	,	[1][0]=3	+	[0][2]=5)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
18 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 8 
∞ 2 0 
k:0 i:2 l:0 
=		min([2][0]=∞	,	[2][0]= ∞	+	[0][0]=0)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
19 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 8 
∞ 2 0 
k:0 i:2 l:1 
=		min([2][1]=2	,	[2][0]= ∞	+	[0][1]=8)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
20 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo 
0 8 5 
3 0 8 
∞ 2 0 
k:0 i:2 l:2 
=		min([2][2]=0	,	[2][0]= ∞	+	[0][2]=5)	
 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
v0 como intermediário 
21 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo v1 como intermediário 
0 8 5 
3 0 8 
5 2 0 
k:1 i:2 l:2 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
22 
void	floydWarshall(Peso	mat[][]){	
		for	(int	k	=	0;	k	<	n;	k++)	
				for	(int	i	=	0;	i	<	n;	i++)	
						for	(int	l	=	0;	l	<	n;	l++)	
		mat[i][l]	=	min(mat[i][l],	mat[i][k]	+	mat[k][l])	
}	
Exemplo v2 como intermediário 
0 7 5 
3 0 8 
5 2 0 
k:2 i:2 l:2 
Algoritmo de Floyd-Warshall 
0 1 2 
8 
3 
2 
5 
2 
k: intermediário 
i: origem 
l: destino 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM 
GRAFOS 
 
CAMINHOS EM GRAFOS: 
PROBLEMAS 
 
Prof. Alexei Machado 
PUC MINAS 
Problema do carteiro chinês 
¨  Um carteiro deseja entregar cartas ao longo de 
todas as ruas de uma cidade, e retornar ao ponto 
inicial. Como ele pode planejar as rotas de forma a 
minimizar o caminho andado? 
2 
Problema do carteiro chinês 
3 
Problema do carteiro chinês 
4 
¤ Se o grafo for euleriano, 
basta percorrer o ciclo de 
Euler 
¤ Caso contrário, algumas 
arestas serão percorridas 
mais de uma vez 
Problema do carteiro chinês 
¨  Identifique os m nós de grau ímpar de G(N,A) (m 
é sempre par) 
¨  Encontre os menores caminhos entre cada par 
formado pelos m nós e identifique os m/2 
caminhos mínimos que liguem os nós 
¨  Adicione estes m/2 caminhos mínimos como arcos 
ligando os nós dos pares. O novo grafo G(N,A) 
contém zero vértices de grau ímpar 
¨  Encontre um ciclo euleriano em G(N,A). Este ciclo 
é a solução ótima do problema no grafo original 
G(N,A) e o seu comprimento é igual ao 
comprimento total das arestas do grafo original 
mais o comprimento total dos m/2 caminhos 
mínimos 
5 
Problema do caixeiro viajante (PCV) 
¨  Dado um conjunto de cidades a serem visitadas por 
um vendedor, qual é o caminho mínimo que pode ser 
realizado sem repetir cidades e, preferencialmente, 
retornando ao ponto de partida? 
6 
Problema do caixeiro viajante 
¨  Representação em grafos 
¤ Cidades: vértices 
¤ Arestas: ligações entre as cidades 
¨  Arestas ponderadas! 
 
7 
Problema do caixeiro viajante 
8 
Problema do caixeiro viajante 
9 
 
Encontrar um circuito de 
Hamilton de peso 
mínimo 
 
Problema do caixeiro viajante 
¨  Generalizando o problema, temos várias aplicações 
¤ entrega de encomendas / correspondências 
¤  recolhimento de objetos 
¤ planejamento de viagens 
¤  leitura de contadores de consumo 
¤  ... 
10 
Problema do caixeiro viajante 
¨  Como encontrar o circuito de peso mínimo? 
¤ Tentativa e erro? 
¤ Adaptação da busca em profundidade? 
¤ Adaptação de Dijkstra? 
11 
Problema do caixeiro viajante 
¨  É fácil encontrar tal caminho? 
¤ Problema combinatório 
¤ Solução recursiva 
¨  Uso de heurísticas para a resolução do problema 
12 
Problema do caixeiro viajante 
¨  O algoritmo do vizinho mais próximo é rápido e fácil 
de implementar 
¨  A partir de um vértice, visite seu vizinho não 
explorado de menor custo 
13 
Problema do caixeiro viajante 
14 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
¨  Porém, nem sempre o resultado é satisfatório 
15 
u 
v s 
t 
20 
10 
20 
10 
10 
100 
Problema do caixeiro viajante 
¨  Heurística de inserção de vértices: iniciando-se com 
um ciclo, inserir o vértice mais perto/mais distante de 
qualquer dos vértices do ciclo 
¨  Encontrar o melhor lugar para inserir o novo vértice e 
manter/expandir o ciclo 
16 
Problema do caixeiro viajante 
17 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
18 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
19 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
¨  Resultado: 11+5-10 = +6 
20 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
21 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
¨  Resultado: 10+5-9 = +6 
22 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
23 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
¨  Resultado: 11+10-7 = +14 
24 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
¨  Novo ciclo intermediário 
25 
w 
z u 
s 
v 
10 9 
5 6 
7 
11 
6 
9 
10 7 
Problema do caixeiro viajante 
¨  E se... O grafo não for completo? 
26 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM 
GRAFOS 
 
DIGRAFOS 
GRAFOS DIRIGIDOS ACÍCLICOS 
 
Prof. Alexei Machado 
PUC MINAS 
Digrafos1 
¨  Digrafo ou grafo direcionado: é um grafo no qual as 
arestas são pares ordenados de vértices 
¨  As arestas em um digrafo são 
comumente chamadas de arcos 
2 
1 - “A palavra digrafo é uma adaptação do termo digraph em inglês, que resultou da contração de directed e graph. Já dígrafo (com acento) é outra coisa 
muito diferente!” – Feofiloff, Paulo (2016) em http://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/digraphs.html 
Digrafos 
¨  Vértice inicial e vértice final de um arco 
¨  Dois arcos são antiparalelos ou simétricos se o vértice 
inicial de um é o vértice final de outro e vice versa 
3 
Digrafos 
¨  Grau de entrada de um vértice: d-(v) 
¨  Grau de saída de um vértice: d+(v) 
4 
Digrafos e grafos correspondentes 
5 
Grafo 
Correspondente 
Isomorfismo de digrafos 
¨  Isomorfismo de digrafos: a direção das arestas deve 
ser a mesma 
6 
Isomorfismo de digrafos 
¨  Isomorfismo de digrafos: a direção das arestas deve 
ser a mesma 
¨  G1 e G2 nãosão isomorfos 
7 
Digrafos simétricos 
¨  Um digrafo é simétrico se para toda aresta (va,vb) 
existe uma aresta (vb,va) 
8 
Digrafos simétricos 
¨  Um digrafo é simétrico se para toda aresta (va,vb) 
existe uma aresta (vb,va) 
¨  == grafo! 
9 
Digrafos completos 
10 
Simétrico 
(grafo) 
Assimétrico 
(torneio) 
Digrafo balanceado 
¨  Se, para todo vértice v de um digrafo, temos 
 
 
o digrafo é dito balanceado. 
11 
Caminhos e circuitos em digrafos 
¨  Caminho dirigido: segue a orientação das arestas 
¤ Semi-caminho: é um caminho no grafo correspondente 
mas não é no dígrafo 
¨  Caminho simples dirigido e Semi-caminho simples 
¨  Circuito dirigido e Semi-circuito 
 
12 
Conectividade 
¨  Digrafo fortemente conexo: existe um caminho 
dirigido entre quaisquer pares de vértices 
¨  Digrafo fracamente conexo: digrafo não é 
fortemente conexo, mas seu grafo correspondente é 
conexo 
¨  Se falarmos que um digrafo é conexo, simplesmente 
significa que seu grafo correspondente é conexo 
13 
Eulerianos 
¨  Digrafos Eulerianos: possuem um caminho fechado 
dirigido que passa por todas as arestas exatamente 
uma vez 
¨  TEOREMA: Um dígrafo é euleriano se, e somente se, 
ele for fortemente conexo e balanceado 
14 
Eulerianos 
15 
Digrafos e representação 
¨  Matriz de adjacência 
 v1 v2 v3 v4 v5 
v1 0 1 1 1 0 
v2 0 1 0 0 0 
v3 0 0 0 1 1 
v4 1 0 0 0 0 
v5 0 0 1 1 0 
16 
1 
2 
5 4 
3 
Digrafos e representação 
¨  Listas de adjacência 
v1 v2 v3 v4 
v2 v2 
v3 v4 v5 
v4 v1 
v5 v3 v4 
17 
1 
2 
5 4 
3 
Grafos dirigidos acíclicos 18 
Grafos dirigidos acíclicos 
¨  São digrafos que não possuem ciclos, isto é, para 
qualquer vértice v não existe um circuito iniciando-se 
e terminando em v 
¨  Conhecidos como DAG 
(directed acyclic graph) 
19 
Busca em profundidade e ciclos 
¨  Como usar a busca em profundidade para descobrir 
se um digrafo é um DAG? 
20 
a
c
db
Busca em profundidade e ciclos 
¨  Classificação de arestas 
¤ Arestas de árvore 
¤ Arestas de cruzamento ou avanço 
¤ Arestas de retorno 
21 
a
c
db
Classificação de arestas 
¨  Arestas de árvore: as que levam a vértices ainda não 
visitados 
22 
a
c
db
Classificação de arestas 
¨  Arestas de árvore: as que levam a vértices ainda não 
visitados 
¤  Iniciando a busca em A 
23 
a
c
db
Classificação de arestas 
¨  Arestas de árvore: as que levam a vértices ainda não 
visitados 
¤  Iniciando a busca em A 
n Chegada em um vértice branco: 
aresta de árvore 
24 
a
c
db
Classificação de arestas 
¨  Arestas de árvore: as que levam a vértices ainda não 
visitados 
¤  Iniciando a busca em A 
n Chegada em um vértice branco: 
aresta de árvore 
25 
a
c
db
Classificação de arestas 
¨  Arestas de retorno: as que conectam um vértice u a 
um predecessor seu, v 
¤  Iniciando a busca em A 
26 
a
c
db
Classificação de arestas 
¨  Arestas de retorno: as que conectam um vértice u a 
um predecessor seu, v 
¤  Iniciando a busca em A 
n Chegando em um vértice cinza: 
aresta de retorno 
27 
a
c
db
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A 
28 
a
c
db
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A 
29 
a
c
db
árvore 
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A 
30 
a
c
db
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A: 
chegando a um vértice preto: 
n Avanço, se u vem antes de v 
n Cruzamento, caso contrário 
31 
a
c
db
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A: 
chegando a um vértice preto: 
n Avanço, se u vem antes de v 
n Cruzamento, caso contrário 
32 
a
c
db
cruzamento 
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A: 
chegando a um vértice preto: 
n Avanço, se u vem antes de v 
n Cruzamento, caso contrário 
33 
a
c
db
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A: 
chegando a um vértice preto: 
n Avanço, se u vem antes de v 
n Cruzamento, caso contrário 
34 
a
c
db
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A: 
chegando a um vértice preto: 
n Avanço, se u vem antes de v 
n Cruzamento, caso contrário 
35 
a
c
db
Classificação de arestas 
¨  Arestas de cruzamento ou avanço: indicam o avanço 
em uma árvore existente ou o 
cruzamento de uma árvore a outra 
¤  Iniciando a busca em A: 
chegando a um vértice preto: 
n Avanço, se u vem antes de v 
n Cruzamento, caso contrário 
36 
a
c
db
avanço 
DAG e arestas de retorno 
¨  Um digrafo é DAG se e somente se na busca em 
profundidade não for encontrada nenhuma aresta de 
retorno. 
37 
CIÊNCIA DA COMPUTAÇÃO 
ALGORITMOS EM GRAFOS 
 
ORDENAÇÃO TOPOLÓGICA 
 
 
Prof. Alexei Machado 
PUC MINAS 
Ordenação topológica 
¨  Dado um DAG, é possível dispor seus vértices de 
modo que cada vértice apareça antes de todos os 
seus sucessores? 
2 
Ordenação topológica 
¨  Ordenação topológica: ordenação linear de vértices 
na qual cada vértice precede o conjunto que forma 
seu fecho transitivo direto. 
3 
Ordenação topológica 
4 
Teorema 
¨  Seja um digrafo G, 
¤ Ou ele possui ciclos. 
¤ Ou ele apresenta uma ou mais ordenações topológicas. 
5 
Ordenação topológica - algoritmos 
¨  Existem algoritmos com complexidade linear para 
determinar uma ordenação topológica de um DAG. 
¤ Algoritmo de Kahn 
¤ DFS modificado 
6 
Algoritmo de Kahn (1962) 
¨  Baseado em duas listas: 
¤ S: conjunto de vértices sem arcos de entrada 
¤ L: lista de vértices ordenados topologicamente 
¨  Retorna uma lista de ordenação topológica OU 
detecta a existência de um ciclo 
7 
8 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
9 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
4 23 16 
S
L
10 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
4 23 16 
S
L
11 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuirmais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
23 16 
4 
S
L
12 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
23 16 
4 
S
L
13 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
23 16 
4 
S
L
14 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
23 16 
4 
S
L
15 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
23 16 
4 
S
L
16 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
23 16 
4 
S
L
17 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
16 
4 23 
S
L
18 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
16 
4 23 
S
L
19 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
16 
4 23 
S
L
20 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
16 11 
4 23 
S
L
21 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
11 
4 23 16 
S
L
22 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
11 
4 23 16 
S
L
23 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
11 
4 23 16 
S
L
24 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
11 8 
4 23 16 
S
L
25 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
11 8 
4 23 16 
S
L
26 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
11 8 
4 23 16 
S
L
27 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
8 
4 23 16 11 
S
L
28 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
8 15 
4 23 16 11 
S
L
29 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o	vértice	v	em	L	
para	cada	arco	v,w	existente	faça	
remover	o	arco	v,w	de	E	
se	w	não	possuir	mais	arcos	de	entrada	
inserir	w	em	S	
Fim	para	
Fim	enquanto	
Se	E	=	∅	retorna	L		//lista	ordenada	
Senão	o	grafo	possui	pelo	menos	um	ciclo	
4 23 16 
8 11 
42 
9 
15 
8 15 
4 23 16 11 
S
L
30 
Algoritmo de Kahn 
L	=	∅;	
S	=	todos	os	vértices	sem	arcos	de	entrada;	
Enquanto	S	≠	∅	faça	
remover	um	vértice	v	de	S	
inserir	o