Estruturas de Dados - Exemplos - Escalonamento (Dibio)

Prévia do material em texto

dibio@unb.br
Assuntos 
● Exemplos
– Escalonamento 
– Grafos Orientados Acíclicos
– Algoritmo de Kahn, 1962
– Algoritmo de Tarjan, 1976
– Exemplo 
dibio@unb.br
dibio@unb.br
Solução para escalonamento por 
(Kahn, 1962)
● Inicia escolhendo nós na mesma ordem que uma 
eventual ordenação topológica. Primeiro, encontra 
uma lista de nós iniciais que não possuem 
nenhuma aresta que chega a eles, e os coloca em 
um conjunto S. Pelo menos um desses nós deve 
existir em grafos orientados acíclicos.
dibio@unb.br
Algoritmo de Kahn, 1962
L ← Lista vazia que conterá todos os elementos ordenados
S ← Conjunto de todos os nós com nenhuma aresta que chega a eles
while S não for vazia do
 remover um nó n de S
 inserir n em L
 for cada nó m com aresta e from n to m do
 remover aresta e do grafo
 if m não tiver mais arestas que chegam then
 inserir m em S
if grafo tiver arestas then
 output error message (grafo possui pelo menos um ciclo)
else 
 output message (ordem topológica proposta é: L)
dibio@unb.br
Outro algoritmo, usando agora 
DFS (busca em profundidade) 
(Tarjan, 1976)
● O algoritmo varre cada nó do grafo, em ordem 
arbitrária e inicia uma busca em profundidade que 
termina quando atingir um nó já visitado.
dibio@unb.br
Algoritmo de Tarjan, 1976
L ← Lista vazia que conterá os nós ordenados
S ← Conjunto de todos os nós com nenhuma aresta que chega a eles 
função visitar(nó n)
 if n não foi visitado ainda then
 marque n como visitado
 for cada nó m com uma aresta from n to m do
 visitar(m)
 incluir n em L
for cada nó n em S do
 visitar(n)
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
dibio@unb.br
Referências
● Kahn, A. B. (1962), "Topological sorting of large 
networks", Communications of the ACM 5 (11): 
558–562,
● Tarjan, Robert E. (1976), "Edge-disjoint spanning 
trees and depth-first search", Algorithmica 6 (2): 
171–185
dibio@unb.br
Referências
● Cormen, T.; Leiserson, C. & Rivest, R. 
 Algoritmos: teoria e prática, Campus Editora, RJ, 
 2002.
● Sedgewick, R. Algorithms in C, 3rd edition, 
Addison Wesley, EUA, 2002.
● Tenenbaum, A.; Langsam, Y. & Augenstein, M. 
 Estruturas de Dados usando C, Makron Books, 
 RJ, 1995.
● Ziviani, N. Projetos de Algoritmos com 
Implementações em Pascal e C, Cengage 
Learning, SP, 2004.
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17