Algoritmos em Grafos
Cauê Nascimento
Geane
Busca em Largura
• Expande a fronteira entre vértices descobertos
e não descobertos uniformemente através da
largura da fronteira.
• O algoritmo descobre todos os vértices a uma
distância k do vértice origem antes de
descobrir qualquer vértice a uma distância k +
1.
• O grafo G(V, A) pode ser direcionado ou não
direcionado.
Algoritmos em Grafos 2
Busca em Largura
• Cada vértice é colorido de branco, cinza
ou preto.
• Todos os vértices são inicializados
branco.
• Quando um vértice é descoberto pela
primeira vez ele torna-se cinza
Algoritmos em Grafos 3
Busca em Largura
• Vértices cinza e preto já foram descobertos,
mas são distinguidos para assegurar que a
busca ocorra em largura.
• Se (u, v) ∈ A e o vértice u é preto, então o
vértice v tem que ser cinza ou preto.
• Vértices cinza podem ter alguns vértices
adjacentes brancos, e eles representam a
fronteira entre vértices descobertos e não
descobertos.
Algoritmos em Grafos 4
Busca em Largura -Implementação
−−Entram aqui os operadores FFVazia, Vazia, Enfileira e Desenfileira do−−}
{−−TAD Filas com arranjos ou apontadores, dependendo da implementação−−}
{−−da busca em largura usar arranjos ou apontadores, respectivamente−−}
procedure BuscaEmLargura (var Grafo: TipoGrafo);
var x : TipoValorVertice;
Dist : array[TipoValorVertice ] of integer;
Cor : array[TipoValorVertice ] of TipoCor;
Antecessor : array[TipoValorVertice ] of integer;
{−−−Entra aqui o procedimento VisitaBfs (a seguir)−−−}
begin
for x := 0 to [Link]−1do
begin
Cor[x] := branco; Dist [x] := infinito ; Antecessor[x] := −1;
end;
for x := 0 to [Link]−1do if Cor[x] = branco then VisitaBfs (x);
end; { BuscaEmLargura }
Algoritmos em Grafos 5
Busca em Largura - Exemplo
Algoritmos em Grafos 6
Busca em Largura - Análise (para
listas de adjacência)
• O custo de inicialização do primeiro anel em BuscaEmLargura é
O(|V |) cada um.
• O custo do segundo anel é também O(|V |).
• Visita Bfs: enfileirar e desenfileirar têm custo O(1), logo, o custo
total com a fila é O(|V |).
• Cada lista de adjacentes é percorrida no máximo uma vez,
quando o vértice é desenfileirado.
• Desde que a soma de todas as listas de adjacentes é O(|A|), o
tempo total gasto com as listas de adjacentes é O(|A|).
• Complexidade total: é O(|V | + |A|).
Algoritmos em Grafos 7
Caminhos Mais Curtos
• A busca em largura obtém o caminho mais
curto de u até v.
• O procedimento VisitaBfs contrói uma árvore
de busca em largura que é armazenada na
variável Antecessor.
• O programa abaixo imprime os vértices do
caminho mais curto entre o vértice origem e
outro vértice qualquer do grafo, a partir do
vetor Antecessor obtido na busca em largura.
Algoritmos em Grafos 8
procedure ImprimeCaminho (Origem, v : TipovalorVertice );
begin
if Origem = v
then write(Origem:3)
else if Antecessor[v] = −1
then write( ’Nao existe caminho de’ ,Origem:3 , ’ ate ’ ,v:3)
else begin
Imprimecaminho(Origem, Antecessor[v ]);
write(v:3);
end;
end; { ImprimeCaminho }
Algoritmos em Grafos 9
Busca em Profundidade
• A busca em profundidade, do inglês depth-first search), é um
algoritmo para caminhar no grafo
• A estratégia é buscar o mais profundo no grafo sempre que
possível
• As arestas são exploradas a partir do vértice v mais recentemente
descoberto que ainda possui arestas não exploradas saindo dele.
• Quando todas as arestas adjacentes a v tiverem sido exploradas a
busca anda para trás para explorar vértices que saem do vértice
do qual v foi descoberto
• O algoritmo é a base para muitos outros algoritmos importantes,
tais como verificação de grafos acíclicos, ordenação topológica e
componentes fortemente conectados.
Algoritmos em Grafos 10
Busca em Profundidade
• Para acompanhar o progresso do algoritmo cada
vértice é colorido de branco, cinza ou preto.
• Todos os vértices são inicializados branco.
• Quando um vértice é descoberto pela primeira vez ele
torna-se cinza, e é tornado preto quando sua lista de
adjacentes tenha sido completamente examinada.
• d[v]: tempo de descoberta
• t[v]: tempo de término do exame da lista de
adjacentes de v.
• Estes registros são inteiros entre 1 e 2|V | pois existe
um evento de descoberta e um evento de término para
cada um dos |V | vértices.
Algoritmos em Grafos 11
Busca em Profundidade -
Implementação
procedure BuscaEmProfundidade (var Grafo: TipoGrafo);
var Tempo : TipoValorTempo;
x : TipoValorVertice;
d, t : array[TipoValorVertice ] of TipoValorTempo;
Cor : array[TipoValorVertice ] of TipoCor;
Antecessor : array[TipoValorVertice ] of integer;
{−−−Entra aqui o procedimento VisitaDFS (a seguir)−−−}
begin
Tempo := 0;
for x := 0 to [Link]−1do
begin Cor[x] := branco; Antecessor[x] := −1; end;
for x := 0 to [Link]−1do
if Cor[x] = branco then VisitaDfs (x);
end; { BuscaEmProfundidade }
Algoritmos em Grafos 12
Busca em Profundidade - Exemplo
Algoritmos em Grafos 13
Busca em Profundidade - Análise
• Os dois anéis da BuscaEmProfundidade têm custo O(|V |) cada
um, a menos da chamada do procedimento VisitaDfs(u) no
segundo anel.
• O procedimento VisitaDfs é chamado exatamente uma vez para
cada vértice u ∈ V , desde que VisitaDfs é chamado apenas para
vértices brancos e a primeira ação é pintar o vértice de cinza.
• Durante a execução de VisitaDfs(u) o anel principal é executado
|Adj[u]| vezes.
• Desde que P u∈V |Adj[u]| = O(|A|), o tempo total de execução
de VisitaDfs é O(|A|).
• Logo, a complexidade total da BuscaEmProfundidade é O(|V | +
|A|).
Algoritmos em Grafos 14