Aula 11 - Busca em Grafos, Busca em Profundidade (1)

Prévia do material em texto

Grafos e Algoritmos Computacionais
Prof. André Britto
Busca em Grafos
 Busca em Profundidade:
Introdução
Grafos e Algoritmos Computacionais
Busca em Grafos
 Busca em Árvore
• Problema simples
• Semelhante a algoritmos já vistos em Estrutura de 
Dados.
2
Grafos e Algoritmos Computacionais
Busca em Árvore
3
algoritmo BuscaArvore
início
 Se árvore vazia então não faça nada
Senão 
 início
caminhe pela subárvore mais a esquerda da raiz;
após pela 2ª mais a esquerda;
após pela 3ª mais a esquerda;
e assim por diante;
 fim 
fim
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 
4
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1
5
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2
6
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5
7
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6
8
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10
9
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10 3
10
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10 3 7
11
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10 3 7 8
12
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10 3 7 8 11
13
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10 3 7 8 11 4
14
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10 3 7 8 11 4 9
15
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Árvore
 Que caminhamento é esse?
Ex.:
 Caminhamento : 1 2 5 6 10 3 7 8 11 4 9
Busca em nível ou largura
Ex.: 1 2 3 4 5 6 7 8 9 10 11
16
1
2
5
6
10
3
8
7
11
9
4
Grafos e Algoritmos Computacionais
Busca em Grafos
 Árvore  classe especial de grafo
 E para um grafo qualquer ? 
• Problemas: Falta de um referencial qual necessita de 
informação adicional para o processo de exploração.
• Marcas: Designa se o vértice foi ou não já 
considerado no processo de busca.
17
Grafos e Algoritmos Computacionais
Algoritmo Básico( Ideia )
 Quando seleciona-se aresta (v,w) a partir do vértice 
marcado v dizemos que (v,w) foi explorada e w foi 
alcançado. Um vértice torna-se explorado quando 
todas arestas incidentes no mesmo tiverem sido 
exploradas.
18
a
b
c
d
e f
hg
Grafos e Algoritmos Computacionais
Algoritmo Básico( Ideia )
 Quando seleciona-se aresta (v,w) a partir do vértice 
marcado v dizemos que (v,w) foi explorada e w foi 
alcançado. Um vértice torna-se explorado quando 
todas arestas incidentes no mesmo tiverem sido 
exploradas.
19
a
b
c
d
e f
hg
Grafos e Algoritmos Computacionais
Algoritmo Básico( Ideia )
 Quando seleciona-se aresta (v,w) a partir do vértice 
marcado v dizemos que (v,w) foi explorada e w foi 
alcançado. Um vértice torna-se explorado quando 
todas arestas incidentes no mesmo tiverem sido 
exploradas.
20
a
b
c
d
e f
hg
Grafos e Algoritmos Computacionais
Algoritmo Básico( Ideia )
 Quando seleciona-se aresta (v,w) a partir do vértice 
marcado v dizemos que (v,w) foi explorada e w foi 
alcançado. Um vértice torna-se explorado quando 
todas arestas incidentes no mesmo tiverem sido 
exploradas.
21
a
b
c
d
e f
hg
Grafos e Algoritmos Computacionais
Algoritmo Básico( Ideia )
 Quando seleciona-se aresta (v,w) a partir do vértice 
marcado v dizemos que (v,w) foi explorada e w foi 
alcançado. Um vértice torna-se explorado quando 
todas arestas incidentes no mesmo tiverem sido 
exploradas.
22
a
b
c
d
e f
hg
Grafos e Algoritmos Computacionais
Algoritmo Básico( Ideia )
 Quando seleciona-se aresta (v,w) a partir do vértice 
marcado v dizemos que (v,w) foi explorada e w foi 
alcançado. Um vértice torna-se explorado quando 
todas arestas incidentes no mesmo tiverem sido 
exploradas.
23
a
b
c
d
e f
hg
Grafos e Algoritmos Computacionais
Algoritmo Básico( Ideia )
 Quando seleciona-se aresta (v,w) a partir do vértice 
