u
n
e
s
p
Estruturas de Dados
(Grafos)
Ronaldo Celso Messias Correia
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Busca em Grafos
 Dado um grafo G = (V, A) e um vértice v
pertencente a V, deseja-se encontrar todos os
vértices em G que estão conectados a v.
 Ou, dado um grafo G = (V, A), deseja-se visitar
todos os vértices de G.
 Serão vistas duas maneiras de realizar essas
tarefas:


Busca em profundidade, e;
Busca em largura.
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Busca em Profundidade
 A busca em profundidade (depth-first search) é um
algoritmo para caminhar no grafo.
 A estratégia é buscar o vértice 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 (backtrack) 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.
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Versão recursiva do algoritmo
procedimento Busca(G: Grafo)
Para cada vértice v de G:
Marque v como não visitado
Para cada vértice v de G:
Se v não foi visitado:
Busca-Prof(v)
procedimento Busca-Prof(v: vértice)
Marque v como visitado
Para cada vértice w adjacente a v:
Se w não foi visitado:
Busca-Prof(w)
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Versão recursiva do algoritmo
/* Supondo que os FLAGs dos vertices sejam
todos iguais a 0 */
void busca_profund(heads *G,int i)
{
no *aux;
G[i].FLAG = 1;
for (aux=G[i].ADJ;aux;aux = aux->NEXT)
if (G[aux->VERTEX].FLAG == 0)
busca_profund(G,aux->VERTEX)
}
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Execução do algoritmo
1
3
2
4
7
6
8
Busca-Prof(1)
5
Busca-Prof(2)
Busca-Prof(4)
Busca-Prof(5)
Busca-Prof(3)
Busca-Prof(6)
Busca-Prof(7)
Busca-Prof(8)
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Busca em Largura
 A busca em largura (breadth-first search)
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 um
distância k do vértice origem antes de descobrir
qualquer vértice a uma distância k+1.
 O grafo pode ser direcionado ou não
direcionado
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Algoritmo de busca em Largura
procedimento Busca-Largura(v: vértice)
Inicializar F
Marcar v como visitado
Inserir v no final de F
Enquanto F não vazio:
u := primeiro elemento de F
Retirar u de F
Para cada vértice w adjacente a u:
Se w não foi visitado:
Marcar w como visitado
Colocar w no final de F
procedimento Busca(G: Grafo)
Para cada vértice v de G:
Marcar v como não visitado
Para cada vértice v de G:
Se v não foi visitado:
Busca-Largura(v)
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Algoritmo de busca em Largura
/* Suponha Q uma fila de numeros inteiros e
os FLAGs dos
vertices sejam todos iguais a 0 */void
Busca_Largura(heads *G)
{int i;
no *aux;
G[0].FLAG = 1;
INSERE(Q,0);
while (EMPTY(Q) != 1)
{
i = REMOVE(Q); /* Retira um elemento da fila */
for (aux = G[i].ADJ; aux; aux = aux->NEXT)
{
if (G[aux->VERTEX].FLAG == 0)
{
G[aux->VERTEX].FLAG = 1;
INSERE(Q,aux->VERTEX);
}
}
}
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Execução do algoritmo
1
3
2
4
7
6
8
Busca-Larg(1)
5
Busca-Larg(2)
Busca-Larg(3)
Busca-Larg(5)
Busca_Larg(4)
Busca-Larg(6)
Busca-Larg(7)
Busca-Larg(8)
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Teste para verificar se grafo é Acíclico
 A busca em profundidade pode ser usada para
verificar se um grafo é acíclico ou contém um
ou mais ciclos.
 Se uma aresta de retorno é encontrada durante
a busca em profundidade em G, então o grafo
tem ciclo.
 O algoritmo de busca em profundidade pode
ser modificado para detectar ciclos em grafos
orientados simplesmente verificando se um
vértice w adjacente a v possui o FLAG=1 na
primeira vez que a aresta (v, w) é percorrida.
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Caminho mais curto
Quando todas as arestas de grafo G
possuem peso 1, o problema de
encontrar o caminho de menor custo
entre um vértice s e os outros vértices de
G, se resume ao caminho mais curto
entre s e os outros vértices do grafo G,
ou seja, o caminho com o menor número
de arestas
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Caminho mais curto
O caminho mais curto de s até o próprio vértice v3 é 0. Os vértices que
estão a uma distância 1 de s , v1 e v6. Os vértices que estão a uma
distância 2 de s podem ser encontrados através dos vértices adjacentes
aos vértices v1 e v6, cujo caminho mais curto ainda não tenha sido
encontrado. Na figura acima estes vértices são v2 e v4.
Seguindo o procedimento acima, podemos encontrar os vértices que
estão a uma distância 3,4 etc. Note que o esquema acima é muito
parecido com o método de busca em largura.
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Algoritmo de caminho mais curto
void calc_dist(heads *G, int s) /* s eh o indice do vertice fonte */
{
int i;
no *aux;
for(i=0; i<NUMVERT; i++)
{
G[i].FLAG = 0;
G[i].DIST = MAXINT; /* MAXINT eh o maior inteiro representavel */
}
G[s].FLAG = 1;
G[s].DIST = 0;
INSERE(Q,s);
while (EMPTY(Q) != 1)
{
i = REMOVE(Q);
for(aux = G[i].ADJ; aux; aux = aux->NEXT)
{
if (G[aux->VERTEX].FLAG == 0)
{
G[aux->VERTEX].FLAG = 1;
G[aux->VERTEX].DIST = G[i].DIST + 1;
INSERE(Q,aux->VERTEX);
}
}
}
}
Ronaldo Celso Messias Correia – [email protected]
u
n
e
s
p
Caminho de Custo Mínimo - Dijkstra
 O algoritmo de Dijkstra é o mais famoso dos algoritmos
para cálculo de caminho de custo mínimo entre vértices
de um grafo e, na prática, o mais empregado.
 Escolhido um vértice como raiz da busca, esse
algoritmo calcula o custo mínimo deste vértice para
todos os demais vértices do grafo.
 O algoritmo pode ser usado sobre grafos orientados
(dígrafos), ou não, e admite que todas as arestas
possuam pesos não negativos (nulo é possível). Esta
restrição é perfeitamente possível no contexto de redes
de transportes, onde as arestas representam
normalmente distâncias ou tempos médios de
percurso; poderão existir, no entanto, aplicações que
as arestas apresentam pesos negativos, nestes casos
o algoritmo não funcionará corretamente.
Ronaldo Celso Messias Correia – [email protected]