Aula número 1
Dia 2-10-2000
Patrícia Isabel Assis Valadas da Silva
Nesta aula vimos duas maneiras possíveis de se percorrer grafos: em profundidade (DFS) e em largura (BFS).
Nesta página podemos encontrar, para além da explicação da matéria, exercícios resolvidos sobre a mesma, aplicações reais possíveis destes algoritmos e os seus applets em Java.
DFS - Depth-First Search (Percurso em profundidade)
O método usado pelo DFS é, como o seu nome indica, procurar num grafo o mais profundo possível.
Pode ser definido da seguinte forma:
Algoritmo: marcam-se os nós do grafo para indicar em que medida é que já foram visitados. Para tal começa-se por marcar todos os nós como não tendo sido visitados (Brancos). Os nós que já foram vistos dividem-se em duas categorias: os que estão "em curso" (Verdes) e os que já foram inteiramente vistos (Vermelhos), ou seja, aqueles que se encontram a verde mas que já não tem mais adjacentes brancos.
O algoritmo pode ser implementado do seguinte modo:
void DFS (grafo G) {
for (all v in G) {
v -> color = branco;
v -> p = null; }
time = 0;
for (all v in G)
if (v -> color = = branco)
DFS_Visit (v); }
void DFS_Visit (vértice v) {
time = time+1;
v -> color = verde;
v -> d = time;
for (all u in v -> adj)
if (u -> color = = branco) {
u -> p = v;
DFS_Visit (u); }
time = time+1;
v -> color = vermelho;
v -> f = time; }
O atributo d representa o tempo em que um nó foi visto pela primeira vez, isto é, a altura em que foi marcado a verde.
O atributo f representa o tempo em que o nó foi completamente visitado, neste caso isto significa que todos os seus descendentes foram vistos. Coincide com a altura em que é marcado a vermelho.
As figuras que se seguem ilustram o progresso do algoritmo DFS no grafo que se segue. Este grafo tem como source o vértice I.
|
O source é o primeiro vértice a ser visitado. Ao ser visitado passa a verde o que quer dizer que o seu "tratamento" está em curso. |
Vamos agora ver o estado dos seus adjacentes. Como I só tem como adjacente o vértice E, e este se encontra a branco, será o próximo a ser tratado, passando então para verde. |
Podemos agora verificar que E tem dois adjacentes e que os dois se encontram a branco. Qual dos dois será o próximo a ser tratado? Devemos adoptar uma convenção para faze-lo, neste caso optamos por percorrer os vértices por ordem alfabética. Assim sendo, o próximo vértice a ser tratado será o B, passando este também a verde. |
|
Seguindo o "modo de visita" adoptado, vamos tratar o vértice A. |
Neste passo "tratamos" o vértice C que, também ele, tem dois vértices adjacentes ainda a branco. Seguindo a mesma convenção segue-se o vértice D. |
Tratamos agora o vértice D, que passa a verde. |
|
Segue-se o vértice G. |
Neste passo "tratamos" o vértice F que, como podemos verificar, não tem nenhum adjacente a branco. O que fazer agora? |
Quando um vértice já não tem adjacentes a branco, este considera-se completamente tratado passando então para vermelho. |
|
Neste momento já temos o vértice F completamente tratado, temos então que recuar para o vértice que foi visitado anteriormente. Neste caso foi o vértice G que como também já não tem adjacentes brancos passa também a vermelho. |
Recuamos então até ao vértice D, mas D ainda tem um adjacente a branco o qual deverá ser tratado. |
H também não tem adjacentes a branco, é então a altura de passar a vermelho. |
|
Podemos agora verificar que já não existem vértices com adjacentes brancos. Agora temos sempre que ir recuando e tratar os vértices completamente, ou seja, eles vão passar a vermelho, até já não haverem vértices com o "tratamento em curso", isto é, a verde. |
|
A ultima figura representa o grafo final depois de ser percorrido através do algoritmo de DFS. |
BFS - Breadth-First Search (Percurso em largura)
O Breadth-First Search é um algoritmo que está na base de muitos algoritmos para grafos.
Pode ser definido da seguinte forma:
Algoritmo: marcam-se os nós do grafo para indicar em que medida é que já foram visitados. Para tal começa-se por marcar todos os nós como não tendo sido visitados (Brancos). Os nós que já foram vistos dividem-se em duas categorias: os que estão "em curso" (Verdes) e os que já foram inteiramente vistos (Vermelhos), ou seja, aqueles que se encontram a verde mas que já não tem mais adjacentes brancos.
O algoritmo pode ser implementado do seguinte modo:
void BFS (grafo G, vértice s) {
queue Q;
for (all v in G; v != s) {
v -> color = branco;
v -> d = inf;
v -> p = null; }
s -> color = verde;
s -> d = 0;
s -> p = null;
insert (Q,s);
while (!empty (Q)) {
u = head (Q);
for (all v in u -> adj) {
if (v -> color = = branco) {
v -> color = verde;
v -> d = u -> d+1;
v -> p = u;
insert (Q,v);} }
delete (Q);
u -> color = preto; } }
As figuras que se seguem ilustram o progresso do BFS no respectivo grafo.
|
Vamos agora aplicar o algoritmo BFS a este grafo tomando a letra I como source. |
I passa agora a ter o valor 1 a verde, o que quer dizer que a sua visita está "em curso". I é inserido na fila Q e será o próximo vértice a ser tratado. |
Verificamos que o único adjacente de I é o vértice E e que se encontra a branco . I passa agora para vermelho, pois já foi completamente tratado, e saí da fila. Para esta passa o vértice E (o número 2 indica qual a distancia entre o source - I - e o vértice - E). |
|
Como o vértice E tem dois adjacentes a branco, estes vão entrar os dois para a pilha. Devemos adoptar uma convenção para faze-lo. Neste caso os vértices serão colocados na fila por ordem alfabética. O vértice E passa a vermelho pois já está completamente tratado. |
Seguindo o mesmo raciocínio, tratamos o vértice B e o seu adjacente A passa para a fila com o valor 4. O próximo vértice a ser tratado não será o A mas sim o F pois este agora encontra-se à cabeça da fila. |
Ao tratarmos o vértice F o seu adjacente G, que ainda se encontrava a branco, passa para a fila também com o valor 4 pois esta é a distancia que o separa do source. |
|
Neste passo A é tratado passando os seu adjacentes, que se encontram a branco, para a fila para serem tratados posteriormente. |
Ao tratarmos G, podemos verificar que os seus vértices não se encontram a branco mas sim a verde, o que quer dizer que o seu "tratamento" está em curso, ou seja, já se encontram na fila. |
Passamos agora ao "tratamento" de C, que se encontra nas mesmas circunstâncias de G, e este saí da fila. |
|
Ao tratarmos o vértice D, é inserido na fila o ultimo vértice do grafo que se encontra a branco. |
H é tratado e neste momento deparamo-nos com uma fila vazia, o que quer dizer que a execução do algoritmo BFS termina aqui. |
Neste grafo podemos verificar a ordem pela qual se foram visitando os vértices. |
Exercícios resolvidos
(Livro - "Introduction to Algorithms", Thomas H.Cormen; Charles E. Leiserson; Ronald L. Rivest)
1. Mostre o resultado da aplicação do algoritmo Depth-First Search no seguinte grafo. Deve seguir a ordem alfabética dos vértices.
2. Mostre o resultado da aplicação do algoritmo Breadth-First Search no seguinte grafo. Deve usar o vértice u como source.
Mas afinal, quais são as aplicações reais destes dois modos de procura?
Podem ser aplicados, por exemplo, em apoios à decisão, construção de horários, planeamento, demonstração automática de teoremas, ... .
Por exemplo: dado um mapa de estradas, com ligações entre cidades, encontrar um caminho entre duas das cidades. O mapa pode ser representado por um grafo. Um grafo é constituído por nós (A,B,C,D,E,F) e ramos que são as ligações entre os nós.
Vamos agora ver como procurar um caminho entre dois pontos (por exemplo A e F) usando as duas estratégias de procura estudadas.
DFS - Depth-First Search (Percurso em profundidade)
Partimos de
A
Sequência = [A]
Expansão de A = {B,E,C}
Nova sequência, com A marcado =
[B,E,C,A]
Escolhemos
B
Expansão de
B =
{D,E}
Nova sequência, com
B marcado =
[D,E,B,E,C,A]
Escolhemos
D
Expansão de
D = {}
Nova sequência, com
D marcado =
[D,E,B,E,C,A]
Escolhemos
E
Expandimos
E =
{F}
Nova sequência, com
E (1ª ocorrência) marcado =
[F,D,E,B,E,C,A]
Escolhemos
F
F era o nosso objectivo
Então há caminho entre
A e
F.
BFS - Breadth-First Search (Percurso em largura)
Partimos de A
Sequência = [A]
Expansão de A
= {B,E,C}
Nova sequência, com A
marcado = [A,B,E,C]
Escolhemos B
Expansão de B
= {D,E}
Nova sequência, com B
marcado = [A,B,E,C,D,E]
Escolhemos E
Expansão de E
= {F}
Nova sequência, com E
marcado = [A,B,E,C,D,E,F]
Escolhemos C
Expansão de C
= {E}
Nova sequência, com C
marcado = [A,B,E,C,D,E,F,E]
Escolhemos D
Expansão de D
= { }
Nova sequência, com D
marcado = [A,B,E,C,D,E,F,E]
Escolhemos E
Expansão de E
= {F}
Nova sequência, com E
marcado = [A,B,E,C,D,E,F,F]
Escolhemos F
F
era o nosso objectivo
Então há caminho entre A
e F.
Applet em Java
Applet do DFS
Applet do BFS