marcado v dizemos que (v,w) foi explorada e w foi 
alcançado. Um vértice torna-se explorado quando 
todas arestas incidentes no mesmo tiverem sido 
exploradas.
24
a
b
c
d
e f
hg
Grafos e Algoritmos Computacionais
Busca Geral
25
algoritmo BuscaGeral(G);
início
 escolher e marcar um vértice inicial;
 enquanto existir algum vértice v marcado e incidente a
 uma aresta (v,w) não explorada faça
 início
 escolher o vértice v e explorar (v,w);
 se w é não marcado então marcar w;
 fim
fim
Grafos e Algoritmos Computacionais
Busca Geral
26
algoritmo BuscaGeral(G);
início
 escolher e marcar um vértice inicial;
 enquanto existir algum vértice v marcado e incidente a
 uma aresta (v,w) não explorada faça
 início
 escolher o vértice v e explorar (v,w);
 se w é não marcado então marcar w;
 fim
fim
 Esta busca fornece um só resultado?
Grafos e Algoritmos Computacionais
Busca em Profundidade
Critério: “dentre os vértices marcados incidentes a 
alguma aresta não explorada, escolher aquele mais 
recentemente alcançado na busca.”.
27
Grafos e Algoritmos Computacionais
Busca em Profundidade
28
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
29
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
30
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
31
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
32
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
A cada aresta explorada um novo vértice ainda não 
visitado é marcado.
A busca constrói um árvore que chamamos uma árvore 
de profundidade.
As arestas dessa árvore são chamadas de arestas da 
árvore.
33
Grafos e Algoritmos Computacionais
Busca em Profundidade
34
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos ComputacionaisBusca em Profundidade
O que acontece quando encontramos um vértice já 
visitado?
O vértice já é marcado, logo a busca não visita ele 
novamente.
Essas arestas são chamadas de arestas de retorno.
35
Grafos e Algoritmos Computacionais
Busca em Profundidade
36
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
37
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
38
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
39
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
40
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
41
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
42
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
43
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
44
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
45
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
46
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
47
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
48
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
49
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
50
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
51
a
b
c
e a b
d V2
b 
V1
c V4
V4
V2 V3 h
V5
V5
a
b
ca g
e 
d 
f 
e 
Ex.:
f
g
h
a f V4 V5g h
V4 V5c f h
V4 V5c f g
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
52
algoritmo BP(G,v) {em inglês DFS}
{dados: um grafo simples e conexo G e um vértice v para 
início da busca}
início
 marque v;
 para todas as arestas (v,w) faça
 {é equivalente a para todo w  Adj(v) faça} 
início
 se w é não marcado então BP(G,w);
fim 
fim
Grafos e Algoritmos Computacionais
Busca em Profundidade
Complexidade do algoritmo básico BP
Espaço:
Grafos e Algoritmos Computacionais
Busca em Profundidade
Complexidade do algoritmo básico BP
Espaço: O(n+m) EA para armazenar o grafo.
 
54
Grafos e Algoritmos Computacionais
Busca em Profundidade
Complexidade do algoritmo básico BP
Espaço: O(n+m) EA para armazenar o grafo.
 
Tempo:
Grafos e Algoritmos Computacionais
Busca em Profundidade
Complexidade do algoritmo básico BP
Espaço: O(n+m) EA para armazenar o grafo.
 
Tempo: Depende de quantas chamadas fazemos e 
do trabalho realizado em cada uma delas. Ao se 
encerrar uma chamada de BP(G,v) temos que o 
trabalho realizado por ela foi na lista de adjacentes do 
vértice v: O( Adj(v) ). Mas, podemos realizar n 
chamadas, cada uma delas na marcação de cada 
vértice do grafo, portanto o tempo total é dado por:
 
56
Grafos e Algoritmos Computacionais
Busca em Profundidade
Complexidade do algoritmo básico BP
Espaço: O(n+m) EA para armazenar o grafo.
 
Tempo: Depende de quantas chamadas fazemos e 
do trabalho realizado em cada uma delas. Ao se 
encerrar uma chamada de BP(G,v) temos que o 
trabalho realizado por ela foi na lista de adjacentes do 
vértice v: O( Adj(v) ). Mas, podemos realizar n 
chamadas, cada uma delas na marcação de cada 
vértice do grafo, portanto o tempo total é dado por:
 
57
O(  Adj(vi) ) = O(n+m)
 n
