Grafos v DFS

5/26/2018 Grafos v DFS

1/5

Algoritmos e Estruturas deDados II

1

ra os :Percursos em Digrafos e

Ordenao TopolgicaRicardo J. G. B. Campello

Parte deste material baseado em adaptaes e extenses de slidesdisponveis em http://ww3.datastructures.net (Goodrich & Tamassia).

OrganizaoReviso (DFS)

Percursos em Digrafos Exemplo de Execuo (DFS)

Propriedades e Aplicaes

Algoritmos&Estrutura

sdeDadosII

2

Digrafos Acclicos (DAGs)

Ordenao Topolgica

Reviso (Algoritmo DFS)

DB

A

C

E

AlgoritmoDFS(G, v)

v.labelDESCOBERTO

process_vertex(v)

para todo e incidentEdges(G, v)

yopposite(G, v, e)

Algoritmos&Est

ruturasdeDadosII

3

Assume-se que inicialmente os vrtices de G sorotulados como no descobertos.

DB

A

C

E

. = -

y.parent v

DFS(G,y)

seno

se (y.label=EXPLORADO )

process_edge(e)

v.labelEXPLORADO

Percursos em DigrafosDFS e BFS podem ser adaptados para digrafos.

Essas adaptaes so mais genricas: qualquer grafo no-direcionado pode ser

Algoritmos&Est

ruturasdeDadosII

4

.

Mudana:

percurso s feito no sentido correto das arestas,ou seja, apenas atravs das arestas de sada.

logo, no preciso se preocupar em no processar duasvezes a mesma aresta

arestas podem ser processadas no vrtice de sada


2/5

DFS em DigrafosDFS direcionado:

as arestas que no so de descoberta no so mais necessariamentede retorno, pois no mais necessariamente apresentam a propriedadede conectar um vrtice a um ancestral na rvore DFS.


sdeDadosII

5

De fato, as arestas podem tambm ser de:

avano: conectam um vrtice a um descendente na rvore DFS

cruzamento: conectam um vrtice a outro que no nemdescendente nem ancestral na rvore DFS

DFS em DigrafosExemplo:

BOS

JFKSFO

ORD


sdeDadosII

6

MIA

DFW

LAX

DFS em DigrafosArestas:

De descoberta

_______

De retorno

1

27

5

Algoritmos&Est

ruturasdeDadosII

7

----------

De avano

_______

De cruzamento

----------- 6

3

4

Percursos em DigrafosAs adaptaes de DFS e BFS para digrafos permitem:

Obter, para cada vrtice de G, o subgrafo alcanvel a

partir daquele vrtice. Calcular os componentes fortemente conexos de G e

Algoritmos&Est

ruturasdeDadosII

8

es ar se , como um o o, or emen e conexo.

Encontrar um ciclo direcionado em G.

Obter um caminho com o menor nmero de arestasentre dois vrtices (BFS).

...


3/5

Percursos em DigrafosPropriedade 1: DFS ou BFS em um digrafo G partindo

de um vrtice s explora todos os vrtices e arestasalcanveis a partir de s.

Exerccio: Justificar a Propriedade 1


sdeDadosII

9

Propriedade 2:As arestas de descoberta DFS ou BFSformam uma rvore com caminhos direcionados de spara cada um dos vrtices alcanveis a partir des.

Exerccio: Justificar a Propriedade 2

Percursos em DigrafosAnlise:

Tempo: Se G for implementado com uma lista de adjacnciasou estrutura alternativa, ento DFS (BFS) roda em tempoO(ns+ms), ondens ems so respectivamente os nmeros devrtices e arestas alcanveis a partir des.


sdeDadosII

10

Cada vrtice e aresta alcanveis so explorados uma nica vez

no caso de aresta, a partir da sua origem

Espao:

DFS utiliza O(ns) espao auxiliar com a pilha de recurso devido ns chamadas recursivas com espao constante em cada uma delas.

BFS no possui recurso, mas utiliza espao auxiliar O(ns) paraarmazenar a fila de vrtices Q.

Percursos em DigrafosTeste de Conexo Forte: Podemos executar DFS ouBFS mltiplas vezes e verificar se o grafo fortemente

conexo verificando se a partir de cada vrtice tomadocomo origem todos os demais vrtices so alcanveis

Algoritmos&EstruturasdeDadosII

11

Tempo O(n (n +m) ) no pior caso.

Qual o pior caso?

Nota: possvel executar um teste de conexo forte em tempoO(n +m ) com apenas duas execues de DFS ou BFS, uma

sobre o digrafo original G e a outra sobre o seu transposto GT: Desafio: Descubra o porqu sem checar a literatura!!!

Digrafos AcclicosGrafos Direcionados Acclicos (DAGs): Como sugere o nome, sodigrafos que no possuem ciclos. Exemplos:

