Aula 14: Grafos — BFS e DFS

Pense em um mapa de cidades conectadas por estradas, ou amigos em uma rede social. Qualquer coisa que seja 'pontos e relações entre eles' é um 'grafo': nós (nodes) conectados por arestas (edges). Duas formas de percorrer um grafo: o BFS se espalha anel por anel, como uma onda na água — ótimo para o

BFS é como uma onda na água: você começa em um ponto e se espalha anel por anel, o mais próximo primeiro. DFS é como andar em um labirinto — você vai até o fim de um caminho, e se ficar preso, volta e tenta outro.

percurso em grafo: Visitar sistematicamente todos os nós alcançáveis a partir de um nó inicial, usando BFS (uma fila) ou DFS (uma pilha/recursão).
dicionário de adjacência: Uma representação de grafo em que cada nó é mapeado para sua lista de vizinhos: {node: [neighbors]} — acesso aos vizinhos em O(1).
conjunto de visitados: Um conjunto (set) que marca quais nós já foram percorridos, para evitar revisitá-los e prevenir laços infinitos.