Estou de volta!
Como esperado por muitos, o resultado da OBI saiu completamente ontem. Para o RN o resultado foi bom na categoria iniciação (mais de 100 aprovados), porém deixou a desejar na de Programação, tendo 2 aprovados em Júnior, 1 no nível 1 e 5 no nível 2. Como continuação do nosso preparo para a segunda fase da competição, teremos hoje a segunda aula sobre Grafos!
Aula 7 – Grafos II
Conteúdo: Aprofundamento com as buscas em largura e profundidade em um grafo, além do menor caminho em grafos não-valorados.
A operação básica na maioria dos grafos é percorrê-lo completamente e sistematicamente. É preciso visitar cada vértice e cada aresta exatamente uma vez em uma ordem pré-definida. Existem dois tipos primordiais de algoritmos para realizar essa atividade: Busca em Largura (BFS, do inglês Breadth-First search) e Busca em Profundidade (DFS, do inglês Depth-First search). A diferença entre não é nem percebida em certos problemas, pois eles compartilham uma idéia fundamental: marcar os vértices já explorados para não repetir ações.
Busca em Largura
A Busca em Largura é apropriada se nós não precisarmos de uma ordem específica para a busca ou se nós estamos interessados no menor caminho entre dois vértices para grafos não-valorados. A sua implementação utiliza duas vetores Boolean para manter o conhecimento sobre todos os vértices. Um vértice é descoberto a primeira vez que o visitamos. Um vértice é considerado processado depois de passarmos por todas as arestas provenientes dele.
Uma vez que o vértice é descoberto, ele é colocado em uma fila, sendo processados na ordem de chegada, pois os vértices mais antigos na fila são os mais próximos da raiz (local de partida para a busca). Para não encher o post somente com código, colocarei diversos links falando sobre BFS, para vocês darem uma olhada neles, depois voltarem para a continuação do post.
- Busca em largura – Wikipédia
- Busca em largura – IME/USP
- Busca em largura – IME/USP – outra explicação
- Breadth-first search – Wikipedia
O comportamento exato da BFS depende das funções de processar o vértice e processar a aresta, sendo essa a forma de personalizar a busca, podendo imprimí-los ou contar o número de arestas. Outra forma de personalizar é na função Boolean de validar a aresta, ignorando as não existentes. Ao retornar sempre true, percorreremos todas arestas, sendo uma BFS completa.
Encontrando caminhos
O vetor parent utilizado na bfs( ) é muito útil para encontrar caminhos em um grafo. O vértice que descobriu i é denominado parent[i]. Essa relação define uma árvore de descobertas com o nó inicial como a raiz da árvore.
Pelo fato dos vértices serem descobertos em ordem crescente de distância da raiz, essa árvore tem uma propriedade muito importante. O caminho da raiz até x (um dos vértices) utiliza o menor número de arestas possível para esse caminho.
Ele pode ser reconstruído seguindo os “ancestrais” de x até a raiz, pelo vetor parent[ ], contudo será um caminho do fim para o começo. Nós podemos “consertá-lo” ao guardá-los em uma pilha. É preciso lembrar de dois pontos cruciais na utilização de BFS: só é possível descobrir o menor caminho entre x e y, se x for a raiz do grafo; além disso, essa ação só é realizada com eficiência em grafos não-valorados.
Busca em Profundidade
Busca em profundidade utiliza a mesma idéia do Backtracking, mostrado na Aula 5 desse curso. Ambos envolvem a busca de todas as possibilidades ao avançar quando for possível e recuar quando não houver nada inexplorado à frente, sendo mais facilmente entendíveis como algoritmos recursivos. Essa busca pode ser pensada como BFS com uma pilha ao invés de fila. A parte bela dessa implementação é que a recursividade elimina a existência explícita de uma pilha, contudo não irei mostrar aqui o algoritmo completo, novamente sugerindo sites para vê-lo:
- Busca em Grafos – UFSC
- Busca em profundidade – Wikipédia
- Busca em profundidade – IME/USP
- Busca em Grafos
Com essa abordagem, chegamos ao final de mais uma aula de grafos, faltando apenas a abordagem de algoritmos como o de Dijkstra e da Árvore Geradora Mínima, os quais serão abordados próxima semana. Abaixo estão dispostos os exercícios a respeito das aulas 6 e 7:
- Bicoloring – Nível 1
- Playing With Wheels – Nível 2
- The Tourist Guide – Nível 3
- Slash Maze – Nível 2
- Edit Step Ladders – Nível 3
- Tower of Cubes – Nível 3
- From Dusk Till Dawn – Nível 3
- Hanoi Tower Troubles Again! – Nível 3
PS: Todo o conteúdo desse post e de todo o curso “Programando melhor” é baseado no livro Programming Challenges, de autoria de Miguel Revilla e Steve Skiena e foi permitido o “resumo” e tradução do mesmo pelos próprios autores para a criação desse curso. Além disso os exercícios estão todos disponibilizados no site UVa Online Judge.
Posts interessantes:
- Divulgação OBMEP
- Programando melhor: Aula 6 – Grafos I
- Programando melhor: Aula 5 – Bracktracking
- Programando melhor: Revisão
- Programando melhor: Aula 2 – Estrutura de Dados
Vamos lá pessoal! Essas últimas aulas serão cruciais para a segunda fase da OBI, preparem-se! Qualquer dúvida ou dica, COMENTEM!
Helton de Melo Duarte
“Os céus manifestam a glória de Deus e o firmamento anuncia a obra das suas mãos.” Salmos 19.1
“A lei do SENHOR é perfeita e refrigera a alma; o testemunho do SENHOR é fiel e dá sabedoria aos símplices.” Salmos 19.7
maio 1st, 2009 at 22:02
Parabéns, pelo excelente resultado na OBI!!!
Deixo também meus parabéns para Bryan e para todos os outros competidores! Valeu pela representação, todos nós sabemos que vocês tÊm muita CAPACIDADE de ser os MELHORES!!
Que Deus continue vos abençoando!!!
Até Logo!
maio 4th, 2009 at 14:55
Muito obrigado Dayane,
Graças a Deus consegui ser classificado para a 2ª fase da OBI.
Assim como você, deixo meus parabéns para Bryan, Ítalo, Israel e Guilherme, os quais também se classificaram. Para meus amigos do IF-RN que não conseguiram passar, fiquei muito triste, pq conheço a capacidade de todos.
Obrigado,
Helton de Melo Duarte
maio 7th, 2009 at 14:29
[...] Leia mais >> [...]
janeiro 23rd, 2010 at 18:00
[...] Programando melhor: Aula 7 – Grafos II [...]