ACH2024 Aula05e06 Grafos BuscaEmProfundidade

Prévia do material em texto

1
Datas da provas – turma 94
P1: 27 de abril
P2: 25 de maio
P3: 29 de junho
Prova SUB (fechada): 06 de julho
2
ACH2024 
Aulas 05 e 06 – Grafos:
Busca em Profundidade
Profa. Ariane Machado Lima
3Slide do livro do Ziviani – cap 7
(antecessor de v)
4Slide do livro do Ziviani – cap 7
Medidores de tempo: úteis para
- acompanhar a evolução da busca
- utilizados em vários algoritmos de grafos
5Slide do livro do Ziviani – cap 7
Cada vértice 
tem:
cor(d[v],t[v])
6
7
buscaProfundidade(grafo){
 Aloca vetores cor, tdesc, tterm, antecessor com tamanho grafo->nrVertices
tempo ← 0;
Para cada vertice v 
cor[v] ← branco; tdesc[v] = tterm[v] = 0; antecessor[v] ← -1;
Para cada vertice v 
Se cor[v] = branco visitaBP(v, grafo, &tempo, cor, tdesc, tterm, antecessor);
}
visitaBP(v, grafo, tempo, cor, tdesc, tterm, antecessor){
cor[v] ← cinza; tdesc[v] ← ++(*tempo);
Para cada vertice u da lista de adjacência de v
Se u é branco
antecessor[u] ← v;
visitaBP(u, grafo, &tempo, cor, tdesc, tterm, antecessor);
tterm ← ++(*tempo);
cor[v] ← preto;
}
 
8Slide do livro do Ziviani – cap 7
9
Busca em Profundidade: Análise
Essa complexidade vale para as duas 
implementações de grafos? Se não:
- qual a complexidade para matrizes e listas de 
adjacência?
- então deve-se sempre usar uma ao invés de outra? 
Se não, por quê?
10Slide do livro do Ziviani – cap 7
11Slide do livro do Ziviani – cap 7
(u,v) é
avanço se tdesc[u] <= tdesc[v]
cruzamento caso contrário
12
Observação
Se o grafo é não direcionado, a busca em 
profundidade produzirá apenas arestas de 
árvore e arestas de retorno
Por quê?
13
Algumas aplicações de 
busca em profundidade
14
Identificar se um grafo é acíclico ou 
não
15Slide do livro do Ziviani – cap 7
16
Exercício
Implemente tal algoritmo
17
Slide do livro do Ziviani – cap 7
18
19
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
20
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
21
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
22
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
23
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
24
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
25
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
Qual seria a complexidade desse algoritmo?
26
Como poderíamos obter tal ordenação?
Quem são as últimas “tarefas”? As que não têm tarefas adjacentes.
Então os vértices que não possuem arestas SAINDO deles devem ficar no fim da lista
(ou seja, serem inseridos primeiro em uma lista ligada, com inserção sempre na frente)
E depois?
Remove esse vértice recém inserido (e as arestas que chegam nele) e recomeça o processo.
Qual seria a complexidade desse algoritmo? Pode chegar a O(V3)
A questão é como achar, de forma eficiente, os vértices sem adjacentes... 
27
Como poderíamos obter essa informação dos vértices sem adjacentes, a cada passo, 
de forma eficiente?
28
Como poderíamos obter essa informação dos vértices sem adjacentes, a cada passo, 
de forma eficiente?
BUSCA EM PROFUNDIDADE!
29
Como poderíamos obter essa informação dos vértices sem adjacentes, a cada passo, 
de forma eficiente?
BUSCA EM PROFUNDIDADE!
Como? Insere o vértice no início da lista quando ele se tornar preto...
30
Como poderíamos obter essa informação dos vértices sem adjacentes, a cada passo, 
de forma eficiente?
BUSCA EM PROFUNDIDADE!
Como? Insere o vértice no início da lista quando ele se tornar preto...
31
Desta forma, os vértices ficaram ordenados decrescentemente pelo tempo de término.
Por quê? 
32Slide do livro do Ziviani – cap 7
33
Encontrar um caminho entre dois 
vértices u e v
34
Encontrar um caminho entre dois 
vértices u e v
Partindo de u, o vértice v deve ser visitado (ou 
seja, deve pertencer à árvore de busca em 
profundidade com raiz em u)
35
Componentes conexos de um grafo 
não direcionado
36
Componentes conexos de um grafo 
não direcionado
Em um grafo não direcionado (não 
necessariamente verdade em um direcionado):
- cada vértice está contido em exatamente um 
componente conexo
- para cada vértice v, o componente conexo que 
contém v é exatamente o conjunto de todos os 
vértices alcançáveis por v 
37
Componentes conexos de um grafo 
não direcionado
Cada árvore de busca em profundidade 
corresponde a um componente conexo 
38Slide do livro do Ziviani – cap 7
39Slide do livro do Ziviani – cap 7
40Slide do livro do Ziviani – cap 7
41Slide do livro do Ziviani – cap 7
42Slide do livro do Ziviani – cap 7
	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
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42