TEORIA DOS GRAFOS
Márcio Antônio Duarte
UFG – Ciência da Computação
email: marcioaduarte@[Link]
Busca em Grafos
Percorrer um grafo é um problema fundamental;
Deve-se ter uma forma sistemática de visitar as
arestas e os vértices;
O algoritmo deve ser suficientemente flexível para se
adequar à diversidade de grafos.
Busca em Grafos
Como saber se existe caminho entre dois vértices de
maneira eficiente?
Ideia: evitar explorar vértices já explorados
marcar os vértices!
vértice: não visitados, visitados e processados.
Busca em Grafos
Solução
Manter uma lista de vértices no estado visitados;
Há duas possibilidades:
Busca em largura (usando uma fila);
Busca em profundidade (usando uma pilha).
BFS (Busca em Largura)
BFS –Breadth-First Search
Todos os nós com distância k a um nó v são
visitados antes dos nós com distância k+1;
Descobre todos os vértices alcançáveis a partir de
v.
BFS (Busca em Largura)
BFS –Breadth-First Search (Algoritmo Genérico):
Passo inicial
desmarcar todos os vértices;
selecionar origem e marcá-lo visitado;
Passo geral (enquanto houver vértice não-visitado)
Selecionar vértice visitado, u;
Considerar aresta não explorada, (u, v);
Se v não estiver marcado, marcar v como
visitado;
Marcar u processado quando não houver mais
arestas incidentes a u a serem exploradas.
BFS (Busca em Largura)
Ordem de visita dos vértices e arestas?
Algoritmo genérico não
estabelece ordem!
Qual é uma possível ordem?
Sistemática de exploração
Duas abordagens
Explorar o vértice descoberto “mais antigo”;
Explorar o vértice descoberto “mais recente.
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q:
Resultado:
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q:
Resultado:
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q: 2, 5, 6
Resultado: 2, 5, 6
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q: 5, 6, 3
Resultado: 2, 5, 6, 3
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q: 6, 3, 4
Resultado: 2, 5, 6, 3, 4
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q: 3, 4
Resultado: 2, 5, 6, 3, 4
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q: 4
Resultado: 2, 5, 6, 3, 4
BFS (Busca em Largura)
Percorrendo um Grafo: BFS
Q:
Resultado: 2, 5, 6, 3, 4
BFS (Busca em Largura)
Interpretação
Onda é propagada à partir da raiz;
Onda expande em círculos, descobrindo vértices
alcançáveis!
BFS (Busca em Largura)
Percorrendo um Grafo: árvore de busca em largura:
As arestas (2,5) e (3,4) não percorridas!
BFS (Busca em Largura)
BFS –Breadth-First Search
Em grafos não-dirigidos, cada aresta é visitada
somente duas vezes;
Em grafos dirigidos, cada aresta é visitada uma
única vez;
Em geral, armazena-se a distânciade cada nó em
relação ao nó inicial onde a busca se iniciou;
Exemplo: aplicações de caminho mais curto!
É comum a utilização de esquemas de cores para
identificar os nós ainda não visitados (branco),
visitados (cinza) e já completamente processados
(preto)!
BFS (Busca em Largura)
Exercício: faça a busca em largura no grafo abaixo,
mostrando a ordem de visita aos vértices.
BFS (Busca em Largura)
Exercício: faça a busca em largura no grafo abaixo,
mostrando a ordem de visita aos vértices.
BFS (Busca em Largura)
Grafo Acíclico
●
Grafo acíclico é um grafo que não possui ciclos.
Exemplo:
●
K4 é acíclico?
●
Como descobrir se um grafo é acíclico?
BFS (Busca em Largura)
Árvores
- Uma árvore é um grafo acíclico conexo.
- Folha: vértice com grau 1;
- Raiz: um determinado vértice define orientação na
árvore (pai, filhos, descendentes e ancestrais)
●
Quantos caminhos (simples) distintos existe entre dois
vértices quaisquer?
●
Quantas arestas possui uma árvore com n vértices?
BFS (Busca em Largura)
Árvore Geradora
●
Subgrafo que contém todos os vértices de G e é uma
árvore.