Busca em Profundidade

Prévia do material em texto

GCC218 � Algoritmos em Grafos
Mayron César O. Moreira
Universidade Federal de Lavras
mayron.moreira@u�a.br
Mayron César O. Moreira (UFLA) GCC218 1 / 10
Conteúdo
1 Busca em Profundidade
Pontes e Vértices de Articulação
Componentes Fortemente Conexas
Exercício
2 Referências
Mayron César O. Moreira (UFLA) GCC218 2 / 10
Busca em Profundidade (DFS - Depth First Search)
Aplicações
Caracterização de arestas em grafos (detecção de ciclos); Ordenação
topológica; Componentes fortemente conexas.
Ideia
Procurar �mais fundo� no grafo sempre que possível;
Utiliza backtracking para voltar ao nó pai e continuar a busca.
Vejamos a implementação no JuPy.
Mayron César O. Moreira (UFLA) GCC218 3 / 10
Pontes e Vértices de Articulação
O vértice 4 é um vértice de articulação;
O vértice 2 não é um vértice de articulação.
Figura: Efeitos da remoção de vértices (Goldbarg & Goldbarg, 2012).
Implementações no JuPy.
Mayron César O. Moreira (UFLA) GCC218 4 / 10
Pontes e Vértices de Articulação
A aresta u1 é uma ponte;
As arestas u2 e u3 não são pontes.
Figura: Efeitos da remoção de arestas (Goldbarg & Goldbarg, 2012).
Implementações no JuPy.
Mayron César O. Moreira (UFLA) GCC218 4 / 10
Componentes fortemente conexas
De�nição
Uma componente fortemente conexa de um digrafo G = (V ,E ) é o
conjunto máximo de vértices C ⊆ V tal que, para todo par de vértices u e
v em C , temos u v e v u.
Exemplo: C = {a, b, e}.
Mayron César O. Moreira (UFLA) GCC218 5 / 10
Componentes fortemente conexas - Solução via DFS
Apliquemos DFS!
Mayron César O. Moreira (UFLA) GCC218 6 / 10
Componentes fortemente conexas - Solução via DFS
Após aplicação da DFS:
Agora, considere o grafo reverso de G : GT .
Apliquemos DFS(GT ), em ordem decrescente de u.f .
Mayron César O. Moreira (UFLA) GCC218 6 / 10
Componentes fortemente conexas - Solução via DFS
Após aplicação da DFS em G t , priorizando a ordem decrescente de v .f :
Mayron César O. Moreira (UFLA) GCC218 6 / 10
Componentes fortemente conexas
Mayron César O. Moreira (UFLA) GCC218 7 / 10
Componentes fortemente conexas
Resultado �nal:
Mayron César O. Moreira (UFLA) GCC218 7 / 10
Componentes fortemente conexas via DFS
Algorithm 1 CFC-DFS
Require: G = (V ,E ).
1: Chame DFS(G ) para calcular os tempos de término u.f , ∀u ∈ V ;
2: Calcular GT ;
3: Chame DFS(GT ), considerando os vértices em ordem decrescente de
u.f (calculado no Passo 1);
4: Cada componente fortemente conexa será uma árvore da �oresta obtida
no Passo 3.
Complexidade: ordem de n +m operações, sendo |V | = n e |E | = m.
Mayron César O. Moreira (UFLA) GCC218 8 / 10
Exercício
Encontre as componentes fortemente conexas do grafo abaixo, utilizando o
Algoritmo CFC-DFS.
Figura: Loureiro & Assunção (2016).
Mayron César O. Moreira (UFLA) GCC218 9 / 10
Referências
Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and
Stein, Cli�ord (2009). Introduction to algorithms, 3ed., MIT press.
Goldbarg, Marco and Goldbarg, Elizabeth (2012). Grafos: Conceitos,
algoritmos e aplicações, 1ed., Elsevier.
Loureiro, Antonio Alfredo Ferreira (2020). Notas de aula (Matemática
Discreta) do professor Antonio Alfredo Ferreira Loreiro (DCC/UFMG),
https://homepages.dcc.ufmg.br/~loureiro/md.html. Último
acesso: 25 de maio de 2020.
Mayron César O. Moreira (UFLA) GCC218 10 / 10
https://homepages.dcc.ufmg.br/~loureiro/md.html
	Busca em Profundidade
	Pontes e Vértices de Articulação
	Componentes Fortemente Conexas
	Exercício
	Referências