Hierarquia de heranas entre classes em orientao a objetos Pr-requisitos entre disciplinas de um curso

1

2

4

3

5


12

Restries de cronograma entre tarefas de um projeto

Ordenao Topolgica: Trata-se de uma ordenao dos vrticesv1, ..., vn de um DAG G tal que para qualquer aresta direcionada(vi, vj) tem-se i < j.

Caminhos direcionados percorrem os vrtices em ordem crescente.

Qualquer caminho entre vi e vj no passa por vk tal quek < i ouk > j.

Vide exemplo simples acima (no canto superior direito)


4/5

Ordenao TopolgicaAlgoritmo mais popular utiliza as seguintes

Propriedades de DAGs: Necessariamente possuem ao menos um vrtice sem arestas

incidentes de entrada (apenas arestas de sada ou nenhuma).


sdeDadosII

13

Se todo vrtice possui ao menos uma aresta de entrada,necessariamente existe ao menos um ciclo.

Se tais vrtices e as suas arestas de sada forem removidas, ografo restante tambm um DAG.

Idia do Algoritmo: Remover sucessivamente aquelesvrtices sem arestas incidentes de entrada, rotulando osmesmos em ordem crescente de remoo e removendotambm as respectivas arestas de sada.

Ordenao TopolgicaAlgoritmo TopologicalSort(G)

S Pilha Vaziapara todo u vertices(G)

se u.inDegree = 0push(S, u)

t 1

Note que os vrticesno precisam ser defato removidos do grafo.

suficiente modificarartificialmente uma


sdeDadosII

Espao e tempo de execuo de pior caso: O(n +m ) Detecta Existncia de Ciclos:

G no DAG se um ou mais vrtices no for removido / rotulado.

upop(S)u.topsortttt + 1para todo e outgoingEdges(G, u)

vopposite(G, u, e)

v.inDegree v.inDegree

1se v.inDegree = 0

push(S, v)

entrada de cada vrtice.

1

24

3

5

Exemplo:

OrdenaoTopolgica

Note o uso de uma filaao invs de pilha.

De fato, qualquer EDpode ser utilizada.

Diferentes EDs podem


produzir ordenstopolgicas distintas.

Ordenao topolgicano nica!

Ordenao TopolgicaExemplos:

1

3 2 23 1


6

75

8

9

4

4

75

8

9

6


5/5

Exerccios1. Modifique o pseudo-cdigo DFS de grafos no direcionados para

que este seja vlido para grafos direcionados. Para tanto, faaas modificaes necessrias ao TAD grafo apresentado em aula.

Dica: Note que no mais necessrio se preocupar em no processarcada aresta mais de uma vez, apenas no vrtice de sada.


sdeDadosII

17

. s para que esta seja vlida para grafos direcionados.

3. necessrio mudar algo na especializao do algoritmo DFSpara busca de ciclos vista em aula se o grafo for direcionado?Explique.

Nota: Observe que oprincpiodo uso de DFS para busca de ciclos nomuda, ou seja, arestas de retornocontinuam caracterizando ciclos(agora direcionados) e continuam sendo caracterizadas por levarem atum vrtice j descobertomas ainda no totalmente explorado.

4. Repita os Exerccios 1 e 2 para busca em largura (BFS).

Exerccios5. Descreva com suas palavras uma forma de calcular o fechamento

transitivo de um digrafo G usando BFS ou DFS. Assumindo que o

digrafo possuim arestas,n vrtices e fortemente conexo, qual acomplexidade do seu mtodo em termos de tempo de execuo?

Dica: Tome como base a Propriedade 1 de percursos em digrafos


sdeDadosII

18

. .est interessado nos seguintes cursos: LA15, LA16, LA22, LA31, LA32,LA126, LA127, LA141 e LA169. Dados os pr-requisitos desses cursosabaixo, mostre como usar ordenao topolgica para encontrar umaseqncia de cursos que permita satisfazer todos os pr-requisitos: LA15 e LA22: nenhum

LA16 e LA31: LA15 LA32: LA16 e LA31

LA126: LA22 e LA32

LA127: LA16

LA141: LA22 e LA16

LA169: LA32

Mostre uma tal seqncia eresponda justificadamente seela nica ou no!

RefernciasM. T. Goodrich and R. Tamassia, Data Structures and

Algorithms in C++/Java, John Wiley & Sons, 2002/2005.

N. Ziviani, Projeto de Algoritmos, Thomson, 2a. Edio, 2004.


22

. . , . . , . . ,to Algorithms, MIT Press, 2nd Edition, 2001.

S. Skiena e M. Revilla, Programming Challenges: TheProgramming Contest Training Manual, Springer-Verlag, 2003.

Documents

Grafos v DFS