TEMA_4_-_ARA0175_-_T_CNICAS_DE_BUSCA_EM_GRAFOS

Prévia do material em texto

Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TEMA 4 – TÉCNICAS DE BUSCA EM GRAFOS
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TÉCNICA DE BUSCA:
VISITA EM GRAFOS
Grafos – Busca em Grafos
Prof. Simone 
Gama
Análise de Algoritmos 3
Técnica de Busca em Grafos
A técnica de Busca em Grafos (ou Percurso em Grafos) é uma forma de 
examinar de vértices e arestas de um grafo. 
É fortemente recomendado o domínio destas técnicas para a elaboração 
de bons projetos de algoritmos, não somente em grafos, como para 
outras técnicas de programação.
Grafos – Busca em Grafos
Prof. Simone 
Gama
Análise de Algoritmos 4
Técnica de Busca em Grafos
Duas técnicas são amplamente conhecidas para buscar informações da 
estrutura de um grafo:
1. Busca em Largura
2. Busca em Profundidade
4
1
2
3
5
6 7
8
9
Grafos – Busca em Grafos
Prof. Simone 
Gama
Análise de Algoritmos 5
Técnica de Busca em Grafos
Duas técnicas são amplamente conhecidas para buscar informações da 
estrutura de um grafo:
1. Busca em Largura
2. Busca em Profundidade
4
1
2
3
5
6 7
8
9
Grafos – Busca em Largura
Prof. Simone 
Gama
Análise de Algoritmos 6
Algoritmo de Busca em Largura ou busca de amplitude é um 
algoritmo de busca em grafos utilizado para realizar uma busca 
ou travessia em um grafo típico.
Algoritmo BFS (Breadth-First Search)
Prof. Simone 
Gama
Análise de Algoritmos 7
Algoritmo BFS (Breadth-First Search)
• O algoritmo inicia pelo vértice raiz e explora todos os vértices vizinhos à 
ele. 
• Então, para cada um desses vértices mais próximos, exploramos os seus 
vértices vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
4
1
2
3
5
6 7
8
9
Grafos – Busca em Largura
Prof. Simone 
Gama
Análise de Algoritmos 8
4
1
2
3
5
6 7
8
9
Algoritmo BFS (Breadth-First Search)
• O algoritmo inicia pelo vértice raiz e explora todos os vértices vizinhos à 
ele. 
• Então, para cada um desses vértices mais próximos, exploramos os seus 
vértices vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
Grafos – Busca em Largura
Prof. Simone 
Gama
Análise de Algoritmos 9
4
1
2
3
5
6 7
8
9
Algoritmo BFS (Breadth-First Search)
• O algoritmo inicia pelo vértice raiz e explora todos os vértices vizinhos à 
ele. 
• Então, para cada um desses vértices mais próximos, exploramos os seus 
vértices vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
Grafos – Busca em Largura
Prof. Simone 
Gama
Análise de Algoritmos 10
4
1
2
3
5
6 7
8
9
Algoritmo BFS (Breadth-First Search)
• O algoritmo inicia pelo vértice raiz e explora todos os vértices vizinhos à 
ele. 
• Então, para cada um desses vértices mais próximos, exploramos os seus 
vértices vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
Grafos – Busca em Largura
Prof. Simone 
Gama
Análise de Algoritmos 11
4
1
2
3
5
6 7
8
9
Algoritmo BFS (Breadth-First Search)
• O algoritmo inicia pelo vértice raiz e explora todos os vértices vizinhos à 
ele. 
• Então, para cada um desses vértices mais próximos, exploramos os seus 
vértices vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
Grafos – Busca em Largura
Prof. Simone 
Gama
12
4
1
2
3
5
6 7
8
9
Algoritmo BFS (Breadth-First Search)
• O algoritmo inicia pelo vértice raiz e explora todos os vértices vizinhos à 
ele. 
• Então, para cada um desses vértices mais próximos, exploramos os seus 
vértices vizinhos inexplorados e assim por diante, até explorar todo o 
grafo.
Grafos – Busca em Largura
Prof. Simone 
Gama
Análise de Algoritmos 13
Busca em Largura: Algoritmo
Passos do Algoritmo BFS
• A busca em largura começa por um vértice, chamaremos 
de 𝒔. O algoritmo visita 𝑠, depois visita todos os vizinhos de 𝑠, depois 
todos os vizinhos dos vizinhos, e assim por diante.
• O algoritmo numera os vértices, em sequência, na ordem em que eles 
são descobertos (ou seja, visitados pela primeira vez). Para fazer isso, 
o algoritmo usa uma fila (queue) de vértices. No começo de cada 
iteração, a fila contém vértices que já foram numerados mas têm 
vizinhos ainda não numerados.
Prof. Simone 
Gama
Análise de Algoritmos 14
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: end for 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
s
Busca em Largura: Algoritmo
Algoritmo 
BFS
Grafo G 
exemplo
Prof. Simone 
Gama
Análise de Algoritmos 15
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: end for 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
Q
s
a b c d e f g h
d
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 16
BFS(G,s) 
1: for each 𝒖 ∈ (𝑽 – {𝒔}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
a b c d e f g h
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
Q
d
s
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 17
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
b
a b c d e f g h
∞ 𝟎 ∞ ∞ ∞ ∞ ∞ ∞
Q
d
s
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 18
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
b
a b c d e f g h
∞ 𝟎 ∞ ∞ ∞ ∞ ∞ ∞
Q
d
s
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 19
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
a b c d e f g h
∞ 𝟎 ∞ ∞ ∞ ∞ ∞ ∞
Q
d
s
𝒖 b
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 20
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
a b c d e f g h
∞ 𝟎 ∞ ∞ ∞ ∞ ∞ ∞
Q
d
s
𝒖 b
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 21
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: whileQ≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
a b c d e f g h
∞ 𝟎 ∞ ∞ ∞ ∞ ∞ ∞
Q
d
s
𝒖 b
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 22
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
f a
a b c d e f g h
𝟏 𝟎 ∞ ∞ ∞ 𝟏 ∞ ∞
Q
d
s
𝒖 b
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 23
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
f aQ
d
s
𝒖 b
𝒖
a b c d e f g h
𝟏 𝟎 ∞ ∞ ∞ 𝟏 ∞ ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 24
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
f aQ
d
s
𝒖 b
𝒖
a b c d e f g h
𝟏 𝟎 ∞ ∞ ∞ 𝟏 ∞ ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 25
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
aQ
d
s
𝒖 f
𝒖
a b c d e f g h
𝟏 𝟎 ∞ ∞ ∞ 𝟏 ∞ ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 26
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
aQ
d
s
𝒖 f
𝒖
a b c d e f g h
𝟏 𝟎 ∞ ∞ ∞ 𝟏 ∞ ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 27
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
a c gQ
d
s
𝒖 f
𝒖
a b c d e f g h
𝟏 𝟎 𝟐 ∞ ∞ 𝟏 𝟐 ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 28
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
a c gQ
d
s
𝒖 f
𝒖
a b c d e f g h
𝟏 𝟎 𝟐 ∞ ∞ 𝟏 𝟐 ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 29
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
c gQ
d
s
𝒖 a
𝒖
a b c d e f g h
𝟏 𝟎 𝟐 ∞ ∞ 𝟏 𝟐 ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 30
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q); 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA; 
14: d[v]  d[u] + 1; 
15: ENQUEUE(Q,v); 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
c g eQ
d
s
𝒖 a
𝒖
a b c d e f g h
𝟏 𝟎 𝟐 ∞ 𝟐 𝟏 𝟐 ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 31
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
c g eQ
d
s
𝒖 a
𝒖
a b c d e f g h
𝟏 𝟎 𝟐 ∞ 𝟐 𝟏 𝟐 ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 32
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s); 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
g eQ
d
s
𝒖 c
𝒖
a b c d e f g h
𝟏 𝟎 𝟐 ∞ 𝟐 𝟏 𝟐 ∞
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 33
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO; 
ba
e f
c
g
d
h
g e d
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 ∞
Q
d
s
𝒖 c
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 34
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
g e d
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 ∞
Q
d
s
𝒖 c
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 35
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
e d
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 ∞
Q
d
s
𝒖 g
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 36
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 115: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
e d h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 g
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 37
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
e d h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 g
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 38
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
d h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 e
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 39
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
d h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 e
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 40
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 d
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 41
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 d
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 42
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 h
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 43
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑
Q
d
s
𝒖 h
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 44
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
a b c d e f g h
𝟏 𝟎 𝟐 𝟑 𝟐 𝟏 𝟐 𝟑d
s
𝒖
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 45
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
s
𝒖
Todos os vértices são 
visitados pelo menos 3 vezes!
Todas as arestas são visitadas 
no máximo 1 vez!
Busca em Largura: Algoritmo
Prof. Simone 
Gama
Análise de Algoritmos 46
BFS(G,s) 
1: for each 𝑢 ∈ (𝑉 – {𝑠}) do 
2: cor[u]  BRANCO 
3: d[u]∞ 
4: endfor 
5: cor[s]  CINZA
6: d[s]  0
7: Q  ∅ 
8: ENQUEUE(Q,s) 
9: while Q≠ ∅ do 
10: u  DEQUEUE(Q) 
11: for each v  Adj[u] do 
12: if cor[v] = BRANCO then 
13: cor[v]  CINZA 
14: d[v]  d[u] + 1 
15: ENQUEUE(Q,v) 
16: endif 
17: end for 
18: cor[u]  PRETO 
ba
e f
c
g
d
h
s
𝒖
Complexidade 
Computacional:
𝑂(𝑉 + 𝐸)
Busca em Largura: Algoritmo
Prof. Simone 
Gama
47
6
1
2
5
3
4 7
9
8
Algoritmo DFS (Depth-First Search)
A busca em profundidade (também 
conhecido em inglês por Depth-First Search 
- DFS) é um algoritmo usado para realizar 
uma busca ou travessia em um grafo.
Busca em Profundidade
Prof. Simone 
Gama
48
6
1
2
5
3
4 7
9
8
Algoritmo DFS (Depth-First Search)
A busca em profundidade (também 
conhecido em inglês por Depth-First Search 
- DFS) é um algoritmo usado para realizar 
uma busca ou travessia em um grafo.
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 49
• A busca em profundidade não resolve um problema específico, apenas 
explora o grafo.
• A busca com o DFS ajuda a compreender a estrutura de um grafo, 
revelando sua forma e reunindo informações (representadas pela 
numeração dos vértices) que ajudam a responder perguntas sobre o 
grafo. 
• O algoritmo de busca DFS visita todos os vértices e todos os arcos do 
grafo numa determinada ordem e atribui um número a cada vértice: 
o 𝒌-ésimo vértice descoberto recebe o número 𝑘.
Busca em Profundidade
Algoritmo DFS (Depth-First Search)
Prof. Simone 
Gama
Análise de Algoritmos 50
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA; 
2: t  t + 1; 
3: d[u]  t; 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
Busca em Profundidade
Algoritmo 
DFS
Grafo G 
exemplo
Prof. Simone 
Gama
Análise de Algoritmos 51
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA; 
2: t  t + 1; 
3: d[u]  t; 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO
10: t  t + 1 
11: f[u]  t
𝒕 0
Busca em Profundidade
Variável que irá 
marcar o tempo de 
visita dos vértices.
Prof. Simone 
Gama
Análise de Algoritmos 52
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA; 
2: t  t + 1; 
3: d[u]  t; 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1 
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7:DFS-VISIT(u)
8: endif 
9: endfor 
Busca em Profundidade
𝒕 0
Prof. Simone 
Gama
Análise de Algoritmos 53
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[u] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1d
f
𝒕 1
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 54
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1d
f
𝒕 1
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 55
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1d
f
𝒕 1
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 56
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2d
f
𝒕 2
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 57
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2d
f
𝒕 2
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 58
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 3d
f
𝒕 3
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 59
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 3d
f
𝒕 3
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 60
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3d
f
𝒕 4
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 61
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3d
f
𝒕 4
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 62
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3 5d
f
𝒕 5
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 63
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3 5
6
d
f
𝒕 6
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 64
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3 5
6
d
f
𝒕 6
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 65
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3 5
7 6
d
f
𝒕 7
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 66
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3 5
7 8 6
d
f
𝒕 8
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 67
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 3 5
9 7 8 6
d
f
𝒕 9
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 68
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif9: endfor 
a b c d e f
1 2 4 3 5
9 7 8 6
d
f
𝒕 9
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 69
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 10 3 5
9 7 8 6
d
f
𝒕 10
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 70
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 10 3 5
9 7 8 6
d
f
𝒕 10
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 71
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 10 3 5
9 7 11 8 6
d
f
𝒕 11
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 72
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 10 3 5
12 9 7 11 8 6
d
f
𝒕 12
Busca em Profundidade
Prof. Simone 
Gama
Análise de Algoritmos 73
ba
ed f
c
DFS-VISIT(u) 
1: cor[u]  CINZA 
2: t  t + 1 
3: d[u]  t 
4: for each v ∈ Adj[u] then 
5: if cor[v] = BRANCO then 
6: DFS-VISIT(v) 
7: endif 
8: endfor 
9: cor[u]  PRETO 
10: t  t + 1
11: f[u]  t 
DFS(G) 
1: for each u ∈ V do 
2: cor[u]  BRANCO 
3: endfor 
4: t  0 
5: for each u ∈ V do 
6: if cor[u] = BRANCO then 
7: DFS-VISIT(u)
8: endif 
9: endfor 
a b c d e f
1 2 4 10 3 5
12 9 7 11 8 6
d
f
2/91/12 4/7
10/11 3/8 5/6
Busca em Profundidade
Prof. Simone 
Gama
74
1. Faça a Busca em Largura (com as distâncias) e Busca em 
Profundidade (com tempos de visitas e tempos de términos) dos 
seguintes grafos abaixo:
Busca em Grafos: Exercícios
Grafo A Grafo B
Prof. Simone Gama
Universidade Estácio de Sá (UNESA)
ARA0175 – ALGORITMOS 
EM GRAFOS
TÉCNICA DE BUSCA:
ÁRVORES GERADORAS MÍNIMAS
Grafos Árvores e Florestas
Prof. Simone 
Gama
Análise de Algoritmos 76
Grafos 
Árvores
Grafos 
Ciclos
Floresta
Árvores Geradoras Mínimas
Seja 𝐺 um grafo conexo e suponha que para cada aresta (𝑢, 𝑣) associamos um 
peso 𝑤(𝑢, 𝑣). O problema segue que deseja-se encontrar uma Árvore Geradora 
de Custo Mínimo (ou MST de minimum spanning tree) de um grafo não-dirigido 
com custos nas arestas. 
Prof. Simone 
Gama
Análise de Algoritmos 77
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
Prof. Simone 
Gama
Análise de Algoritmos 78
a
b
i
c
h g f
e
d
4
8 7
2
1 2
4
9
Árvores Geradoras Mínimas
Seja 𝐺 um grafo conexo e suponha que para cada aresta (𝑢, 𝑣) associamos um 
peso 𝑤(𝑢, 𝑣). O problema segue que deseja-se encontrar uma Árvore Geradora 
de Custo Mínimo (ou MST de minimum spanning tree) de um grafo não-dirigido 
com custos nas arestas. 
Características do Problema
• Seja G um grafo não-dirigido com custos nas arestas. O custo de cada 
aresta pode ser positivo ou negativo. O custo de um subgrafo não-
dirigido 𝑇 de 𝐺 é a soma dos custos das arestas da árvore 𝑇.
• Uma árvore geradora T de G é mínima se nenhuma outra árvore 
geradora tem custo menor que o de T.
Prof. Simone 
Gama
Análise de Algoritmos 79
Árvores Geradoras Mínimas
Existem algoritmos eficientes para resolver o problema da MST:
• O algoritmo de Prim, que faz crescer uma árvore até que ela se 
torne geradora e,
• O algoritmo de Kruskal, que faz crescer uma floresta geradora 
até que ela se torne uma árvore. 
Prof. Simone 
Gama
Análise de Algoritmos 80
Árvores Geradoras Mínimas
Ambos os algoritmos (kruskal e Prim) têm caráter guloso (greedy):
❑Em cada iteração do algoritmo, “abocanham” a aresta que 
parece mais promissora naquele momento sem se preocupar 
com o efeito global dessa escolha. 
❑Esses algoritmos são os protótipos da estratégia gulosa que 
resolve vários outros problemas computacionais. 
Prof. Simone 
Gama
Análise de Algoritmos 81
Árvores Geradoras Mínimas
Aplicações
• Encontrar uma rede de computadores interconectando-os que use a 
menor quantidade de fibra ótica possível.
• Instalação de linhas telefônicas (ou elétricas) entre um conjunto de 
localidades utilizando a infra-estrutura das rodovias com o menor uso de 
material.
Prof. Simone 
Gama
Análise de Algoritmos 82
Árvores Geradoras Mínimas
• O Algoritmo de PRIM, foi publicado por Robert C. Prim em 1957 e 
por E. W. Dijkstra pouco depois. 
• Escolhe-se um vértice como raiz da busca, o algoritmo mantém 
uma árvore até que todas as arestas sejam percorridas pelo 
algoritmo.
• O algoritmo tem caráter guloso: em cada iteração, escolhe a 
aresta mais barata do corte sem se preocupar com o efeito global, 
a longo prazo, dessa escolha.
Prof. Simone 
Gama
Análise de Algoritmos 83
Árvores Geradoras Mínimas: Prim
Algoritmo de Prim: Extração do Mínimo
A Função EXTRACT-MIN mantém de 
forma eficiente o menor elemento em 
uma lista.
Prof. Simone 
Gama
Análise de Algoritmos 84
EXTRACT-MIN(𝑸)
1: 𝑚𝑖𝑛 = 𝑄.first
2: for each 𝑣 ∈ 𝑄(𝐺) do
2: if d[𝑣] < d[𝑚𝑖𝑛] then
3: 𝑚𝑖𝑛  𝑣
4: end if
5: end for
6: 𝑄 ← 𝑄 − {𝑚𝑖𝑛}
7: return 𝑚𝑖𝑛
Estrutura de Manutenção de Elementos
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[u]  ∞
3: pai[u]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 85
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 86
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 87
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
∞
∞∞
∞∞
∞
∞
∞
∞
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢] NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 88
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞∞
∞∞
∞
∞
∞
∞
a b c d e f g h i𝑄
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 89
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞∞
∞∞
∞
∞
∞
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 90
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞∞
∞∞
∞
∞
∞
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 91
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞∞
∞∞
∞
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 92
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞∞
∞∞
∞
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 93
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞∞
∞∞
∞
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 94
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞𝟖
∞∞
∞
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 95
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞𝟖
∞∞
∞
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 96
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
∞𝟖
∞∞
∞
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 97
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒∞
𝟐
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 98
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒∞
𝟐
𝟖
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 99
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟔
𝟐
𝟕
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 100
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟔
𝟐
𝟕
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 101
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟔
𝟐
𝟕
𝟒
∞
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 102
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟐
𝟐
𝟕
𝟒
𝟏𝟎
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 103
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟐
𝟐
𝟕
𝟒
𝟏𝟎
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 104
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟐
𝟐
𝟏
𝟒
𝟏𝟎
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 105
a
b
i
c
h g f
e
d
4
8 7
2
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟐
𝟐
𝟏
𝟒
𝟏𝟎
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 106
a
b
i
c
h g f
e
d
4
8 7
2
1 2
4
14
9
10
𝟎
𝟕𝟖
𝟒𝟐
𝟐
𝟏
𝟒
𝟏𝟎
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 107
a
b
i
c
h g f
e
d
4
8 7
2
1 2
4
9
𝟎
𝟕𝟖
𝟒𝟐
𝟐
𝟏
𝟒
𝟗
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 108
a
b
i
c
h g f
e
d
4
8 7
2
1 2
4
9
𝟎
𝟕𝟖
𝟒𝟐
𝟐
𝟏
𝟒
𝟗
a b c d e f g h i𝑄
u
u
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 109
a
b
i
c
h g f
e
d
4
8 7
2
1 2
4
9
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 110
Algoritmo de Prim: Implementação
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 111
Inicialização do Grafo:
𝑂( 𝑉 )
Algoritmo de Prim: Complexidade
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 112
Laço while:
𝑂( 𝑉 )
Algoritmo de Prim: Complexidade
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 113
Laço while:
𝑂( 𝑉 )
𝑂(log |𝑉|)
𝑶( 𝑽 𝐥𝐨𝐠 |𝑽|)
Algoritmo de Prim: Complexidade
1: for each 𝑢 ∈ 𝑉[𝐺] do
2: 𝑘𝑒𝑦[𝑢]  ∞
3: pai[𝑢]  NIL
4:end for
5: 𝑘𝑒𝑦[𝑟]  0
6: 𝑄  𝑉[𝐺] 
7: while 𝑄  ∅ do
8: 𝑢  EXTRACT-MIN(𝑸)
9: for each 𝑣  Adj[𝑢] do
10: if 𝑣 ∈ 𝑄 and 𝑤 𝑢, 𝑣 < 𝑘𝑒𝑦[𝑣] then
11: pai[𝑣]  𝑢
12: 𝑘𝑒𝑦[𝑣]  𝑤(𝑢, 𝑣)
9: end if
10: end for 
AGM-PRIM(𝐺, 𝑤, 𝑠)
Prof. Simone Gama Análise de Algoritmos 114
Laço while:
𝑂( 𝑉 )
𝑂(log |𝑉|)
𝑂( 𝐸 )
𝑶( 𝑬𝐥𝐨𝐠 |𝑽|)
Algoritmo de Prim: Complexidade
Algoritmo de Kruskal
• No Algoritmo de Kruskal, o subgrafo 𝐹 = (𝑉, 𝐴) é uma floresta. 
• Inicialmente a floresta 𝐴 é vazio, onde a floresta contém os vértices sem as 
arestas. Em cada iteração, o algoritmo escolhe uma aresta (𝑢, 𝑣) de menor 
peso que liga vértices de componentes (árvores) distintos 𝐶 de 𝐶’ de 𝐹 =
𝑉, 𝐴 :
1.escolha uma aresta externa que tenha custo mínimo;
2.seja 𝒂 a aresta escolhida;
3.acrescente 𝒂 a floresta 𝐹.
Prof. Simone 
Gama
Análise de Algoritmos 115
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 116
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 117
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo irá criar uma floresta somente 
com os vértices de 𝑮.
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 118
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo irá ordenar as arestas em 
ordem crescente de peso!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 119
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 120
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 121
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 122
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 123
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 124
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 125
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7 6
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 126
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 127
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
7
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 128
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 129
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
8 7
2
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 130
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
7
2
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 131
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢,𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
7
2
1 2
4
14
9
10
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 132
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
11
7
2
1 2
4
14
9
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 133
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
7
2
1 2
4
14
9
O Algoritmo inserir na floresta as arestas de menor 
peso, até que a árvore completa seja formada!
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 134
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
a
b
i
c
h g f
e
d
4
8
7
2
1 2
4
9
Algoritmo de Kruskal: Implementação
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 135
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
Algoritmo de Kruskal: Complexidade
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 136
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
Algoritmo de Kruskal: Complexidade
Considerando que o grafo tem 𝑉 vértices e 𝐴 arestas:
• Precisamos ordenas as arestas por ordem crescente, 𝑂(𝐴 log 𝐴).
• Adicionar as arestas mínimas (1 aresta inserida, dois vértices acessados). Logo, 
𝑂 (log 𝑉).
• Complexidade final: 𝑂(𝐴 log 𝑉).
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 137
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
Algoritmo de Kruskal: Complexidade
Considerando que o grafo tem 𝑉 vértices e 𝐴 arestas:
• Precisamos ordenas as arestas por ordem crescente, 𝑂(𝐴 log 𝐴).
• Adicionar as arestas mínimas (1 aresta inserida, dois vértices acessados). Logo, 
𝑂 (log 𝑉).
• Complexidade final: 𝑂(𝐴 log 𝑉).
AGM-KRUSKAL(𝐺, 𝑤)
Prof. Simone 
Gama
Análise de Algoritmos 138
1: 𝐴 ← ∅
2: Ordene as arestas em ordem não-decrescente de peso
3: para cada 𝑢, 𝑣 ∈ 𝐸 nessa ordem faça
4: se 𝑢 e 𝑣 estão em componentes distintos de (𝑉, 𝐴) então
5: 𝐴 ← 𝐴 ∪ {(𝑢, 𝑣)}
6: fimse
7:fimpara
Algoritmo de Kruskal: Complexidade
Considerando que o grafo tem 𝑉 vértices e 𝐴 arestas:
• Precisamos ordenas as arestas por ordem crescente, 𝑂(𝐴 log 𝐴).
• Adicionar as arestas mínimas (1 aresta inserida, dois vértices acessados). Logo, 
𝑂 (log 𝑉).
• Complexidade final: 𝑶(𝑨 𝒍𝒐𝒈 𝑽).
1. Aplique o algoritmo de Prim e Kruskal nos grafos abaixo e compare os 
resultados obtidos de cada um:
Prof. Simone 
Gama
Análise de Algoritmos 139
Arvores Geradoras Mínimas: Exercícios
Grafo A Grafo B
Dúvidas?
Prof. Simone 
Gama
Análise de Algoritmos 140
Bibliografia
• Algoritmos DFS e BFS: 
• Adaptado de Jayme Luiz. Estruturas de Dados e seus Algoritmos. Rio de Janeiro: LTC, 
1994.
• Adaptado das aulas Prof Dr. Eduardo Nakamura, Universidade Federal do Amazonas 
(ICOMP- UFAM) – AM.
• Adaptado das aulas Prof. Dr Fábio Protti, Universidade Federal Fluminense (IC-UFF) – 
Niterói, RJ.
• Adaptado das aulas Análise de Algoritmos: Prof Ms. Simone Gama, Universidade 
Federal do Amazonas (ICOMP- UFAM - FUCAPI) – AM.
• Análise Assintótica: 
• Cormen, Thomas H. (2009). Introduction to Algorithms,. Massachusetts Institute of
Technology: MIT Press. 333 páginas.
• Adaptado: Paulo Feofiloff. Departamento de Ciência da Computação e Instituto de 
Matemática e Estatística da USP.
Prof. Simone 
Gama
Análise de Algoritmos 141
	Slide 1: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 2: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 3: Grafos – Busca em Grafos
	Slide 4: Grafos – Busca em Grafos
	Slide 5: Grafos – Busca em Grafos
	Slide 6: Grafos – Busca em Largura
	Slide 7: Grafos – Busca em Largura
	Slide 8: Grafos – Busca em Largura
	Slide 9: Grafos – Busca em Largura
	Slide 10: Grafos – Busca em Largura
	Slide 11: Grafos – Busca em Largura
	Slide 12: Grafos – Busca em Largura
	Slide 13: Busca em Largura: Algoritmo
	Slide 14: Busca em Largura: Algoritmo
	Slide 15: Busca em Largura: Algoritmo
	Slide 16: Busca em Largura: Algoritmo
	Slide 17: Busca em Largura: Algoritmo
	Slide 18: Busca em Largura: Algoritmo
	Slide 19: Busca em Largura: Algoritmo
	Slide 20: Busca em Largura: Algoritmo
	Slide 21: Busca em Largura: Algoritmo
	Slide 22: Busca em Largura: Algoritmo
	Slide 23: Busca em Largura: Algoritmo
	Slide 24: Busca em Largura: Algoritmo
	Slide 25: Busca em Largura: Algoritmo
	Slide 26: Busca em Largura: Algoritmo
	Slide 27: Busca em Largura: Algoritmo
	Slide 28: Busca em Largura: Algoritmo
	Slide 29: Busca em Largura: Algoritmo
	Slide 30: Busca em Largura: Algoritmo
	Slide 31: Busca em Largura: Algoritmo
	Slide 32: Busca em Largura: Algoritmo
	Slide 33: Busca em Largura: Algoritmo
	Slide 34: Busca em Largura: Algoritmo
	Slide 35: Busca em Largura: Algoritmo
	Slide 36: Busca em Largura: Algoritmo
	Slide 37: Busca em Largura: Algoritmo
	Slide 38: Busca em Largura: Algoritmo
	Slide 39: Busca em Largura: Algoritmo
	Slide 40: Busca em Largura: Algoritmo
	Slide 41: Busca em Largura: Algoritmo
	Slide 42: Busca em Largura: Algoritmo
	Slide 43: Busca em Largura: Algoritmo
	Slide 44: Busca em Largura: Algoritmo
	Slide 45: Busca em Largura: Algoritmo
	Slide 46: Busca em Largura: Algoritmo
	Slide 47: Busca em Profundidade
	Slide 48: Busca em Profundidade
	Slide 49: Busca em Profundidade
	Slide 50: Busca em Profundidade
	Slide 51: Busca em Profundidade
	Slide 52: Busca em Profundidade
	Slide 53: Busca em Profundidade
	Slide 54: Busca em Profundidade
	Slide 55: Busca em Profundidade
	Slide 56: Busca em Profundidade
	Slide 57: Busca em Profundidade
	Slide 58: Busca em Profundidade
	Slide 59: Busca em Profundidade
	Slide 60: Busca em Profundidade
	Slide 61: Busca em Profundidade
	Slide 62: Busca em Profundidade
	Slide 63: Busca em Profundidade
	Slide 64: Busca em Profundidade
	Slide 65: Busca em Profundidade
	Slide 66: Busca em Profundidade
	Slide 67: Busca em Profundidade
	Slide 68: Busca em Profundidade
	Slide 69: Busca em Profundidade
	Slide 70: Busca em Profundidade
	Slide 71: Busca em Profundidade
	Slide 72: Busca em Profundidade
	Slide 73: Busca em Profundidade
	Slide 74: Busca em Grafos: Exercícios
	Slide 75: ARA0175 – ALGORITMOS EM GRAFOS
	Slide 76: Grafos Árvores e Florestas
	Slide 77: Árvores Geradoras Mínimas
	Slide 78: Árvores Geradoras Mínimas
	Slide 79: Árvores Geradoras Mínimas
	Slide 80: Árvores Geradoras Mínimas
	Slide 81: Árvores Geradoras Mínimas
	Slide 82: Árvores Geradoras Mínimas
	Slide 83: Árvores Geradoras Mínimas: Prim
	Slide 84: Algoritmo de Prim: Extração do Mínimo
	Slide 85: Algoritmo de Prim: Implementação
	Slide 86: Algoritmo de Prim: Implementação
	Slide 87: Algoritmo de Prim: Implementação
	Slide 88: Algoritmo de Prim: Implementação
	Slide 89: Algoritmo de Prim: Implementação
	Slide 90: Algoritmo de Prim:Implementação
	Slide 91: Algoritmo de Prim: Implementação
	Slide 92: Algoritmo de Prim: Implementação
	Slide 93: Algoritmo de Prim: Implementação
	Slide 94: Algoritmo de Prim: Implementação
	Slide 95: Algoritmo de Prim: Implementação
	Slide 96: Algoritmo de Prim: Implementação
	Slide 97: Algoritmo de Prim: Implementação
	Slide 98: Algoritmo de Prim: Implementação
	Slide 99: Algoritmo de Prim: Implementação
	Slide 100: Algoritmo de Prim: Implementação
	Slide 101: Algoritmo de Prim: Implementação
	Slide 102: Algoritmo de Prim: Implementação
	Slide 103: Algoritmo de Prim: Implementação
	Slide 104: Algoritmo de Prim: Implementação
	Slide 105: Algoritmo de Prim: Implementação
	Slide 106: Algoritmo de Prim: Implementação
	Slide 107: Algoritmo de Prim: Implementação
	Slide 108: Algoritmo de Prim: Implementação
	Slide 109: Algoritmo de Prim: Implementação
	Slide 110: Algoritmo de Prim: Implementação
	Slide 111: Algoritmo de Prim: Complexidade
	Slide 112: Algoritmo de Prim: Complexidade
	Slide 113: Algoritmo de Prim: Complexidade
	Slide 114: Algoritmo de Prim: Complexidade
	Slide 115: Algoritmo de Kruskal
	Slide 116: Algoritmo de Kruskal: Implementação
	Slide 117: Algoritmo de Kruskal: Implementação
	Slide 118: Algoritmo de Kruskal: Implementação
	Slide 119: Algoritmo de Kruskal: Implementação
	Slide 120: Algoritmo de Kruskal: Implementação
	Slide 121: Algoritmo de Kruskal: Implementação
	Slide 122: Algoritmo de Kruskal: Implementação
	Slide 123: Algoritmo de Kruskal: Implementação
	Slide 124: Algoritmo de Kruskal: Implementação
	Slide 125: Algoritmo de Kruskal: Implementação
	Slide 126: Algoritmo de Kruskal: Implementação
	Slide 127: Algoritmo de Kruskal: Implementação
	Slide 128: Algoritmo de Kruskal: Implementação
	Slide 129: Algoritmo de Kruskal: Implementação
	Slide 130: Algoritmo de Kruskal: Implementação
	Slide 131: Algoritmo de Kruskal: Implementação
	Slide 132: Algoritmo de Kruskal: Implementação
	Slide 133: Algoritmo de Kruskal: Implementação
	Slide 134: Algoritmo de Kruskal: Implementação
	Slide 135: Algoritmo de Kruskal: Complexidade
	Slide 136: Algoritmo de Kruskal: Complexidade
	Slide 137: Algoritmo de Kruskal: Complexidade
	Slide 138: Algoritmo de Kruskal: Complexidade
	Slide 139: Arvores Geradoras Mínimas: Exercícios
	Slide 140: Dúvidas?
	Slide 141: Bibliografia