algoritmos e estrutura de dados 3-Grafos(Algoritmos)

Prévia do material em texto

Estruturas de Dados IIEstruturas de Dados IIEstruturas de Dados II
Rodrigo Porfírio da Silva SacchiRodrigo Porfírio da Silva SacchiRodrigo Porfírio da Silva Sacchi
rodrigosacchi@ufgd.edu.brrodrigosacchi@ufgd.edu.br
Representação e Algoritmos Elementares de GrafosRepresentação e Algoritmos Elementares de Grafos
NOTA: Este material sofreu ligeiras alterações de formatação feitas NOTA: Este material sofreu ligeiras alterações de formatação feitas 
pelo Prof. Wellington Lima dos Santospelo Prof. Wellington Lima dos Santos
Grafos – Representação e Grafos – Representação e Grafos – Representação e 
Algoritmos ElementaresAlgoritmos ElementaresAlgoritmos Elementares
Representações de GrafosRepresentações de GrafosRepresentações de Grafos
• Na descrição do tempo de execução de • Na descrição do tempo de execução de • Na descrição do tempo de execução de 
uma algoritmo de grafo sobre um uma algoritmo de grafo sobre um 
determinado grafo G = (V, E, f ), determinado grafo G = (V, E, f ), 
normalmente medimos o tamanho da normalmente medimos o tamanho da normalmente medimos o tamanho da 
entrada em termos do:entrada em termos do:entrada em termos do:
– Número de vértices |V|; e do– Número de vértices |V|; e do– Número de vértices |V|; e do
– Número de arestas |E|.– Número de arestas |E|.
Representações de GrafosRepresentações de GrafosRepresentações de Grafos
• Exemplo, poderíamos dizer que “o algoritmo • Exemplo, poderíamos dizer que “o algoritmo • Exemplo, poderíamos dizer que “o algoritmo 
é executado em tempo O(V E )”, é executado em tempo O(V E )”, 
significando que o algoritmo é executado no significando que o algoritmo é executado no 
tempo O(|V | |E|);tempo O(|V | |E|);tempo O(|V | |E|);
Representações de GrafosRepresentações de GrafosRepresentações de Grafos
• Existem duas maneiras básicas para • Existem duas maneiras básicas para • Existem duas maneiras básicas para 
representar um grafo G = (V, E ):representar um grafo G = (V, E ):
– Como uma coleção de listas de adjacências;– Como uma coleção de listas de adjacências;
– Como uma matriz de adjacências.– Como uma matriz de adjacências.
Lista de AdjacênciasLista de AdjacênciasLista de Adjacências
• Em geral, é a preferida;• Em geral, é a preferida;• Em geral, é a preferida;
• Fornece um modo compacto de representar • Fornece um modo compacto de representar • Fornece um modo compacto de representar 
grafos esparsos:grafos esparsos:grafos esparsos:
– |E | é muito menor que |V |2.– |E | é muito menor que |V |2.
• Geralmente, os algoritmos pressupõem que • Geralmente, os algoritmos pressupõem que • Geralmente, os algoritmos pressupõem que 
um grafo de entrada é representado como um grafo de entrada é representado como 
uma lista de adjacências;uma lista de adjacências;uma lista de adjacências;
• Memória exigida: Θ(V + E ).• Memória exigida: Θ(V + E ).
Lista de AdjacênciasLista de AdjacênciasLista de Adjacências
• Esta representação de um grafo G = (V, E )• Esta representação de um grafo G = (V, E )• Esta representação de um grafo G = (V, E )
consiste de um arranjo (vetor) Adj de |V |consiste de um arranjo (vetor) Adj de |V |
listas, uma para cada vértice em V;listas, uma para cada vértice em V;
∈• Para cada u ∈ V, a lista de adjacências • Para cada u ∈ V, a lista de adjacências 
Adj[u] contém (ponteiros) todos os vértices vAdj[u] contém (ponteiros) todos os vértices vAdj[u] contém (ponteiros) todos os vértices v
tais que existe uma aresta (u, v) ∈ E;tais que existe uma aresta (u, v) ∈ E;tais que existe uma aresta (u, v) ∈ E;
• Em geral, os vértices estão armazenados • Em geral, os vértices estão armazenados • Em geral, os vértices estão armazenados 
em uma ordem arbitrária.em uma ordem arbitrária.em uma ordem arbitrária.
Lista de AdjacênciasLista de AdjacênciasLista de Adjacências
• Exemplo de uma lista de adjacências para • Exemplo de uma lista de adjacências para • Exemplo de uma lista de adjacências para 
um grafo G não orientado.um grafo G não orientado.
t u x
ut
t
u t x vut u t x v
v
v u w
v
w v x
x w
w v x
w
x w
x t u w
Grafo não orientado Lista de adjacências do grafoGrafo não orientado Lista de adjacências do grafo
Lista de AdjacênciasLista de AdjacênciasLista de Adjacências
• Se G é um grafo orientado, a soma dos • Se G é um grafo orientado, a soma dos • Se G é um grafo orientado, a soma dos 
comprimentos de todas as listas de comprimentos de todas as listas de 
adjacências é |E|;adjacências é |E|;
• Uma aresta da forma (u, v) é representada • Uma aresta da forma (u, v) é representada 
fazendo-se v aparecer em Adj [u];fazendo-se v aparecer em Adj [u];fazendo-se v aparecer em Adj [u];
• Se G é um grafo não orientado, a soma dos • Se G é um grafo não orientado, a soma dos 
comprimentos de todas as listas de comprimentos de todas as listas de comprimentos de todas as listas de 
adjacências é 2 |E|. Por que?adjacências é 2 |E|. Por que?adjacências é 2 |E|. Por que?
Lista de AdjacênciasLista de AdjacênciasLista de Adjacências
• Exemplo de uma lista de adjacências para • Exemplo de uma lista de adjacências para • Exemplo de uma lista de adjacências para 
um grafo G orientado.um grafo G orientado.
t u w
u vt
t
u
u w
xu vt u x
v x yv
w
x y
u
yw x
w u
yw x
x w
Grafo orientado
x w
y yGrafo orientado y y
Lista de adjacências do grafoLista de adjacências do grafo
Lista de AdjacênciasLista de AdjacênciasLista de Adjacências
• Podem ser adaptadas para representar • Podem ser adaptadas para representar • Podem ser adaptadas para representar 
grafos ponderados:grafos ponderados:
– Grafos nos quais cada aresta tem um peso– Grafos nos quais cada aresta tem um peso
associado a ela, normalmente dado por uma associado a ela, normalmente dado por uma associado a ela, normalmente dado por uma 
função peso w : E → R.função peso w : E → R.
Matriz de AdjacênciasMatriz de AdjacênciasMatriz de Adjacências
• Pode ser preferível quando o grafo é denso:• Pode ser preferível quando o grafo é denso:• Pode ser preferível quando o grafo é denso:
– |E| está próximo de |V|2.– |E| está próximo de |V|2.– |E| está próximo de |V| .
• Ou quando precisamos ter a possibilidade • Ou quando precisamos ter a possibilidade • Ou quando precisamos ter a possibilidade 
de saber com rapidez se existe uma aresta de saber com rapidez se existe uma aresta 
conectando dois vértices dados:conectando dois vértices dados:
– Exemplo: caminhos mais curtos de todos os – Exemplo: caminhos mais curtos de todos os 
pares.pares.pares.
Matriz de AdjacênciasMatriz de AdjacênciasMatriz de Adjacências
• Na representação de um grafo G = (V, E), supomos • Na representação de um grafo G = (V, E), supomos 
que os vértices são numerados 1, 2, ..., |V | de alguma que os vértices são numerados 1, 2, ..., |V | de alguma que os vértices são numerados 1, 2, ..., |V | de alguma 
maneira arbitrária;maneira arbitrária;
• A representação de um grafo G consiste em uma • A representação de um grafo G consiste em uma 
matriz A = (a ) tal que:matriz A|V | x |V | = (aij) tal que:|V | x |V | ij
1, se ( , ) ,i j E
a

 
1, se ( , ) ,
0, casocontrário.
ij
i j E
a

 
0, casocontrário.
ija  

