Grafos 4 rotulação de arestas

Prévia do material em texto

Algoritmos e Estruturas de 
Dados II – SCC-503 
Grafos: Rotulação de 
Arestas 
Gustavo Batista 
A execução do algoritmo de busca em 
profundidade gera uma árvore chamada 
árvore de busca em profundidade. 
Árvore de Busca em 
Profundidade 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
Árvore de Busca em 
Profundidade 
1 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
Árvore de Busca em 
Profundidade 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 
Árvore de Busca em 
Profundidade 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
Árvore de Busca em 
Profundidade 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 
Árvore de Busca em 
Profundidade 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 6/ 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/9 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/10 4/9 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/ 
Árvore de Busca em 
Profundidade 
2 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/ 
13/ 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/ 
13/14 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/15 
13/14 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 
2 
5 
1 
6 
3 
7 
4 
8 
1/16 
2/11 
3/10 4/9 
5/8 6/7 
12/15 
13/14 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 
Floresta de Árvores de Busca 
Caso o grafo G for não (fortemente) 
conectado, então a busca em 
profundidade irá criar uma floresta de 
árvores de busca. 
1 
6 
2 
5 
3 
4 
Classificação de Arestas 
As arestas de um grafo podem ser 
classificadas conforme a sua árvore de busca 
em profundidade: 
n  Arestas de árvore: arestas que ocorrem na árvore 
de busca em profundidade; 
n  Arestas de retorno: arestas que ligam com um nó 
antecessor na árvore; 
n  Arestas de avanço: arestas que ligam com um nó 
descendente na árvore; 
n  Arestas de cruzamento: demais arestas. 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
Árvore de Busca em 
Profundidade 
1 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
Árvore de Busca em 
Profundidade 
1 
6 arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 
Árvore de Busca em 
Profundidade 
3 
1 
6 arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
Árvore de Busca em 
Profundidade 
4 
3 
1 
6 arv 
arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 
Árvore de Busca em 
Profundidade 
8 
4 
3 
1 
6 arv 
arv 
arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 6/ 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv 
arv 
arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 6/ 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv 
arv 
arv 
arv 
ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 6/ 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv 
arv 
arv 
arv 
ret 
ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 6/ 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv 
arv 
arv 
arv 
ret 
ret 
ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/ 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/ 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/ 4/9 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/ 
3/10 4/9 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
Árvore de Busca em 
Profundidade 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/ 
Árvore de Busca em 
Profundidade 
2 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/ 
13/ 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/ 
13/14 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/ 
2/11 
3/10 4/9 
5/8 6/7 
12/15 
13/14 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/16 
2/11 
3/10 4/9 
5/8 6/7 
12/15 
13/14 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
arv 
arv 
2 
5 
1 
6 
3 
7 
4 
8 
1/16 
2/11 
3/10 4/9 
5/8 6/7 
12/15 
13/14 
Árvore de Busca em 
Profundidade 
5 
2 
7 
8 
4 
3 
1 
6 arv 
arv arv ret ret 
arv 
arv ret 
arv 
arv 
Em um grafo não orientado todas as 
arestas são de árvore ou de retorno. 
Árvore de Busca em 
Profundidade 
É importante reparar que a classificação das arestas 
pode ser diferente se a ordem os vértices adjacentes 
percorridos dos alterada. 
Em outras palavras, a classificação das arestas 
depende da árvore de busca em profundidade. 
Entretanto, a maioria dos algoritmos que faz uso da 
classificação das arestas, não depende de um 
classificação específica, mas sim da existência de um 
tipode aresta. 
n  Por exemplo, algoritmo de detecção de ciclos requer 
encontrar uma aresta de retorno. 
Árvore de Busca em 
Profundidade 
O algoritmo de busca em profundidade 
funciona igualmente bem para grafos 
direcionados. 
Nesse caso, podem ocorrer arestas de 
avanço e de cruzamento. 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 
1 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 
1 
2/ 
2 
arv 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 
1 
2/ 
2 
3/ 
3 
arv arv 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 
1 
2/ 
2 
3/ 
3 
arv arv 
6 
arv 
4/ 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 
1 
2/ 
2 
3/ 
3 
arv arv 
6 
arv ret 
4/ 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 2/ 3/ arv arv 
arv ret 
4/5 
1 
2 
3 
6 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 2/ 3/6 arv arv 
arv ret 
4/5 
1 
2 
3 
6 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 2/ 3/6 arv arv 
arv ret 
4/5 7/ 
1 
2 
3 
6 
5 
arv 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 2/ 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 2/ 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 2/9 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/ 2/9 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
ava 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/10 2/9 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
ava 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/10 2/9 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
4 
11/ 
ava 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/10 2/9 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
4 
11/ 
cruz 
ava 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/10 2/9 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
4 
11/ 
cruz 
cruz ava 
Árvore de Busca em 
Profundidade 
3 2 1 
4 5 6 
1/10 2/9 3/6 arv arv 
arv ret 
4/5 7/8 
1 
2 
3 
6 
5 
arv 
cruz 
4 
11/12 
cruz 
cruz ava 
Exercício 
Mostre como a busca em profundidade 
funciona para o grafo a seguir. Mostre a 
seqüência de vértices visitados, a 
árvore ou floresta de busca em 
profundidade e o vetor antecessor. 
1 2 
4 5 
7 9 8 
6 
3