-
Professor: Humberto Nigri
[email protected]
Teoria dos Grafos Busca em Profundidade
-
! Busca em Profundidade
! Busca em Largura
! Algoritmo de Dijkstra
Algoritmos de Caminhamento
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
No visitados
Visitados
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
B
C
D
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
C
D
F
B
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
C
D
F
B
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
C
D B
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
C
D B
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
C
D B
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
C
D B
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
C
D B
F
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
D B
F C
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
D B
F C
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
D B
F C
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
D B
F C
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
0
1
2
3
5
4
6
7 8
9 A
D B
F C
(1) Marque todos os vrtices como no visitados
(2) Escolha um vrtice no visitado V aleatoriamente e marque o
como visitado
(3) Escolha aleatoriamente um vizinho de V no visitado e marque
o como visitado
(4) Repita o passo (3) enquanto existirem vizinhos no
visitados
(5) Volte ao vrtice pai e repita o passo (3)
(6) Se existirem vrtices no visitados, volte ao passo (2)
Busca em Profundidade
-
Algoritmo Marque todos os vrtices como no visitados para cada
vrtice V no visitado faa visite(v)
visite (V) Marque V como visitado para cada vizinho i (no
visitado) de V faa visite (i)
Busca em Profundidade
-
Algoritmo Marque todos os vrtices como no visitados para cada
vrtice V no visitado faa visite(v)
visite (V) Marque V como visitado para cada vizinho i (no
visitado) de V faa visite (i)
(1) Marque todos os vrtices como no
visitados
No visitados
Visitados
Busca em Profundidade
-
Algoritmo Marque todos os vrtices como no visitados para cada
vrtice V no visitado faa visite(v)
visite (V) Marque V como visitado para cada vizinho i (no
visitado) de V faa visite (i)
(2) Escolha um vrtice no visitado V aleatoriamente e
marque o como visitado
Busca em Profundidade
-
Algoritmo Marque todos os vrtices como no visitados para cada
vrtice V no visitado faa visite(v)
visite (V) Marque V como visitado para cada vizinho i (no
visitado) de V faa visite (i)
(3) Escolha aleatoriamente um vizinho de V no visitado
e marque o como visitado
(4) Repita o passo anterior enquanto
existirem vizinhos no
visitados
Busca em Profundidade
-
Algoritmo Marque todos os vrtices como no visitados para cada
vrtice V no visitado faa visite(v)
visite (V) Marque V como visitado para cada vizinho i (no
visitado) de V faa visite (i)
(5) Volte ao vrtice pai e
repita o passo (3) Voltar para o pai significa acabar a funo
visite chamada recursivamente
Busca em Profundidade
-
Algoritmo Marque todos os vrtices como no visitados para cada
vrtice V no visitado faa visite(v)
visite (V) Marque V como visitado para cada vizinho i (no
visitado) de V faa visite (i)
(6) Se existirem vrtices
no visitados, volte ao
passo (2)
A volta ao passo (2) acontece por causa deste loop
Busca em Profundidade
-
! Como adaptar o algoritmo de busca em
profundidade para contabilizar o nmero de
componentes em um grafo ?
! Como adaptar o algoritmo de busca em
profundidade para encontrarmos a soluo
tima do PCV?
Exerccios
