Caminhamento em Grafos:
Busca em Largura e Busca em
Profundidade
Estruturas Discretas
Busca em Largura
BFS(G)
1 for every vertex s of G not explored yet
2
do Enqueue(S,s)
3
mark vertex s as visited
while S is not empty do
4
5
u ← Dequeue(S);
6
For each v in Adj[u] then
if v is unexplored then
7
8
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Notação
• Adj[u] : lista dos vértices adjacentes a u em alguma ordem
• Dequeue(S): Remove o primeiro elemento da fila S
• Enqueue (S,v) : Adiciona o nó v na fila S
Estruturas Discretas
Exemplo
S
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
1
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
4
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
45
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
452
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
52
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
52
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
52
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
2
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
6
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
3
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
3
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Exemplo
S
7
3
4
1
BFS(G)
2
1 for every vertex s of G not explored yet
2
do Enqueue(S,s);
3
4
5
6
7
8
mark vertex s as visited
while S is not empty do
7
5
6
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
mark edge (v,u) as tree edge
9
10
mark vertex v as visited
Enqueue(S,v)
Estruturas Discretas
Distâncias da origem aos demais vértices
BFS(G)
1
2
For each v do d[v]infinito
3
mark vertex s as visited
while S is not empty do
4
5
6
7
8
9
(inicia o vetor d)
Enqueue(S,s) ; d[s]0
u ← Dequeue(S);
For each v in Adj[u] then
if v is unexplored then
10
11
d[v]d[u]+1
(atualiza o valor de d[v])
mark edge (v,u) as tree edge
mark vertex v as visited
Enqueue(S,v)
• Assumimos que o grafo é conexo
• Ao término da execução d[v] guarda a distância entre a origem s e o vértice v
Estruturas Discretas
Propriedades da Busca em Largura
Teorema: A BFS visita os vértices em ordem crescente de distâncias
L0
L4
L1
L3
L2
Teorema: Para toda aresta (v, w) em G tal que v  Li e w  Lj, |i – j| ≤ 1.
Estruturas Discretas
Busca em Profundidade
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Busca em Profundidade : Exemplo
DFS(G)
1
Para todo v em G
2
Se v não visitado então
3
DFS-Visit(G, v)
1
2
DFS-Visit(G, v)
6
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
Insira aresta (v, w) na árvore
5
DFS-Visit(G, w)
Estruturas Discretas
3
4
7
5
Aplicações: Determinar as Componentes Conexas
Vetor Componente(v)
• Armazena um número inteiro
correspondente a componente conexa
aonde v se encontra
Estruturas Discretas
Aplicações: Determinar as Componentes Conexas
COMPONENTES (G)
1
2
3
4
5
num =1
Para todo v em G
Se v não visitado então
componrnte(v)  num
DFS_visit(v,num)
6
num ++
DFS_Visit(v, num)
1
Marque v como visitado
2
Para todo w em Adj(v)
3
Se w não visitado então
4
DFS_Visit(w,num)
5
Estruturas Discretas
componente(w)  num
Aplicações: Determinar se um grafo é bipartido
■ G = (V,E) = (X,Y,E)
■XY = V
■XY = 
■{u,w}E então uX e wY
■ Exemplos
■professores e horários
■candidatos e postos
■masculino e feminino
Estruturas Discretas
A
D
B
E
C
F
Aplicações: Determinar se um grafo é bipartido
BIPARTITE (G)
1
2
3
4
Bipartite  true
Para todo v em G
Se v não visitado então
DFS_Visit(v,0)
DFS_Visit(v,p)
1 Marque v como visitado
2 partição(v)  p
3 Para todo w em Adj(v)
4
Se w não visitado então
5
DFS_Visit (w, 1– p )
6
Senão
7
Se partição(w)=p
8
Bipartite  false
Estruturas Discretas
A
D
B
E
C
F
Estrutura de Dados
Partição: vetor de |V| posições
• Partição(u) armazena 0 ou 1,
dependendo da partição em que o
vértice u se encontra
DFS: Estrutura de Dados
cor
• cor(u)=branco, u não foi visitado
• cor(u)=cinza, u já foi visitado mas seus vizinhos ainda não
• cor(u)=preto, u e seus vizinhos já foram visitados

