Caminhamentos em Grafos

Alguns algoritmos vistos anteriormente envolvem caminhamentos em estruturas de dados que são relativamente simples. Por exemplo, vimos que a pesquisa linear nada mais é do que um caminhamento em uma lista de elementos. Dada a estrutura linear e unidimensional da lista de elementos, a tarefa de se caminhar nela é bastante simples.

Grafos, por outro lado, são estruturas de dados mais complexas, o que faz com que caminhamentos em grafos sejam um pouco mais difíceis do que os caminhamentos vistos anteriormente. Nas seções seguintes, veremos duas formas de caminhamentos em grafos: busca em profundidade ---ou Depth-First Search (DFS, em inglês)---, e busca em largura ---ou Breadth-First Search (BFS, em inglês).

É importante entender bem essas duas formas de se percorrer um grafo, pois muitos outros algoritmos importantes usam conceitos de busca em profundidade ou busca em largura.

Antes de começarmos, vamos definir mais formalmente o problema que desejamos resolver.

Problema: Dado um grafo $G(V, E)$, direcionado ou não-direcionado, em um vértice de origem $s \in V$, precisamos identificar todos os vértices de $G$ que são alcançáveis a partir de $s$. Dizer que um vértice $u$ é alcançável a partir de um vértice $v$ significa que existe uma sequência de arestas no grafo permitindo que se saia de $u$ e se chegue a $v$.

Tanto a BFS quanto a DFS resolvem o problema acima. A diferença é a estratégia que cada um desses algoritmos usa para resolvê-lo. Vejamos essas diferenças.

Playground

# Use este espaço para praticar o que você aprendeu nesta seção. # Basta digitar o código no espaço abaixo e clicar 'run'.