1 - Caminhos em um grafo

Você já conheceu a estrutura de grafos e viu alguns exemplos de como modelar problemas através dela, além de algumas opções de como implementá-los computacionalmente. E caminhar pelo bichinho que é bom, nada!

Mas agora você terá a oportunidade, pois chegou a hora de apresentar algumas formas de traçar caminhos em grafos.

Inicialmente, não se preocupe em achar o menor caminho (ainda): foque o estudo em alguns algoritmos que permitem realizar passeios pelo grafo, encontrando um caminho (ou todos) de um ponto A até um ponto B da estrutura.

Existem dois algoritmos clássicos de busca em grafos, denominados Busca em Profundidade (Depth-First Search) e Busca em Largura (Breadth-First Search), carinhosamente conhecidos por suas siglas, DFS e BFS, respectivamente.

Sim, são até parecidas, para facilitar a confusão.

A ideia por trás dos dois algoritmos é similar: você vai escolher um vértice inicial do grafo, o que você quiser, e, a partir dele, vai tentar chegar naqueles vértices que têm uma ligação direta (ou seja, uma aresta) com ele. Nesse momento você coloca esses vértices no caminho e repete a operação até chegar no ponto final que você quer. Sim, não ache estranho, a ideia é essa mesmo! De ponto em ponto, até chegar no final!

Antes de eu sair mostrando códigos, quero frisar que, apesar de seguirem a mesma ideia, existe uma diferença básica entre os dois algoritmos: a ordem em que eles percorrem os vértices vizinhos. Também se fosse tudo igual, ia ser um algoritmo só, não é mesmo?

Então utilize recursos visuais para ajudar. E volte ao lindo grafo do RN, que foi visto na aula passada.