i=1
varrer toda EA
Grafos e Algoritmos Computacionais
Busca em Profundidade
Proposição 1
Se G é conexo então todos os vértices serão 
marcados pelo algoritmo BP e todas as arestas serão 
visitadas pelo menos uma vez durante a execução do 
algoritmo.
58
Precisamos provar que o algoritmo de Busca em 
Profundidade está correto, ou seja que ele consegue 
percorrer todos os vértices e arestas do grafo, se o grafo 
for conexo. 
Grafos e Algoritmos Computacionais
Busca em Profundidade
Prova da Proposição 1
Suponha que BP foi aplicado em um grafo conexo G 
e seja U o conjunto de vértices não marcados após 
aplicação de BP. Como G é conexo, então existe uma 
aresta entre algum vértice marcado v e um vértice w de U. 
Mas, isso é uma contradição pois quando v foi explorado 
pelo BP todos os vértices adjacentes a ele foram 
inspecionados pelo algoritmo e se não estavam marcados, 
foram marcados nesse passo. Logo, todos os vértices 
foram visitados e como quando um vértice é visitado todas 
suas arestas são exploradas, então todas arestas de G 
foram exploradas.
59
Grafos e Algoritmos Computacionais
Busca em Profundidade
E se G não for conexo?
60
Grafos e Algoritmos Computacionais
Busca em Profundidade
E se G não for conexo?
61
BP pode determinar os Componentes de G
Grafos e Algoritmos Computacionais
Aplicação de Busca em Profundidade
62
algoritmo Componentes(G);
{supõe campo na EAD para guardar a numeração dos 
 componentes}
procedimento BP(G,v)
início
 marque v;
 v.comp := ncomp;
 para todas as arestas (v,w) faça
 início
 se w é não marcado então BP(G,w);
fim 
fim
Grafos e Algoritmos Computacionais
Aplicação de Busca em Profundidade
63
{programa principal}
Início
 ncomp := 0;
 enquanto existir algum vértice v não marcado faça
início 
 BP(G,v); 
 ncomp := ncomp + 1; 
fim
Fim
Grafos e Algoritmos ComputacionaisBusca em Profundidade
Se G é conexo, o algoritmo BP explora todos os vértices 
e arestas do grafo e divide as arestas em dois tipos: da 
árvore e de retorno.
A árvore geradora construída pelo BP é uma árvore 
geradora de G e é chamada de árvore de 
profundidade.
Caso G seja desconexo, a aplicação sucessiva de BP 
forma uma floresta de profundidade.
64
Grafos e Algoritmos Computacionais
Busca em Profundidade
65
Ex.:
a
b
d
fe g
c
h
aresta
da árvore
aresta
de retorno
Grafos e Algoritmos Computacionais
Busca em Profundidade
66
algoritmo ArvoreGeradora(G,v);
{use o algoritmo BP com pequena variação}
início
 marque v;
 para todas as arestas (v,w) faça
início
 se w é não marcado então
 início
 adicione (v,w) a T;
 ArvoreGeradora(G,w); 
 fim
 fim 
fim
Grafos e Algoritmos Computacionais
Busca em Profundidade
Normalmente os problemas que são solucionados através da aplicação 
de BP, introduzem modificações no código do algoritmo em dois locais: 
após a marcação de v (antes da chamada recursiva) ou após a chamada 
recursiva.
67
algoritmo BP(G,v) {em inglês DFS}
{dados: um grafo simples e conexo G e um vértice 
v para início da busca}
início
 marque v; TrabalhoAnterior em v;
 para todas as arestas (v,w) faça
 {é equivalente a para todo w  Adj(v) faça} 
início
 se w é não marcado então BP(G,w);
 TrabalhoPosterior em (v,w);
fim 
fim
Grafos e Algoritmos Computacionais
Busca em Profundidade
A ordem em que os vértices são visitados ou explorados 
é também muitas vezes importante para aplicações. 
Assim, define-se profundidade de entrada e de saída 
de v a ordem em que o vértice v foi alcançado pela 
primeira vez e explorado, respectivamente.
68
Grafos e Algoritmos Computacionais
Busca em Profundidade
Ex.: 
(utilizando a BP feita no exemplo)
69
a b c d e f g h
PE(v) 1 2 5 3 4 6 7 8
PS(v) 8 3 7 1 2 6 5 4
a
b
d
fe g
c
h
Grafos e Algoritmos Computacionais
Busca em Profundidade
 EXERCÍCIO DE FIXAÇÃO
 Fazer algoritmo de Busca em Profundidade não 
