Busca em Grafos - Resumo com Exercícios

Prévia do material em texto

Algoritmos de Busca em Grafos
Busca Geral
Algorithm 1 Busca(G, s)
1: s.visitado← 1
2: while houver aresta com um extremo visitado e outro não do
3: Seja (x, y) uma aresta com x.visitado = 1 e y.visitado = 0
4: y.visitado← 1
5: y.predecessor ← x
6: end while
7: for todo v em V (G) do
8: v.visitado← 0
9: v.predecessor ← NULL
10: end for
Busca em Largura (BFS) - O(n+m)
Instruções:
1. Escolha um vértice inicial s.
2. s tem custo 0 e predecessor nulo.
3. Os demais vértices têm custo infinito e predecessor nulo.
4. Crie uma fila de prioridades Q vazia.
5. Insira s na fila Q.
6. Insira, da esquerda para a direita, os vértices adjacentes a s.
7. Atualize o custo e o predecessor de cada vértice adjacente.
8. Examine os vértices adjacentes de cada vértice processado.
1
Algorithm 2 BFS(G, s)
1: s.estado← visitando
2: s.distância← 0
3: s.predecessor ← NULL
4: Q← fila vazia
5: ENFILEIRAR(Q, s)
6: for cada u em V (G) \ {s} do
7: u.estado← não-visitado
8: u.distância←∞
9: u.predecessor ← NULL
10: end for
11: while Q ̸= vazio do
12: u← DESENFILEIRAR(Q)
13: for cada v adjacente a u do
14: if v.estado = não-visitado then
15: v.estado← visitando
16: v.distância← u.distância+ 1
17: v.predecessor ← u
18: ENFILEIRAR(Q, v)
19: end if
20: end for
21: u.estado← processado
22: end while
Busca em Profundidade (DFS) - O(n+m)
Funciona apenas com grafos sem ciclos.
Instruções:
1. Visite o primeiro vértice adjacente de cada vértice, até chegar à primeira
folha.
2. Anote os pesos de entrada e lows dos vértices visitados.
3. Se um vértice for demarcador ou articulação, registre-o.
4. Desempilhe o vértice e anote seu peso de sáıda.
Ordenação Topológica (TopSort)
Instruções:
1. Anote os vértices de entrada e sáıda dos vértices do grafo.
2. Identifique fontes (vértices sem entradas).
3. Adicione fontes à lista e remova suas conexões.
2
4. Repita até que todos os vértices sejam processados.
Exerćıcios
1. Qual a complexidade do algoritmo BFS e como ela é afetada pelo número
de arestas e vértices?
2. Quais são as principais diferenças entre BFS e DFS?
3. Em que situações é prefeŕıvel utilizar a busca em profundidade em vez da
busca em largura?
4. Como a fila de prioridades influencia a performance da busca em largura?
5. Por que a ordenação topológica é importante em grafos direcionados aćıclicos?
3