• (u) = v se e somente se u é visitado quando a lista dos vizinhos de v
é percorrida
d
• d(u) marca o momento em que u é visitado
f
• f(u) marca o momento em que a DFS a partir de u termina (u se torna
preto)
Estruturas Discretas
Busca em Profundidade
DFS(G)
1 for every vertex u of G
2
cor[u]white; [u]NIL
3 time0
4 for every vertex v of G
5
if cor[v]=BRANCO then
6
DFS-Visit(u)
DFS-Visit(u)
1 cor[u]CINZA
2 time  time+1
3 d[u] time
4 for each v in Adj[u]
5
if cor[v]=BRANCO then
6
[v]u;
7
DFS-Visit[u]
8 cor[u]NEGRO
9 time time+1
10 f[u] time+1
Estruturas Discretas
Busca em Profundidade
Estruturas Discretas
Propriedades da DFS
Teorema 1: Seja T a árvore produzida por uma DFS em G e seja vw uma aresta de
G. Se v é visitado antes de w então v é ancestral de w em T.
Estruturas Discretas
Propriedades da DFS
Teorema 2: Sejam u e v dois vértices de G tal que u é visitado antes de v. Então uma
das duas possibilidades ocorre
• d(u) < d(v) < f(v) < f(u)
• d(u) < f(u) <d(v) < f(v)
Estruturas Discretas
Propriedades da DFS
Teorema 3: Um nó v é descendente de um nó u em uma busca em profundidade se e
somente se existe um caminho de u até v que utilize apenas nós com cor branca no
momento que u se torna cinza
=> Se existe o caminho branco podemos argumentar por indução no
tamanho do caminho. Seja w o primeiro vértice do caminho ‘branco’ que
liga u a v que é visitado durante DFS(u). Este w tem que existir já que o
sucessor de u no caminho é visitado durante a DFS(u) pela Teorema 1.
Segue que w é descendente de u e v é descendente de w pela hipótese de
indução.
<= Se não existe caminho branco então DFS(u) não alcança v
Estruturas Discretas
Classificação de arcos em um dígrafo
1. Arco de Árvore: (u,v) é do tipo ‘A’ se v é visitado pela
primeira vez quando a lista Adj[u] é percorrida
2. Arco Reverso: (u,v) é do tipo ‘R’ se v é ancestral de u na
árvore gerada pela DFS
3. Arco Direto: (u,v) é do tipo ‘D’ se v é descendente de u
na árvore gerada pela DFS e (u,v) não é do tipo ‘A’
4. Arco Cruzado: Demais arcos
Estruturas Discretas
Propriedades da DFS
Estruturas Discretas
Testando se um grafo direcionado contem ciclos
Teorema: O grafo G é cíclico se e somente se a execução de uma DFS em
G produz um arco reverso.
Prova
 Seja C um ciclo em G e seja u o primeiro nó de C visitado pela DFS. Seja v
o predecessor de C no ciclo. Portanto, v é descendente de u (caminhos brancos)
e o arco (u,v) é reverso.
Seja (u,v) um arco reverso. Portanto, v é descendente de u. Logo, existe um
caminho de v para u em G. Adicionando (u,v) a este caminho obtemos um ciclo
Estruturas Discretas
Testando se um grafo direcionado contem ciclos
DFS(G)
1
for every vertex v of G
2
do set d[v]  0,f[v]  0
3
Time  1; Aciclico  true
4
for every vertex v of G
5
if d[v] =0 then
6
DFS(G, v)
7
Return Aciclico
DFS_Visit (v)
1
d[v]  time ; time ++
2
For every w in Adj(v)
3
if d[w]=0 then
4
DFS_Visit (w)
5
Else if f[w]=0 then ( ‘arco reverso’)
6
Aciclico  false
7
f[v]  time; time ++
Estruturas Discretas