Matriz de AdjacênciasMatriz de AdjacênciasMatriz de Adjacências
• Exemplo de uma matriz de adjacências para um • Exemplo de uma matriz de adjacências para um 
grafo G não orientado.grafo G não orientado.grafo G não orientado.
t u v x wt u v x w
t 0 1 0 1 0ut t 0 1 0 1 0ut
u 1 0 1 1 0
v
u 1 0 1 1 0
v 0 1 0 0 1
v
v 0 1 0 0 1
x w
x 1 1 0 0 1
x w
w 0 0 1 1 0
Grafo não orientado
w 0 0 1 1 0
Matriz de adjacências
Grafo não orientado
Matriz de adjacências
Matriz de AdjacênciasMatriz de AdjacênciasMatriz de Adjacências
• Exemplo de uma matriz de adjacências paraum • Exemplo de uma matriz de adjacências para um 
grafo orientado G.grafo orientado G.
t u v w x yt u v w x y
t 0 1 0 1 0 0u vt t 0 1 0 1 0 0u vt
u 0 0 0 0 1 0u 0 0 0 0 1 0
v 0 0 0 0 1 1v 0 0 0 0 1 1
w 0 1 0 0 0 0w 0 1 0 0 0 0yw x
x 0 0 0 1 0 0
Grafo orientado
x 0 0 0 1 0 0
y 0 0 0 0 0 1Grafo orientado y 0 0 0 0 0 1
Matriz de adjacênciasMatriz de adjacências
Matriz de AdjacênciasMatriz de AdjacênciasMatriz de Adjacências
• Exige a memória (|V |2), independente do • Exige a memória (|V |2), independente do 
número de arestas do grafo;número de arestas do grafo;número de arestas do grafo;
• Em um grafo não orientado, (u, v) e (v, u)• Em um grafo não orientado, (u, v) e (v, u)• Em um grafo não orientado, (u, v) e (v, u)
representam a mesma aresta;representam a mesma aresta;representam a mesma aresta;
• Portanto, a matriz de adjacências A de um • Portanto, a matriz de adjacências A de um • Portanto, a matriz de adjacências A de um 
grafo não orientado G é sua própria grafo não orientado G é sua própria 
transposta: A = AT;transposta: A = AT;transposta: A = A ;
– Em algumas aplicações, compensa mostrar – Em algumas aplicações, compensa mostrar 
apenas as entradas da diagonal principal e apenas as entradas da diagonal principal e apenas as entradas da diagonal principal e 
acima da diagonal.acima da diagonal.
Matriz de AdjacênciasMatriz de AdjacênciasMatriz de Adjacências
• Também pode ser usada em grafos • Também pode ser usada em grafos • Também pode ser usada em grafos 
ponderados;ponderados;
• Preferível quando os grafos são • Preferível quando os grafos são • Preferível quando os grafos são 
razoavelmente pequenos.razoavelmente pequenos.
Busca em LarguraBusca em LarguraBusca em Largura
Busca em Largura (BFS)Busca em Largura (BFS)Busca em Largura (BFS)Busca em Largura (BFS)
Breadth-First SearchBreadth-First Search
• Usa vetor de listas de adjacências;• Usa vetor de listas de adjacências;• Usa vetor de listas de adjacências;
• |V |: número de vértices em G;• |V |: número de vértices em G;• |V |: número de vértices em G;
• |E |: número de arestas em G;• |E |: número de arestas em G;• |E |: número de arestas em G;
• No algoritmo, utilizamos uma fila (FIFO):• No algoritmo, utilizamos uma fila (FIFO):• No algoritmo, utilizamos uma fila (FIFO):
– Precisamos implementar a fila:– Precisamos implementar a fila:– Precisamos implementar a fila:
• Inicializar;• Inicializar;• Inicializar;
• Finalizar;• Finalizar;
• Fila vazia?;• Fila vazia?;• Fila vazia?;
• Enfileirar e Desenfileirar.• Enfileirar e Desenfileirar.
Busca em LarguraBusca em LarguraBusca em Largura
• É um dos algoritmos mais simples para • É um dos algoritmos mais simples para • É um dos algoritmos mais simples para 
pesquisar um grafo e é base para muitos pesquisar um grafo e é base para muitos 
algoritmos de grafos importantes;algoritmos de grafos importantes;
• Exemplos:• Exemplos:
– Algoritmo de Dijkstra (caminho mínimo de – Algoritmo de Dijkstra (caminho mínimo de 
origem mais curta);origem mais curta);origem mais curta);
– Algoritmo de Prim (árvore espalhada mínima).– Algoritmo de Prim (árvore espalhada mínima).– Algoritmo de Prim (árvore espalhada mínima).
Busca em LarguraBusca em LarguraBusca em Largura
• Dado um grafo G = (V, E) e um vértice de • Dado um grafo G = (V, E) e um vértice de • Dado um grafo G = (V, E) e um vértice de 
origem distinta, s, a busca em largura origem distinta, s, a busca em largura 
explora sistematicamente as arestas de Gexplora sistematicamente as arestas de G
até “descobrir” cada vértice acessível a até “descobrir” cada vértice acessível a até “descobrir” cada vértice acessível a 
partir de s;partir de s;partir de s;
• O algoritmo calcula a distância (menor • O algoritmo calcula a distância (menor • O algoritmo calcula a distância (menor 
número de arestas) desde s até todos os número de arestas) desde s até todos os número de arestas) desde s até todos os 
vértices acessíveis desse tipo.vértices acessíveis desse tipo.
Busca em LarguraBusca em LarguraBusca em Largura
• Produz uma árvore “primeiro na extensão”;• Produz uma árvore “primeiro na extensão”;
• Esta árvore, com raiz s, contém todos os • Esta árvore, com raiz s, contém todos os 
vértices acessíveis;vértices acessíveis;vértices acessíveis;
• Para qualquer vértice v acessível a partir de • Para qualquer vértice v acessível a partir de • Para qualquer vértice v acessível a partir de 
s, o caminho na árvore de s até vs, o caminho na árvore de s até vs, o caminho na árvore de s até v
corresponde a um “caminho mais curto” de corresponde a um “caminho mais curto” de 
s até v em G;s até v em G;s até v em G;
• Um caminho que contém o número mínimo • Um caminho que contém o número mínimo • Um caminho que contém o número mínimo 
de arestas.de arestas.
Busca em LarguraBusca em LarguraBusca em Largura
• O algoritmo descobre todos os vértices à • O algoritmo descobre todos os vértices à • O algoritmo descobre todos os vértices à 
distância k a partir de s, antes de descobrir distância k a partir de s, antes de descobrir 
quaisquer vértices à distância k+1;quaisquer vértices à distância k+1;
• O algoritmo pinta cada vértice de branco, • O algoritmo pinta cada vértice de branco, 
cinza ou preto;cinza ou preto;cinza ou preto;
• Inicialmente, todos os vértices são brancos • Inicialmente, todos os vértices são brancos 
e mais tarde podem tornar-se cinzas ou e mais tarde podem tornar-se cinzas ou e mais tarde podem tornar-se cinzas ou 
pretos.pretos.pretos.
Busca em LarguraBusca em LarguraBusca em Largura
• Um vértice é descoberto na primeira vez em • Um vértice é descoberto na primeira vez em • Um vértice é descoberto na primeira vez em 
que é encontrado durante a busca;que é encontrado durante a busca;
• Nesse momento se torna não branco;• Nesse momento se torna não branco;• Nesse momento se torna não branco;
• Se (u, v) ∈ E e o vértice u é preto, o vértice • Se (u, v) ∈ E e o vértice u é preto, o vértice • Se (u, v) ∈ E e o vértice u é preto, o vértice 
v é cinza ou preto;v é cinza ou preto;
• Vértices de cor cinza ainda podem ter • Vértices de cor cinza ainda podem ter • Vértices de cor cinza ainda podem ter 
vértices adjacentes brancos.vértices adjacentes brancos.
Busca em LarguraBusca em LarguraBusca em Largura
• O algoritmo a seguir pressupõe que o grafo • O algoritmo a seguir pressupõe que o grafo • O algoritmo a seguir pressupõe que o grafo 
G = (V, E) é representado como lista de G = (V, E) é representado como lista de 
adjacências;adjacências;
• Mantém várias estruturas de dados • Mantém várias estruturas de dados 
adicionais com cada vértice no grafo;adicionais com cada vértice no grafo;adicionais com cada vértice no grafo;
∈• A cor de cada vértice u ∈ V é armazenada • A cor de cada vértice u ∈ V é armazenada 
na variável u.cor e o predecessor de u é na variável u.cor e o predecessor de u é na variável u.cor e o predecessor de u é 
armazenado em u.p.armazenado em u.p.armazenado em u.p.
Busca em LarguraBusca em LarguraBusca em Largura
• Se u ainda não possui predecessor, u.p = • Se u ainda não possui predecessor, u.p = • Se u ainda não possui predecessor, u.p = 
nulo;nulo;
• A distância desde a origem s até o vértice u• A distância desde a origem s até o vértice u• A distância desde a origem s até o vértice u
é armazenada em u.d;é armazenada em u.d;
• O algoritmo também utiliza uma fila Q• O algoritmo também utiliza uma fila Q
(FIFO) para gerenciar o conjunto de vértices (FIFO) para gerenciar o conjunto de vértices 
de cor cinza.de cor cinza.de cor cinza.
Busca em LarguraBusca em LarguraBusca em Largura
procedimento BFS(G: Grafo, s: Vértice)procedimento BFS(G: Grafo, s: Vértice)
declaredeclare
Q: FilaQ: Fila
u, v: Vertice
∈
u, v: Vertice
início
∈
início
para cada u ∈ V(G)–{s}façapara cada u ∈ V(G)–{s} faça
u.cor ← “Branco”
∈
u.cor ← “Branco”
u.d ← ∞
∈
u.d ← ∞u.d ← ∞
u.p ← nullu.p ← null
fimparafimpara
s.cor ← “Cinza”s.cor ← “Cinza”
s.d ← 0s.d ← 0
s.p ← nulls.p ← null
InicializaFila(Q)InicializaFila(Q)
Enfileira(Q, s)Enfileira(Q, s)
Busca em LarguraBusca em LarguraBusca em Largura
enquanto FilaVazia(Q) = falso faça
∈
enquanto FilaVazia(Q) = falso faça
∈
u ← Desenfileira(Q)
∈
u ← Desenfileira(Q)
para cada v ∈ Adj[u] façapara cada v ∈ Adj[u] faça
se v.cor = “Branco” então
∈
se v.cor = “Branco” então
v.cor ← “Cinza” 
∈
v.cor ← “Cinza” 
v.d ← u.d + 1 v.d ← u.d + 1 v.d ← u.d + 1 
v.p ← uv.p ← u
Enfileira(Q, v)Enfileira(Q, v)
fimsefimse
fimparafimpara
u.cor ← “Preto”u.cor ← “Preto”
fimenquantofimenquanto
FinalizaFila(Q)FinalizaFila(Q)
fimfim
Busca em LarguraBusca em LarguraBusca em Largura
r s t ur s t u
v w x y
GGG
Busca em LarguraBusca em LarguraBusca em Largura
r s t ur s t u
∞ ∞ ∞0∞ ∞ ∞0
QQ sQ
0
∞ ∞ ∞ ∞
0
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
01
r s t u
∞ ∞01 ∞ ∞
QQ w rQ
1 1
1∞ ∞ ∞
1 1
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
201
r s t u
∞201 ∞
QQ r t xQ
1 2 2
21∞ ∞
1 2 2
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
1 20
r s t u
∞1 20 ∞
QQ t x vQ
2 2 2
2 21 ∞
2 2 2
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
2 31 0
r s t u
2 31 0
QQ x v uQ
2 2 3
2 21 ∞
2 2 3
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
2 31 0
r s t u
2 31 0
QQ v u yQ
2 3 3
322 1
2 3 3
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
2 31 0
r s t u
2 31 0
QQ u yQ
3 3
2 321
3 3
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
321 0
r s t u
321 0
QQ yQ
3
2 321
3
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
r s t u
321 0
r s t u
321 0
Q ∅Q ∅Q ∅
32 21
v w x y
G
x y
GG
Busca em LarguraBusca em LarguraBusca em Largura
• Qual a complexidade da busca em largura • Qual a complexidade da busca em largura • Qual a complexidade da busca em largura 
em um grafo G = (V, E)?em um grafo G = (V, E)?
– Cada vértice é colocado na fila no máximo uma – Cada vértice é colocado na fila no máximo uma 
vez;vez;vez;
– Cada vértice é retirado da fila no máximo uma – Cada vértice é retirado da fila no máximo uma – Cada vértice é retirado da fila no máximo uma 
vez;vez;
– Enfileirar e desenfileirar gasta O(1). Portanto, o – Enfileirar e desenfileirar gasta O(1). Portanto, o 
total de operações em fila é O(V ).total de operações em fila é O(V ).total de operações em fila é O(V ).
Busca em LarguraBusca em LarguraBusca em Largura
• Qual a complexidade da busca em largura • Qual a complexidade da busca em largura • Qual a complexidade da busca em largura 
em um grafo G = (V, E )?em um grafo G = (V, E )?
– A lista de adjacências de cada vértice é – A lista de adjacências de cada vértice é 
examinada somente quando o vértice é examinada somente quando o vértice é examinada somente quando o vértice é 
desenfileirado;desenfileirado;
– Tal lista é examinada somente uma vez;– Tal lista é examinada somente uma vez;
– Portanto, é gasto o tempo O(E);– Portanto, é gasto o tempo O(E);
– Desse modo, o tempo de execução do – Desse modo, o tempo de execução do 
algoritmo BFS é O(V + E).algoritmo BFS é O(V + E).algoritmo BFS é O(V + E).
Busca em LarguraBusca em LarguraBusca em Largura
• O procedimento a seguir imprime os • O procedimento a seguir imprime os • O procedimento a seguir imprime os 
vértices em um caminho mais curto desde svértices em um caminho mais curto desde s
até v, supondo-se que BFS já foi executado até v, supondo-se que BFS já foi executado 
para calcular a árvore do caminho mais para calcular a árvore do caminho mais para calcular a árvore do caminho mais 
curto;curto;curto;
• É executado em tempo linear no número de • É executado em tempo linear no número de • É executado em tempo linear no número de 
vértices no caminho impresso.vértices no caminho impresso.vértices no caminho impresso.
Busca em LarguraBusca em LarguraBusca em Largura
• Algoritmo• Algoritmo• Algoritmo
procedimento imprimeCaminho(G: Grafo; s, v: Vértice)procedimento imprimeCaminho(G: Grafo; s, v: Vértice)
inícioinício
se (v = s) entãose (v = s) então
imprime s;imprime s;
senãosenão
se (v.p = Ø) entãose (v.p = Ø) então
imprime “Nenhum caminho de ‘s’ para ‘v’.”imprime “Nenhum caminho de ‘s’ para ‘v’.”
senãosenão
imprimeCaminho(G, s, v.p);imprimeCaminho(G, s, v.p);imprimeCaminho(G, s, v.p);
imprime vimprime v
fim_sefim_se
fim_sefim_se
fimfim
Busca em Profundidade (DFS)Busca em Profundidade (DFS)Busca em Profundidade (DFS)
Depth-First Search Depth-First Search Depth-First Search 
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• A estratégia da busca em profundidade, como o • A estratégia da busca em profundidade, como o 
próprio nome sugere, é procurar mais “fundo” no próprio nome sugere, é procurar mais “fundo” no 
grafo, sempre que possível;grafo, sempre que possível;grafo, sempre que possível;
• As arestas são exploradas a partir do vértice v• As arestas são exploradas a partir do vértice v
mais recentemente descoberto, que ainda possui mais recentemente descoberto, que ainda possui 
arestas inexploradas saindo dele;arestas inexploradas saindo dele;arestas inexploradas saindo dele;
• A busca volta para explorar arestas que deixam o • A busca volta para explorar arestas que deixam o 
vértice a partir do qual v foi descoberto.vértice a partir do qual v foi descoberto.vértice a partir do qual v foi descoberto.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• A busca em profundidade é executada até • A busca em profundidade é executada até 
descobrirmos todos os vértices acessíveis a partir descobrirmos todos os vértices acessíveis a partir 
do vértice de origem inicial;do vértice de origem inicial;do vértice de origem inicial;
• Se existe algum vértice não descoberto, este será • Se existe algum vértice não descoberto, este será 
selecionado como nova origem;selecionado como nova origem;selecionado como nova origem;
• E a busca se repetirá a partir desta nova origem.• E a busca se repetirá a partir desta nova origem.• E a busca se repetirá a partir desta nova origem.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• Sempre que um vértice v é descoberto • Sempre que um vértice v é descoberto • Sempre que um vértice v é descoberto 
durante a varredura em uma lista de durante a varredura em uma lista de 
adjacências de um vértice u, registra-se que adjacências de um vértice u, registra-se que 
o predecessor de v é u;o predecessor de v é u;o predecessor de v é u;
• A busca em profundidade (floresta), assim • A busca em profundidade (floresta), assim • A busca em profundidade (floresta), assim 
como a busca em largura (árvore), também como a busca em largura (árvore), também como a busca em largura (árvore), também 
cria um subgrafo predecessor.cria um subgrafo predecessor.cria um subgrafo predecessor.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• O subgrafo predecessor de uma busca em • O subgrafo predecessor de uma busca em 
profundidade é definido de forma ligeiramente profundidade é definido de forma ligeiramente 
diferente daquela de uma busca em largura:diferente daquela de uma busca em largura:diferente daquela de uma busca em largura:
– Fazemos G = (V, E ), onde– Fazemos Gp = (V,Ep), onde
– E = { (v.p, v): v ∈ V e v.p ≠ }.– Ep = { (v.p, v): v ∈ V e v.p ≠ Ø }.– Ep = { (v.p, v): v ∈ V e v.p ≠ Ø }.
– O subgrafo predecessor da busca em profundidade – O subgrafo predecessor da busca em profundidade 
forma uma floresta primeiro na profundidade composta forma uma floresta primeiro na profundidade composta forma uma floresta primeiro na profundidade composta 
por várias árvores primeiro na profundidade.por várias árvores primeiro na profundidade.
– As arestas em E são chamadas de arestas da árvore.– As arestas em Ep são chamadas de arestas da árvore.– As arestas em Ep são chamadas de arestas da árvore.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• Os vértices também são coloridos durante a • Os vértices também são coloridos durante a 
busca, a fim de indicar seus estados;busca, a fim de indicar seus estados;
• Cada vértice é inicialmente branco, tornando-se • Cada vértice é inicialmente branco, tornando-se • Cada vértice é inicialmente branco, tornando-se 
cinza ao ser descoberto na busca;cinza ao ser descoberto na busca;
• Depois, torna-se preto quando terminado:• Depois, torna-se preto quando terminado:
– Um vértice é terminado quando sua lista de adjacências – Um vértice é terminado quando sua lista de adjacências 
é completamente examinada;é completamente examinada;
– Cada vértice acaba em exatamente uma árvore – Cada vértice acaba em exatamente uma árvore 
primeiro na profundidade, de forma que tais árvores primeiro na profundidade, de forma que tais árvores 
sejam disjuntas.sejam disjuntas.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• Além de criar uma floresta primeiro na • Além de criar uma floresta primeiro na 
profundidade, a busca também identifica cada profundidade, a busca também identifica cada 
vértice com um “carimbo de tempo”vértice com um “carimbo de tempo”vértice com um “carimbo de tempo”
• Cada vértice v tem dois carimbos de tempo:• Cada vértice v tem dois carimbos de tempo:
– v.d registra quando v é descoberto pela primeira vez – v.d registra quando v é descoberto pela primeira vez 
(tornando-se cinza);(tornando-se cinza);
– v.f registra quando a busca termina de examinar a lista – v.f registra quando a busca termina de examinar a lista 
de adjacências de v (tornando-se preto).de adjacências de v (tornando-se preto).
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• O procedimento DFS registra em u.d o momento • O procedimento DFS registra em u.d o momento 
em que descobre o vértice u, e registra na variável em que descobre o vértice u, e registra na variável 
u.f o momento em que termina o vértice u;u.f o momento em que termina o vértice u;u.f o momento em que termina o vértice u;
• Esses carimbos de tempo são valores inteiros • Esses carimbos de tempo são valores inteiros 
entre 1 e 2 |V|, pois há um evento de descoberta entre 1 e 2 |V|, pois há um evento de descoberta entre 1 e 2 |V|, pois há um evento de descoberta 
e um evento de término para cada um dos |V|e um evento de término para cada um dos |V|
vértices;vértices;vértices;
– Para todo vértice u, u.d < u.f.– Para todo vértice u, u.d < u.f.– Para todo vértice u, u.d < u.f.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• O vértice u é branco antes do tempo u.d, • O vértice u é branco antes do tempo u.d, • O vértice u é branco antes do tempo u.d, 
cinza entre u.d e u.f e preto depois de u.f;cinza entre u.d e u.f e preto depois de u.f;
• O algoritmo apresentado é básico;• O algoritmo apresentado é básico;• O algoritmo apresentado é básico;
• O grafo de entrada G pode ser orientado ou • O grafo de entrada G pode ser orientado ou • O grafo de entrada G pode ser orientado ou 
não orientado;não orientado;
• A variável tempo é uma variável global que • A variável tempo é uma variável global que • A variável tempo é uma variável global que 
utilizamos para definir carimbos de tempo.utilizamos para definir carimbos de tempo.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
procedimento DFS(G: Grafo)procedimento DFS(G: Grafo)procedimento DFS(G: Grafo)
declaredeclare
u: Vértice;
∈
u: Vértice;
início
∈
início
para cada u ∈ V[G] façapara cada u ∈ V[G] façapara cada u ∈ V[G] faça
u.cor ← “Branco” 
∈
u.cor ← “Branco” 
u.p ← Ø
∈
u.p ← Ø
fim_para
∈
fim_para
tempo ← 0
∈
tempo ← 0
∈para cada u ∈ V[G] façapara cada u ∈ V[G] faça
se u.cor = “Branco” então
∈
se u.cor = “Branco” então
DFS_Visit(u)
∈
DFS_Visit(u)
fim_sefim_se
fim_parafim_parafim_para
fimfim
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
procedimento DFS_Visit(u: Vértice)procedimento DFS_Visit(u: Vértice)
declaredeclare
v: Vértice;v: Vértice;
inícioinícioinício
u.cor ← “Cinza”u.cor ← “Cinza”
tempo ← tempo + 1
∈
tempo ← tempo + 1
u.d ← tempo 
∈
u.d ← tempo 
para cada v ∈ Adj[u] faça //Explora (u, v)para cada v ∈ Adj[u] faça //Explora (u, v)
se v.cor = “Branco” então
∈
se v.cor = “Branco” então
∈
se v.cor = “Branco” então
v.p ← u //faz u ser predecessor de v
∈
v.p ← u //faz u ser predecessor de v
DFS_Visit(v)DFS_Visit(v)
fim_sefim_se
fim_parafim_parafim_para
u.cor ← “Preto”u.cor ← “Preto”
tempo ← tempo + 1tempo ← tempo + 1
u.f ← tempou.f ← tempo
fimfim
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
x y z Gx y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/1/
x y z Gx y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/1/ 2/
x y z Gx y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/1/ 2/
3/
x y z G
3/
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/1/ 2/
3/4/
x y z G
3/4/
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/1/ 2/
BB
3/4/
x y z G
3/4/
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/1/ 2/
BB
3/4/5
x y z G
3/4/5
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/1/ 2/
BB
3/64/5
x y z G
3/64/5
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/71/ 2/7
BB
3/64/5
x y z G
3/64/5
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/ 2/71/ 2/7
BF BF
3/64/5
x y z G
3/64/5
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/8 2/71/8 2/7
BF BF
3/64/5
x y z G
3/64/5
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/8 2/7 9/1/8 2/7 9/
BF BF
3/64/5
x y z G
3/64/5
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/8 2/7 9/1/8 2/7 9/
BF CBF C
3/64/5
x y z G
3/64/5
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/8 2/7 9/1/8 2/7 9/
BF CBF C
3/64/5 10/
x y z G
3/64/5 10/
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/8 2/7 9/1/8 2/7 9/
BF CBF C
3/64/5 10/ B
x y z G
3/64/5 10/
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/8 2/7 9/1/8 2/7 9/
BF CBF C
3/64/5 10/11 B
x y z G
3/64/5 10/11
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
u v wu v w
1/8 2/7 9/121/8 2/7 9/12
BF CBF C
3/64/5 10/11 B
x y z G
3/64/5 10/11
x y z G
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• À medida que as arestas são exploradas • À medida que as arestas são exploradaspelo algoritmo, elas são mostradas como pelo algoritmo, elas são mostradas como pelo algoritmo, elas são mostradas como 
sombreadas ou tracejadas;sombreadas ou tracejadas;sombreadas ou tracejadas;
• Arestas sombreadas são arestas de • Arestas sombreadas são arestas de • Arestas sombreadas são arestas de 
árvores;árvores;
• Arestas tracejadas não são arestas de • Arestas tracejadas não são arestas de 
árvores. Estas, são identificadas como B, Cárvores. Estas, são identificadas como B, Cárvores. Estas, são identificadas como B, C
ou F, se são de retorno, cruzadas ou para ou F, se são de retorno, cruzadas ou para 
frente.frente.frente.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• Qual é o tempo de execução do DFS?• Qual é o tempo de execução do DFS?• Qual é o tempo de execução do DFS?
– O DFS demora o tempo Θ(V), fora o tempo – O DFS demora o tempo Θ(V), fora o tempo – O DFS demora o tempo Θ(V), fora o tempo 
para chamar DFS_Visit;para chamar DFS_Visit;
– O procedimento DFS_Visit é chamado – O procedimento DFS_Visit é chamado – O procedimento DFS_Visit é chamado 
exatamente uma vez para cada vértice u ∈ V, exatamente uma vez para cada vértice u ∈ V, ∈
pois é chamado somente para vértices brancos;pois é chamado somente para vértices brancos;
– Dentro do DFS_Visit, o laço é executado – Dentro do DFS_Visit, o laço é executado – Dentro do DFS_Visit, o laço é executado 
| Adj [u] | vezes.| Adj [u] | vezes.
Busca em ProfundidadeBusca em ProfundidadeBusca em Profundidade
• Qual é o tempo de execução do DFS?• Qual é o tempo de execução do DFS?• Qual é o tempo de execução do DFS?
– Tendo em vista que o somatório de |Adj [u] |, – Tendo em vista que o somatório de |Adj [u] |, 
∈
– Tendo em vista que o somatório de |Adj [u] |, 
para todo u ∈ V é Θ(E), temos que:para todo u ∈ V é Θ(E), temos que:
• O tempo de execução do DFS é Θ(V + E ).• O tempo de execução do DFS é Θ(V + E ).• O tempo de execução do DFS é Θ(V + E ).
Ordenação TopológicaOrdenação TopológicaOrdenação Topológica
Ordenação TopológicaOrdenação TopológicaOrdenação Topológica
• Grafos orientados acíclicos (GAO);• Grafos orientados acíclicos (GAO);• Grafos orientados acíclicos (GAO);
• Ordenação Topológica:• Ordenação Topológica:• Ordenação Topológica:
– É uma ordenação linear de todos os seus – É uma ordenação linear de todos os seus – É uma ordenação linear de todos os seus 
vértices, tal que, se G contem uma aresta (u, v), vértices, tal que, se G contem uma aresta (u, v), 
então u aparece antes de v na ordenação;então u aparece antes de v na ordenação;então u aparece antes de v na ordenação;
– É uma ordenação dos vértices ao longo de uma – É uma ordenação dos vértices ao longo de uma – É uma ordenação dos vértices ao longo de uma 
linha horizontal;linha horizontal;
– Útil para representar precedência de eventos.– Útil para representar precedência de eventos.
Ordenação TopológicaOrdenação TopológicaOrdenação Topológica
cuecascuecas
meiasmeias
relógiorelógio
calças sapatoscalças
camisacamisa
cinto gravatacinto gravata
paletópaletó
Ordenação TopológicaOrdenação TopológicaOrdenação Topológica
11/16
cuecas
11/16
cuecas
meias 17/18 9/10meias 17/18 9/10
relógiorelógio
12/15
calças sapatos
12/15
13/14calças
camisa 1/8camisa 1/8
6/7
cinto gravata
6/7
2/5cinto gravata 2/5
paletó 3/4 Com campos numerados de paletó 3/4 Com campos numerados de 
acordo com o DFSacordo com o DFS
Ordenação TopológicaOrdenação TopológicaOrdenação Topológica
cuecas calças cintocamisameias sapatos relógiocuecas calças cintocamisameias sapatos relógio
11/16 12/15 6/71/813/1417/18 9/1011/16 12/15 6/71/813/1417/18 9/10
gravata2/5 gravata2/5
paletó3/4Vértices organizados da paletó3/4Vértices organizados da Vértices organizados da 
esquerda para a direita.esquerda para a direita.
Ordenação TopológicaOrdenação TopológicaOrdenação Topológica
• Algoritmo (modificado por SANTOS, W.L)• Algoritmo (modificado por SANTOS, W.L)• Algoritmo (modificado por SANTOS, W.L)
procedimento topological_Sort(G)procedimento topological_Sort(G)procedimento topological_Sort(G)
inicioinicio
– Execute DFS(G) – Execute DFS(G) 
•Ao terminar cada vértice v (calcular •Ao terminar cada vértice v (calcular 
v.f), inserí-lo numa pilha P.v.f), inserí-lo numa pilha P.
– Desempilhe os vértices de P, – Desempilhe os vértices de P, 
devidamente ordenadosdevidamente ordenadosdevidamente ordenados
fimfim
Ordenação TopológicaOrdenação TopológicaOrdenação Topológica
• Complexidade:• Complexidade:• Complexidade:
– Busca em profundidade gasta Θ(V + E);– Busca em profundidade gasta Θ(V + E);– Busca em profundidade gasta Θ(V + E);
– Inserir cada um dos |V | vértices na lista ligada – Inserir cada um dos |V | vértices na lista ligada 
gasta O(1);gasta O(1);gasta O(1);
– Portanto, a ordenação topológica gasta– Portanto, a ordenação topológica gasta– Portanto, a ordenação topológica gasta
Θ(V + E).Θ(V + E).
• Certidão sucinta da aciclicidade do grafo G.• Certidão sucinta da aciclicidade do grafo G.