05 busca em grafos

Prévia do material em texto

Otimização em Redes
Allexandre Fortes S. Reis
Coordenadoria de Engenharia de Produção
Departamento de Engenharia Mecânica
Campus Santo Antônio
Universidade Federal de São João Del Rei
5 de setembro de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 1 / 45
Conteúdo
1
Busca em Grafos
2
Busca em Profundidade - DFS
3
Busca em Largura - BFS
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 2 / 45
Busca em Grafos
Definição
Pode ser definida como a examinação de vértices e arestas de um grafo.
O projeto de bons algoritmos para determinação de estruturas ou proprieda-
des de grafos depende fortemente do domínio destas técnicas.
Terminologia
i Uma aresta ou vértice ainda não examinados são marcados como não explorados
ou não visitados;
ii Inicialmente, todos os vértices e arestas são marcados como não explorados;
iii Após terem sido examinados, os mesmos são marcados como explorados ou
visitados;
iv Ao final, todos os vértices e arestas são marcados como explorados (no caso
de uma busca completa).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 3 / 45
Busca em Grafos
Entrada: Grafo G = (N,A), vértice inicial i
1 Marque o vértice i como explorado;
2 enquanto existe j ∈ N com uma aresta {j, k} não explorada faça
3 Escolha o vértice j e explore a arestas {j, k} ;
4 se k não é marcado então
5 marque k;
6 fim
7 fim
Algoritmo 1: Algoritmo de Busca Genérica em Grafos
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 4 / 45
Busca em Grafos
Tipos
Dependendo do critério utilizado para escolha dos vértices e arestas a serem
examinados, diferentes tipos de buscas são desenvolvidos a partir da busca
genérica. Basicamente, duas buscas completas em grafos são essenciais:
i Busca em Profundidade (ou DFS � Depth-First Search);
ii Busca em Largura (ou BFS � Breadth-First Search).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 5 / 45
Busca em Profundidade - DFS
Características
A Busca em Profundidade explora todos os vértices de um grafo, usando
como critério o vértice visitado mais recentemente e não marcado. Utiliza
uma pilha explícita ou recursividade para guiar a busca.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 6 / 45
Busca em Profundidade - DFS
Entrada: Grafo G = (N,A), vértice inicial i
1 Marque o vértice i como explorado;
2 enquanto existe j vizinho de i faça
3 se j é marcado como não explorado então
4 Explore a aresta {i, j} ;
5 marque j como explorado;
6 DFS(G, j); //chamada recursiva
7 senão
8 se {i, j} não foi explorada ainda então
9 Explore a aresta {i, j} ;
10 fim
11 fim
12 fim
Algoritmo 2: Algoritmo de Busca em Profundidade - DFS
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 7 / 45
Busca em Profundidade - DFS
Algoritmo de Tarjan - GND
Durante a Busca em Profundidade de um grafo, o Algoritmo de Tarjan (1972)
propõe que pode-se numerar os vértices de acordo com o início e término desta
exploração; As diferentes situações nos permitem estabelecer uma classificação dos
arestas:
i Arestas de Árvore: Satisfazem ao primeiro se do algoritmo anterior (linha 3), ou seja, levam
à exploração de vértices ainda não visitados;
ii Arestas de Retorno: Demais arestas. Formam ciclos, pois levam a vértices já visitados.
Árvore de Profundidade
A subárvore de G formada pelas arestas de árvore é chamada de Árvore de
Profundidade de G.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 8 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(1) Aresta {1, 2}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 9 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(2) Aresta {2, 3}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 10 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(3) Aresta {3, 1}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 11 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(4) Aresta {3, 4}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 12 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(5) Aresta {4, 5}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 13 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(6) Aresta {5, 3}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 14 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(7) Aresta {3, 6}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 15 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
(8) Aresta {3, 7}.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 16 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Não-direcionado
Grago original e sua respectiva Árvore de Profundidade.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 17 / 45
Busca em Profundidade - DFS
Entrada: Grafo G = (N,A), vértice inicial i
1 enquanto existe i não explorado faça
2 DFS(G, i);
3 fim
Algoritmo 3: Algoritmo DFS para GD
Algoritmo de Tarjan - GD
Novamente, o Algoritmo de Tarjan propõe que, ao se explorar um grafo direcionado
G usando a DFS, pode-se categorizar os arcos;
Sejam o vértice i a origem do arco o vértice j o destino da mesmo:
i Arestas de Avanço: Caso j seja descendente de i na floresta;
ii Arestas de Retorno: Caso i seja descendente de j na floresta;
iii Arestas de Cruzamento: Caso j não seja descendente de i e nem i seja descendente de j na
floresta;
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 18 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
(1) Arco (1, 2).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 19 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
(2) Arco (2, 3).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 20 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
(3) Arco (3, 6).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 21 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
(4) Arco (6, 2).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 22 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
(5) Arco (1, 3).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 23 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
(6) Arco (4, 3).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 24 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
(7) Arco (4, 5).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 25 / 45
Busca em Profundidade - DFS
Exemplo - Grafo Direcionado
Grafo original e respectivo conjunto de árvores, ou floresta de profundidade.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 26 / 45
Aplicações - DFS
Detecção de Ciclos
Ao se executar o Algoritmo de Tarjan ou o DFS, basta que seja detectado
ao menos um arco de retorno, para se identificar que existe pelo menos um
ciclo no Grafo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 27 / 45
Aplicações - DFS
Detecção de Componentes Fortemente Conexas
Uma Componente Fortemente Conexa é um subconjunto maximal de vértices de um grafo
direcionado,o que significa que, para todo par de vértices i e j existe um caminho orientado
de j a i e vice-versa;
Durante a execução da DFS, podemos rotular os vértices de acordo com sua ordem de
exploração (índice superior, em preto);
Os vértices ainda não examinados totalmente, ou seja, ainda empilhados, permanecerão
assim até que seja determinada sua componente conexa;
Cada vértice também será rotulado com o menor valor de exploração entre os vértices
alcançáveis (índice inferior, em verde);
Ao final da exploração de um vértice v, se os dois rótulos forem iguais, então todos os
vértices presentes na pilha pertencem a uma mesma componente.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 28 / 45
Aplicações - DFS
Detecção de Componentes Fortemente Conexas
Uma Componente Fortemente Conexa é um subconjunto maximal de vértices de um grafo
direcionado, o que significa que, para todo par de vértices i e j existe um caminho orientado
de j a i e vice-versa;
Durante a execução da DFS, podemos rotular os vértices de acordo com sua ordem de
exploração (índice superior, em preto);
Os vértices ainda não examinados totalmente, ou seja, ainda empilhados, permanecerão
assim até que seja determinada sua componente conexa;
Cada vértice também será rotulado com o menor valor de exploração entre os vértices
alcançáveis (índice inferior, em verde);
Ao final da exploração de um vértice v, se os dois rótulos forem iguais, então todos os
vértices presentes na pilha pertencem a uma mesma componente.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 28 / 45
Aplicações - DFS
Detecção de Vértices de Articulação
Um vértice j é um vértice de articulação se sua remoção do grafo conexo aumentar o número de
componentes conexos.
O Algoritmo de Tarjan pode ser utilizado para detectar estes vértices em grafos conexos, não
orientados e sem laços ou arestas paralelas.
Considerando a árvore de profundidade T e a ordem de exploração dos vértices obtidas pela
aplicação da DFS, tem-se:
A raiz será um vértice de articulação se possuir pelo menos dois filhos em T ;
Cada um dos demais vértices i será um vértice de articulação se possuir pelo menos um
filho sem retorno para nenhum dos vértices ancestrais de i
Os vértices C e H são vértices de articulação.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 29 / 45
Aplicações - DFS
Detecção de Vértices de Articulação
Um vértice j é um vértice de articulação se sua remoção do grafo conexo aumentar o número de
componentes conexos.
O Algoritmo de Tarjan pode ser utilizado para detectar estes vértices em grafos conexos, não
orientados e sem laços ou arestas paralelas.
Considerando a árvore de profundidade T e a ordem de exploração dos vértices obtidas pela
aplicação da DFS, tem-se:
A raiz será um vértice de articulação se possuir pelo menos dois filhos em T ;
Cada um dos demais vértices i será um vértice de articulação se possuir pelo menos um
filho sem retorno para nenhum dos vértices ancestrais de i
Os vértices C e H são vértices de articulação.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 29 / 45
Aplicações - DFS
Detecção de Arestas de Articulação
Uma aresta é uma aresta de articulação ou ponte se sua remoção do grafo conexo aumentar o
número de componentes conexos.
Considerando a árvore de profundidade T e a ordem de exploração dos vértices obtidas pela
aplicação da DFS, tem-se:
Nenhuma aresta de retorno pode ser uma aresta de articulação;
Uma aresta (i, j) será uma aresta de articulação se o vértice j não possuir retorno para
nenhum de seus vértices ancestrais.
As arestas {C,E} e {H,G} são arestas de articulação
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 30 / 45
Aplicações - DFS
Detecção de Arestas de Articulação
Uma aresta é uma aresta de articulação ou ponte se sua remoção do grafo conexo aumentar o
número de componentes conexos.
Considerando a árvore de profundidade T e a ordem de exploração dos vértices obtidas pela
aplicação da DFS, tem-se:
Nenhuma aresta de retorno pode ser uma aresta de articulação;
Uma aresta (i, j) será uma aresta de articulação se o vértice j não possuir retorno para
nenhum de seus vértices ancestrais.
As arestas {C,E} e {H,G} são arestas de articulação
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 30 / 45
Busca em Largura - BFS
Características
A Busca em Largura explora todos os vértices de um grafo, usando como critério
o vértice visitado menos recentemente e não marcado. Utiliza uma fila guiar
a busca. Atuação em camadas:
i Inicialmente são considerados os vértices com distância 0 do vértice inicial;
ii Na iteração 1 são explorados os vértices com distância 1. Prosseguindo, de modo genérico,
na iteração d será adicionada uma camada com todos os vértices com distância d do vértice
inicial;
iii Cada novo vértice explorado é adicionado no final de uma fila Q;
iv Cada vértice da fila é removido depois que toda a vizinhança for visitada;
v A busca termina quando a fila se torna vazia.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 31 / 45
Busca em Largura
Entrada: Grafo G = (N,A), vértice inicial i
1 Crie uma fila Q vazia;
2 Marque o vértice i como explorado;
3 enquanto Q 6= ∅ faça
4 i← remove primeiro elemento de Q;
5 para todo vértice j vizinho de i faça
6 se j é marcado como nao explorado então
7 Explore a aresta {i, j} ;
8 Insira j em Q;
9 Marque j como explorado;
10 senão
11 se {i, j} não foi explorada ainda então
12 Explore a aresta {i, j} ;
13 fim
14 fim
15 fim
16 fim
Algoritmo 4: Algoritmo de Busca em Largura - BFS
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 32 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Inclusão de 1
Q = 1
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 33 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {1, 2}
Q = 2
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 34 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {1, 3}
Q = 2, 3
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 35 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {2, 3}
Q = 3
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 36 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {3, 4}
Q = 4
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 37 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {3, 5}
Q = 4, 5
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 38 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {3, 6}
Q = 4, 5, 6
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 39 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {3, 7}
Q = 3, 7
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 40 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
(1) Aresta {4, 5}
Q = 5, 6, 7
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 41 / 45
Busca em Largura - BFS
Exemplo - Grafo Não-direcionado
Grafo original e sua respectiva Árvore de Profundidade
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 42 / 45
Exercício
Aplique os os algoritmos DFS e BFS no grafo abaixo, à partir do nó 7.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 43 / 45
Dúvidas? Valar joll	orisO que faremos 
hoje professor? Esclarecer todas
 as dúvidas.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 44 / 45
Referências
(1) Notas de aula Professor Dr. Marco Antônio Carvalho (DECOM/UFOP);
(2) Notas de aula Professor Dr. Gustavo Peixoto Silva (DECOM/UFOP);
(3) Goldbarg, Marco e Goldbarg, Elizabeth. Grafos: Conceitos, algoritmos e apli-
cações (2012);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de setembro de 2017 45 / 45
	Busca em Grafos
	Busca em Profundidade - DFS
	Busca em Largura - BFS