TEORIA DOS GRAFOS
Márcio Antônio Duarte
UFCat – Ciência da Computação
email: marcioaduarte@[Link]
DFS (Depth-First Search)
●
Explorar vértices descobertos mais recentes primeiro;
●
Oposto de BFS: explora mais antigo primeiro;
●
Interpretação
●
procurar uma saída de um labirinto vai fundo atrás
da saída (tomando decisões a cada
encruzilhada);
●
volta a última encruzilhada quando encontrar um
beco sem saída (ou lugar já visitado).
DFS (Busca em Profundidade)
●
Explorar o grafo abaixo usando DFS
●
início: vértice 4
●
vizinhos encontrados em ordem crescente
●
Ordem de descobrimento dos vértices?
DFS (Árvore de Profundidade)
●
Árvore induzida pela busca em profundidade
●
Raiz: vértice de origem
●
Pai de v: nó que levou à descoberta de v
raiz: nó 4
●
Ordem da busca define árvore
DFS (Árvore de Profundidade)
●
Árvore induzida pela busca em profundidade
●
Raiz: vértice de origem
●
Pai de v: nó que levou à descoberta de v
raiz: nó 4
●
Ordem da busca define árvore
DFS (Árvore de Profundidade)
●
Árvore induzida pela busca em profundidade
●
Raiz: vértice de origem
●
Pai de v: nó que levou à descoberta de v
raiz: nó 4
●
Ordem da busca define árvore
DFS (Árvore de Profundidade)
●
Também se pode usar o esquema de corespara guiar a
busca:
●
Todos os vértices são inicializados brancos;
●
Quando um vértice v é descoberto pela primeira
vez, ele se torna cinza;
●
Quando todos os vértices adjacentes a v são
descobertos, v se torna preto.
DFS (Árvore de Profundidade)
●
Árvore induzida pela busca em profundidade
●
Raiz: vértice de origem
●
Pai de v: nó que levou à descoberta de v
raiz: nó 4
●
Ordem da busca define árvore
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Árvore de Profundidade)
DFS (Busca em Profundidade)
Exercício: faça a busca em profundidade no grafo
abaixo, mostrando a ordem de visita aos vértices.
DFS (Implementação)
●
Utilizando Recursão
[Link](u)
2. Marcar u como descoberto
3. Para cada aresta (u,v) incidente a u
4. Se v não estiver marcado
5. DFS(v) // chamada recursiva
6.
7. Desmarcar todos os vértices
8. Escolher vértice inicial s
9. DFS(s)
DFS (Implementação)
●
Utilizando Pilha
1. DFS(s)
2. Desmarcar todos os vértices
3. Definir pilha P com um elemento s
4. Enquanto P não estiver vazia
5. Remover u de P // no topo da pilha
6. Se u não estiver marcado
7. Marcar u como descoberto
8. Para cada aresta (u,v) incidente a u
9. Adicionar v em P // no topo
DFS (Complexidade)
Mesma complexidade que BFS!
●
O(|V| + |E|)
●
Complexidade linear
●
mesma ordem de grandeza do tempo necessário
para ler o grafo!
DFS (Aplicação)
●
Uma aplicação comum da DFS é determinar se um
grafo é cíclico
●
Isso acontece quando, ao percorrer uma aresta,
um vértice x se conecta a um vértice y que
não é branco
DFS (Aplicação)
●
Uma aplicação comum da DFS é determinar se um
grafo é cíclico
●
Isso acontece quando, ao percorrer uma aresta,
um vértice x se conecta a um vértice y que
não é branco
●
Algoritmo de busca em profundidade é facilmente
adaptado para esta tarefa!
●
Como?
DFS (Ordenação Topológica)
●
Ordenação topológicade um grafo direcionado
acíclico
●
Ordenação linear dos vértices do grafo tal que u
aparece antes de v se há uma aresta (u,v)
DFS (Ordenação Topológica)
Faça a ordenação topológica do grafo abaixo
