Projeto e Análise de Algoritmos  
Aula 12 Ordenação Topológica  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
Problema  
Um conjunto de N tarefas precisam ser executadas.  
Tarefas são dependentes:  
Exemplo: tarefa B só pode ser executada depois de A;  
Podemos modelar o problema como um grafo direcionado.  
Problema: Qual ordem de execução não viola as  
dependências?  
Problema Exemplo  
Exemplo:  
B depende de A  
A depende de C  
C depende de D  
B depende de E  
B depende de D  
C depende de E  
Ordenação Topológica  
Ordenação linear dos vértices de um DAG (Grafo Acíclico  
Dirigido) tal que, se existe uma aresta (u, v) no grafo, então u  
aparece antes de v.  
Impossível se o grafo for cíclico;  
Não é necessariamente única.  
Ordenação Topológica  
O grafo abaixo tem diversas ordenações topológicas possiveis:  
7, 5, 3, 11, 8, 2, 9, 10  
3, 5, 7, 8, 11, 2, 9, 10  
3, 7, 8, 5, 11, 10, 2, 9  
5, 7, 3, 8, 11, 10, 9, 2  
7, 5, 11, 3, 10, 8, 9, 2  
7, 5, 11, 2, 3, 8, 9, 10  
Algoritmos:  
Eliminação de vértices (algoritmo de Kahn);  
Utilizando uma busca em profundidade;  
Algoritmo de Kahn  
OrdenacaoTopologicaKahn(G)  
L ∅  
for each uv A[G]  
I[v] I[v] + 1  
S ← vertices com grau de entrada zero (S = pilha)  
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
return L  
Algoritmo de Kahn  
L
I
S
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
/
/
L ∅  
for each uv A[G]  
I[v] I[v] + 1  
S ← vertices com grau de entrada zero  
Algoritmo de Kahn  
L
I
S
0
1
2
3
4
5
6
7
0
1
2
1
0
3
3
1
/
/
L ∅  
for each uv A[G]  
I[v] I[v] + 1  
S ← vertices com grau de entrada zero  
Algoritmo de Kahn  
I
S
0
4
L
0
1
2
3
4
5
6
7
0
1
2
1
0
3
3
1
/
L ∅  
for each uv A[G]  
I[v] I[v] + 1  
S ← vertices com grau de entrada zero  
Algoritmo de Kahn  
L
I
S
0
1
2
3
4
5
6
7
0
1
2
1
0
3
3
1
0
4
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
L
I
S
0
1
2
3
4
5
6
7
0
1
2
1
0
3
3
1
0
4
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
L
I
S
0
1
2
3
4
5
6
7
0
1
2
1
0
3
2
0
0
4
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
0
7
L
0
1
2
3
4
5
6
7
0
1
2
1
0
3
2
0
4
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
L
4
7
I
S
0
1
2
3
4
5
6
7
0
1
2
1
0
3
2
0
0
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
L
4
7
0
I
S
0
1
2
3
4
5
6
7
0
1
2
1
0
3
2
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
L
4
7
0
I
S
0
1
2
3
4
5
6
7
0
1
2
1
0
3
2
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
L
4
7
0
I
S
0
1
2
3
4
5
6
7
0
0
1
0
0
3
2
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
L
4
7
0
I
S
1
3
0
1
2
3
4
5
6
7
0
0
1
0
0
3
2
0
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
0
1
2
3
4
5
6
7
0
0
1
0
0
3
2
0
1
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
0
1
2
3
4
5
6
7
0
0
1
0
0
3
2
0
1
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
0
1
2
3
4
5
6
7
0
0
1
0
0
2
2
0
1
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
0
1
2
3
4
5
6
7
0
0
1
0
0
2
2
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
0
1
2
3
4
5
6
7
0
0
1
0
0
2
2
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
0
1
2
3
4
5
6
7
0
0
0
0
0
1
1
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
0
1
2
3
4
5
6
7
0
0
0
0
0
1
1
0
2
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
2
0
1
2
3
4
5
6
7
0
0
0
0
0
1
1
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
2
0
1
2
3
4
5
6
7
0
0
0
0
0
1
1
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
2
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
5
6
L
4
7
0
3
1
2
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
2
6
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
5
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
2
6
5
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
/
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
stack(u, S)  
Algoritmo de Kahn  
I
S
L
4
7
0
3
1
2
6
5
0
1
2
3
4
5
6
7
0
0
0
0
0
0
0
0
/
Algoritmo de Kahn Análise  
Inicializar o vetor I: O(A)  
OrdenacaoTopologicaKahn(G)  
L ∅  
Inicializar a pilha S com os  
vértices de entrada zero:  
O(A)  
for each uv A[G]  
I[v] I[v] + 1  
S ← vertices com grau de  
entrada zero (S = pilha)  
while S ∅  
v ← unstack(S)  
stack(v, L)  
for each u Adj[v]  
I[u] ← I[u] - 1  
if I[u] = 0  
Desempilhar e Empilhar  
vértices: O(V) vertices, cada  
um com tempo O(1)  
Reduzir Ipara todos os  
vértices adjacentes: O(V)  
stack(u, S)  
return L  
Complexidade: O(V + A)  
Algoritmo com Busca em  
Profundidade  
OrdenacaoTopologicaDFS(G)  
L ← ∅  
BuscaEmProfundidade(G)  
return L  
visita(u)  
BuscaEmProfundidade(G)  
for each u V[G]  
c[u] ← white  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
[u] ← NULL  
time 0  
for each u V[G]  
if c[u] = white  
visita(u)  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
/
L
OrdenacaoTopologicaDFS(G)  
L ← ∅  
BuscaEmProfundidade(G)  
return L  
Ordenação Topológica DFS  
/
L
0
1 2 3 4 5 6 7  
c w w w w w w w w  
d
f
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
/
L
0
1 2 3 4 5 6 7  
c g w w w w w w w  
d 1  
f
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
/
L
0
1 2 3 4 5 6 7  
c g g w w w w w w  
d 1 2  
f
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
/
L
0
1 2 3 4 5 6 7  
c g g w g w w w w  
d 1 2  
f
3
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
/
L
0
1 2 3 4 5 6 7  
c g g w g w g w w  
d 1 2  
f
3
4
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
/
L
0
1 2 3 4 5 6 7  
c g g w g w b w w  
d 1 2  
f
3
4
5
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
5
L
0
1 2 3 4 5 6 7  
c g g w g w b w w  
d 1 2  
f
3
4
5
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
5
L
0
1 2 3 4 5 6 7  
c g g w b w b w w  
d 1 2  
f
3
6
4
5
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
3
5
L
0
1 2 3 4 5 6 7  
c g g w b w b w w  
d 1 2  
f
3
6
4
5
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
3
5
L
0
1 2 3 4 5 6 7  
c g g w b w b g w  
d 1 2  
f
3
6
4 7  
5
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
3
5
L
0
1 2 3 4 5 6 7  
c g g w b w b g g  
d 1 2  
f
3
6
4 7 8  
5
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
3
5
L
0
1 2 3 4 5 6 7  
c g g w b w b g b  
d 1 2  
f
3
6
4 7 8  
5
9
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
7
3 5  
L
0
1 2 3 4 5 6 7  
c g g w b w b g b  
d 1 2  
f
3
6
4 7 8  
5
9
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
7
3 5  
L
0
1 2 3 4 5 6 7  
c g g w b w b b b  
d 1 2  
f
3
6
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
6
7 3 5  
L
0
1 2 3 4 5 6 7  
c g g w b w b b b  
d 1 2  
f
3
6
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
6
7 3 5  
L
0
1 2 3 4 5 6 7  
c g b w b w b b b  
d 1 2  
f 11  
3
6
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
1
6 7 3 5  
L
0
1 2 3 4 5 6 7  
c g b w b w b b b  
d 1 2  
f 11  
3
6
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
1
6 7 3 5  
L
0
1 2 3 4 5 6 7  
c g b g b w b b b  
d 1 2 12 3  
11  
4 7 8  
5 10 9  
f
6
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
1
6 7 3 5  
L
0
1 2 3 4 5 6 7  
c g b b b w b b b  
d 1 2 12 3  
f 11 13 6  
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
2
1 6 7 3 5  
L
0
1 2 3 4 5 6 7  
c g b b b w b b b  
d 1 2 12 3  
f 11 13 6  
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
2
1 6 7 3 5  
L
0
1 2 3 4 5 6 7  
c b b b b w b b b  
d 1 2 12 3  
f 14 11 13 6  
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
0
2 1 6 7 3 5  
L
0
1 2 3 4 5 6 7  
c b b b b w b b b  
d 1 2 12 3  
f 14 11 13 6  
4 7 8  
5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
0
2 1 6 7 3 5  
L
0
1 2 3 4 5 6 7  
c b b b b b b b b  
d 1 2 12 3 15 4 7 8  
f 14 11 13 6 16 5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
4
0 2 1 6 7 3 5  
L
0
1 2 3 4 5 6 7  
c b b b b b b b b  
d 1 2 12 3 15 4 7 8  
f 14 11 13 6 16 5 10 9  
c[u] gray  
d[u] time ← time + 1  
for each v Adj[u]  
if c[v] = white  
[v] u  
visita(v)  
c[u] black  
f[u] time ← time + 1  
insertFront(L, u)  
Ordenação Topológica DFS  
4
0 2 1 6 7 3 5  
L
0
1 2 3 4 5 6 7  
c b b b b b b b b  
d 1 2 12 3 15 4 7 8  
f 14 11 13 6 16 5 10 9  
OrdenacaoTopologicaDFS(G)  
L ← ∅  
BuscaEmProfundidade(G)  
return L  
Ordenação Topológica (DFS) Análise  
OrdenacaoTopologicaDFS(G)  
L ← ∅  
Complexidade: O(V + A)  
BuscaEmProfundidade(G)  
return L  
Ordenação Topológica Aplicações  
Dependência entre tarefas: uma ordenação topológica é uma  
sequência válida de tarefas;  
Pré-requisitos de disciplinas: uma ordenação topológica é uma  
sequência válida para se cursar as disciplinas;  
Instalação de pacotes: uma ordenação topológica é uma  
sequência válida para instalação de pacotes com dependências;  
Compilação de sistemas: uma ordenação topológica é uma  
sequência válida para compilar bibliotecas com dependências;  
Exercícios  
Lista de Exercícios 13 Ordenação Topológica  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Halim e Halim. Competitive Programming, 3rd  
Edition, 2003.  
Capítulo 4: Graph  
Cormen, Leiserson, Rivest e Stein. Algoritmos –  
Teoria e Prática, 2ª. Edição, Editora Campus,  
2
002.  
Capítulo 22: Algoritmos Elementares de Grafos