recursivo. Pensar em que lugar da Busca em 
Profundidade posso colocar o cômputo da 
profundidade de entrada e de saída.
70
Grafos e Algoritmos Computacionais
Exercícios Recomendados
 Jayme Szwarcfiter: 4.1*, 4.2*, 4.4*, 4.5**, 4.6*
 * Exercício de fixação
 ** Exercício de prova
1 - Prove que um grafo simples e seu complemento não podem ser
ambos desconexos.
2 - Os grafos bipartidos completos K1,n, conhecidos como grafos estrelas, 
são árvores. Prove que grafos estrelas são os únicos grafos bipartidos 
completos que são árvores
3 - Prove que um grafo é bipartido se e somente se todos os seus ciclos 
tiverem comprimento par
71
Grafos e Algoritmos Computacionais
Referências
 Seções 4.1, 4.2 e 4.3 do Szwarcfiter, J. L., Grafos e Algoritmos 
Computacionais, Ed. Campus, 1983.
 Seção 22.3 do Cormen, Introduction to Algorithms, MIT Press, 2001.
 Adaptado do material de aula da Profa. Leila Silva
 Seção 1.7 do Grafos: conceitos, algoritmos e aplicações. Goldbarg, E. e 
Goldbarg M. Elsevier, 2012
72
	Grafos e Algoritmos Computacionais
	Busca em Grafos
	Busca em Árvore
	Busca em Árvore (2)
	Busca em Árvore (3)
	Busca em Árvore (4)
	Busca em Árvore (5)
	Busca em Árvore (6)
	Busca em Árvore (7)
	Busca em Árvore (8)
	Busca em Árvore (9)
	Busca em Árvore (10)
	Busca em Árvore (11)
	Busca em Árvore (12)
	Busca em Árvore (13)
	Busca em Árvore (14)
	Busca em Grafos (2)
	Algoritmo Básico( Ideia )
	Algoritmo Básico( Ideia ) (2)
	Algoritmo Básico( Ideia ) (3)
	Algoritmo Básico( Ideia ) (4)
	Algoritmo Básico( Ideia ) (5)
	Algoritmo Básico( Ideia ) (6)
	Algoritmo Básico( Ideia ) (7)
	Busca Geral
	Busca Geral (2)
	Busca em Profundidade
	Busca em Profundidade (2)
	Busca em Profundidade (3)
	Busca em Profundidade (4)
	Busca em Profundidade (5)
	Busca em Profundidade (6)
	Busca em Profundidade (7)
	Busca em Profundidade (8)
	Busca em Profundidade (9)
	Busca em Profundidade (10)
	Busca em Profundidade (11)
	Busca em Profundidade (12)
	Busca em Profundidade (13)
	Busca em Profundidade (14)
	Busca em Profundidade (15)
	Busca em Profundidade (16)
	Busca em Profundidade (17)
	Busca em Profundidade (18)
	Busca em Profundidade (19)
	Busca em Profundidade (20)
	Busca em Profundidade (21)
	Busca em Profundidade (22)
	Busca em Profundidade (23)
	Busca em Profundidade (24)
	Busca em Profundidade (25)
	Busca em Profundidade (26)
	Busca em Profundidade (27)
	Busca em Profundidade (28)
	Busca em Profundidade (29)
	Busca em Profundidade (30)
	Busca em Profundidade (31)
	Busca em Profundidade (32)
	Busca em Profundidade (33)
	Busca em Profundidade (34)
	Busca em Profundidade (35)
	Aplicação de Busca em Profundidade
	Aplicação de Busca em Profundidade (2)
	Busca em Profundidade (36)
	Busca em Profundidade (37)
	Busca em Profundidade (38)
	Busca em Profundidade (39)
	Busca em Profundidade (40)
	Busca em Profundidade (41)
	Busca em Profundidade (42)
	Exercícios Recomendados
	Referências