aula26

Prévia do material em texto

AULA 26
ESTRUTURA DE DADOS
Grafos – Busca em Profundidade
Norton T. Roman & Luciano A. Digiampietri
Grafos – Busca em Profundidade
Fazer buscas em um grafo significa seguir suas arestas
sistematicamente, de modo a visitar seus vértices
A estratégia seguida pela busca em profundidade
(Depth-first search ou DFS) é buscar mais fundo no
grafo sempre que possível
A busca para quando encontramos o que queríamos
ou visitamos todos os vértices
Grafos – Busca em Profundidade
Fazer buscas em um grafo significa seguir suas arestas
sistematicamente, de modo a visitar seus vértices
A estratégia seguida pela busca em profundidade
(Depth-first search ou DFS) é buscar mais fundo no
grafo sempre que possível
A busca para quando encontramos o que queríamos
ou visitamos todos os vértices
Grafos – Busca em Profundidade
Fazer buscas em um grafo significa seguir suas arestas
sistematicamente, de modo a visitar seus vértices
A estratégia seguida pela busca em profundidade
(Depth-first search ou DFS) é buscar mais fundo no
grafo sempre que possível
A busca para quando encontramos o que queríamos
ou visitamos todos os vértices
Grafos – Busca em Profundidade
Na busca em profundidade, as arestas são exploradas a
partir do vértice v mais recentemente descoberto que
ainda tem arestas não exploradas saindo dele.
Quando todas as arestas de v são exploradas, a
busca volta ao vértice anterior a v (backtracking),
para seguir arestas ainda não exploradas
Grafos – Busca em Profundidade
Na busca em profundidade, as arestas são exploradas a
partir do vértice v mais recentemente descoberto que
ainda tem arestas não exploradas saindo dele.
Quando todas as arestas de v são exploradas, a
busca volta ao vértice anterior a v (backtracking),
para seguir arestas ainda não exploradas
Grafos – Busca em Profundidade
O processo continua até que tenhamos descoberto
todos os vértices que são atingíveis a partir do vértice
inicial
Um vértice v é atingível a partir de um vértice u se
houver um caminho de u a v no grafo
Se restarem ainda vértices não visitados, um é
selecionado e reiniciamos a busca a partir dele.
Grafos – Busca em Profundidade
O processo continua até que tenhamos descoberto
todos os vértices que são atingíveis a partir do vértice
inicial
Um vértice v é atingível a partir de um vértice u se
houver um caminho de u a v no grafo
Se restarem ainda vértices não visitados, um é
selecionado e reiniciamos a busca a partir dele.
Grafos – Busca em Profundidade
O processo continua até que tenhamos descoberto
todos os vértices que são atingíveis a partir do vértice
inicial
Um vértice v é atingível a partir de um vértice u se
houver um caminho de u a v no grafo
Se restarem ainda vértices não visitados, um é
selecionado e reiniciamos a busca a partir dele.
DFS – Funcionamento
Defina um nó inicial
Escolha um de seus adjacentes ainda não visitados
Visite-o
Repita o processo até atingir o nó objetivo, ou um nó cuja
adjacência já tenha sido toda visitada (nó final)
Se atingir um nó final que não seja objetivo:
Volte ao pai deste
Continue de um nó irmão ainda não visitado
DFS – Reescrevendo...
Defina um nó inicial
Enquanto este não for um nó objetivo ou final (nó cuja adjacência já
tenha sido toda visitada)
Escolha um de seus adjacentes ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão escolha outro nó inicial
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
oufinal (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Defina um nó inicial
Enquanto este não for um nó objetivo
ou final (nó cuja adjacência já tenha
sido toda visitada)
Escolha um de seus adjacentes
ainda não visitados
Visite-o
Se nó final não objetivo:
Volte ao pai deste
Se houver pai, repita. Senão
escolha outro nó inicial
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Note quea estrutura
resultante foi uma árvore
De fato, duas – uma
floresta
São as árvores de busca
em profundidade
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Note que a estrutura
resultante foi uma árvore
De fato, duas – uma
floresta
São as árvores de busca
em profundidade
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Note que a estrutura
resultante foi uma árvore
De fato, duas – uma
floresta
São as árvores de busca
em profundidade
v0
v1
v2
v3
v4
v5
DFS – Funcionamento
Note que a estrutura
resultante foi uma árvore
De fato, duas – uma
floresta
São as árvores de busca
em profundidade
v0
v1
v2
v3
v4
v5
Grafos – Busca em Profundidade
Ideia intuitiva – usamos em nosso dia a dia
Quando exploramos um ambiente, geralmente
seguimos uma direção preferencial, tomando
decisões quando há mais opções de caminhos
Se nos deparamos com um ambiente sem outra
saída, voltamos ao ponto da última decisão e
escolhemos outro caminho
Grafos – Busca em Profundidade
Ideia intuitiva – usamos em nosso dia a dia
Quando exploramos um ambiente, geralmente
seguimos uma direção preferencial, tomando
decisões quando há mais opções de caminhos
Se nos deparamos com um ambiente sem outra
saída, voltamos ao ponto da última decisão e
escolhemos outro caminho
Grafos – Busca em Profundidade
Ideia intuitiva – usamos em nosso dia a dia
Quando exploramos um ambiente, geralmente
seguimos uma direção preferencial, tomando
decisões quando há mais opções de caminhos
Se nos deparamos com um ambiente sem outra
saída, voltamos ao ponto da última decisão e
escolhemos outro caminho
DFS – Implementação
Nessa implementação,
iremos “colorir” os
vértices durante a busca,
indicando seu estado
Cada vértice é
inicialmente branco
v0
v1
v2
v3
v4
v5
DFS – Implementação
Nessa implementação,
iremos “colorir” os
vértices durante a busca,
indicando seu estado
Cada vértice é
inicialmente branco
v0
v1
v2
v3
v4
v5
DFS – Implementação
É feito amarelo quando
descoberto na busca
É feito vermelho quando
for finalizado (quando sua
lista de adjacentes for
completamente
examinada)
v0
v1
v2
v3
v4
v5
DFS – Implementação
É feito amarelo quando
descoberto na busca
É feito vermelho quando
for finalizado (quando sua
lista de adjacentes for
completamente
examinada)
v0
v1
v2
v3
v4
v5
DFS – Implementação
Também não buscaremos
por um nó específico
Faremos apenas uma
caminhada pelo grafo
usando o algoritmo de
busca em profundidade
v0
v1
v2
v3
v4
v5
DFS – Implementação
Também não buscaremos
por um nó específico
Faremos apenas uma
caminhada pelo grafo
usando o algoritmo de
busca em profundidade
v0
v1
v2
v3
v4
v5
DFS – Implementação
E, por tratar-se de uma
operação de busca,
usaremos a representação
que melhor se adequa a
isso
No caso, lista de
adjacências
v0
v1
v2
v3
v4
v5
DFS – Implementação
E, por tratar-se de uma
operação de busca,
usaremos a representação
que melhor se adequa a
isso
No caso, lista de
adjacências
v0
v1
v2
v3
v4
v5
DFS – Implementação
Começamos com as
definições já vistas para a
lista de adjacências
Definindo também
códigos para as “cores”
usadas
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef int bool;
typedef int TIPOPESO;
#define BRANCO 0
#define AMARELO 1
#define VERMELHO 2
DFS – Implementação
Começamos com as
definições já vistas para a
lista de adjacências
Definindo também
códigos para as “cores”
usadas
#include <stdio.h>
#include <stdlib.h>
#define true 1
#define false 0
typedef int bool;
typedef int TIPOPESO;
#define BRANCO 0
#define AMARELO 1
#define VERMELHO 2
DFS – Implementação
Passamos então à
definição do grafo:
typedef struct adjacencia {
int vertice;
TIPOPESO peso;
struct adjacencia *prox;
} ADJACENCIA;
typedef struct vertice {
/* Outros dados vão aqui*/
ADJACENCIA *cab;
} VERTICE;
typedef struct grafo {
int vertices;
int arestas;
VERTICE *adj;
} GRAFO;
DFS – Implementação
E, finalmente, à
caminhada no grafo
Começamos definindo um
arranjo de cores, que
armazenará a cor de cada
vértice
void profundidade(GRAFO *g) {
int cor[g->vertices];
int u;
for (u=0;u<g->vertices;u++) {
cor[u] = BRANCO;
}
for (u=0;u<g->vertices;u++) {
if (cor[u] == BRANCO)
visitaP(g,u,cor);
}
}
DFS – Implementação
E, finalmente, à
caminhada no grafo
Começamos definindo um
arranjo de cores, que
armazenará a cor de cada
vértice
void profundidade(GRAFO *g) {
int cor[g->vertices];
int u;
for (u=0;u<g->vertices;u++) {
cor[u] = BRANCO;
}
for (u=0;u<g->vertices;u++) {
if (cor[u] == BRANCO)
visitaP(g,u,cor);
}
}
DFS – Implementação
O índice do vértice no
arranjo adj em GRAFO
será o mesmo do arranjo
cor
Inicializamos todos os
vértices com branco
void profundidade(GRAFO *g) {
int cor[g->vertices];
int u;
for (u=0;u<g->vertices;u++) {
cor[u] = BRANCO;
}
for (u=0;u<g->vertices;u++) {
if (cor[u] == BRANCO)
visitaP(g,u,cor);
}
}
DFS – Implementação
O índice do vértice no
arranjo adj em GRAFO
será o mesmo do arranjo
cor
Inicializamos todos os
vértices com branco
void profundidade(GRAFO *g) {
int cor[g->vertices];
int u;
for (u=0;u<g->vertices;u++) {
cor[u] = BRANCO;
}
for (u=0;u<g->vertices;u++) {
if (cor[u] == BRANCO)
visitaP(g,u,cor);
}
}
DFS – Implementação
A verificação de todos os
vértices brancos serve
para garantir que, uma
vez esgotada uma árvore
de busca, possamos
reiniciar de algum outro
vértice não visitado
void profundidade(GRAFO *g) {
int cor[g->vertices];
int u;
for (u=0;u<g->vertices;u++) {
cor[u] = BRANCO;
}
for (u=0;u<g->vertices;u++) {
if (cor[u] == BRANCO)
visitaP(g,u,cor);
}
}
DFS – Implementação
A verificação de todos os
vértices brancos serve
para garantir que, uma
vez esgotada uma árvore
de busca, possamos
reiniciar de algum outro
vértice não visitado
v0
v1
v2
v3
v4
v5
início
DFS – Implementação
A verificação de todos os
vértices brancos serve
para garantir que, uma
vez esgotada uma árvore
de busca, possamos
reiniciar de algum outro
vértice não visitado
v0
v1
v2
v3
v4
v5reinício
DFS – Implementação
void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
while (v) {
if (cor[v->vertice]==BRANCO)
visitaP(g,v->vertice,cor);
v = v->prox;
}
cor[u] = VERMELHO;
}
Ao visitar um nó, o
marcamos com amarelo
Então visitamos sua
adjacência (arestas (u, v))
recursivamente
Mas apenas vértices
ainda não visitados
DFS – Implementação
void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
while (v) {
if (cor[v->vertice]==BRANCO)
visitaP(g,v->vertice,cor);
v = v->prox;
}
cor[u] = VERMELHO;
}
Ao visitar um nó, o
marcamos com amarelo
Então visitamos sua
adjacência (arestas (u, v))
recursivamente
Mas apenas vértices
ainda não visitados
DFS – Implementação
void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
while (v) {
if (cor[v->vertice]==BRANCO)
visitaP(g,v->vertice,cor);
v = v->prox;
}
cor[u] = VERMELHO;
}
Ao visitar um nó, o
marcamos com amarelo
Então visitamos sua
adjacência (arestas (u, v))
recursivamente
Mas apenas vértices
ainda não visitados
DFS – Implementação
void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
while (v) {
if (cor[v->vertice]==BRANCO)
visitaP(g,v->vertice,cor);
v = v->prox;
}
cor[u] = VERMELHO;
}
Ao visitar um nó, o
marcamos com amarelo
Então visitamos sua
adjacência (arestas (u, v))
recursivamente
Mas apenas vértices
ainda não visitados
DFS – Implementação
void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
while (v) {
if (cor[v->vertice]==BRANCO)
visitaP(g,v->vertice,cor);
v = v->prox;
}
cor[u] = VERMELHO;
}
Visitada toda a adjacência
de u, o finalizamos,
marcando de vermelho
DFS – Implementação
E se quisermos incluir
uma chave de busca?
Chaves de busca são
incluídas inicialmente em
VERTICE
E verificadas quando o nó
é visitado
typedef struct vertice {
/* Outros dados vão aqui*/
ADJACENCIA *cab;
} VERTICE;void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
...
}
DFS – Implementação
E se quisermos incluir
uma chave de busca?
Chaves de busca são
incluídas inicialmente em
VERTICE
E verificadas quando o nó
é visitado
typedef struct vertice {
/* Outros dados vão aqui*/
ADJACENCIA *cab;
} VERTICE;
void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
...
}
DFS – Implementação
E se quisermos incluir
uma chave de busca?
Chaves de busca são
incluídas inicialmente em
VERTICE
E verificadas quando o nó
é visitado
typedef struct vertice {
/* Outros dados vão aqui*/
ADJACENCIA *cab;
} VERTICE;
void visitaP(GRAFO *g, int u,
int *cor) {
cor[u] = AMARELO;
ADJACENCIA *v = g->adj[u].cab;
...
}
AULA 26
ESTRUTURA DE DADOS
Grafos – Busca em Profundidade
Norton T. Roman & Luciano A. Digiampietri