Grafos: busca em largura (BFS) e em profundidade (DFS)

Como representar

Um grafo tem vértices (pessoas, cidades, módulos) e arestas (amizade, estrada, dependência), com ou sem direção e peso. A forma mais comum é a lista de adjacência: um mapa de cada vértice para seus vizinhos. Matriz de adjacência (V × V) só compensa em grafos densos.

BFS: em largura

Usa uma fila e um conjunto de visitados. Visita todos os vizinhos antes de ir mais longe, então a primeira vez que alcança um vértice é pelo menor número de arestas — caminho mais curto em grafo sem peso (labirintos, "graus de separação"). Com pesos, use Dijkstra (heap) no lugar.

DFS: em profundidade

Usa uma pilha (ou recursão) e vai até o fim de um caminho antes de voltar. Serve para achar ciclos, componentes conectados, ordenação topológica (em que ordem compilar módulos ou rodar migrations) e resolver labirintos. Em grafos grandes, prefira a pilha explícita para não estourar a pilha de chamadas.

// Menor número de passos de 'origem' até 'destino' (ou -1 se não há caminho)
fun distancia(grafo: Map<String, List<String>>, origem: String, destino: String): Int {
    val fila = ArrayDeque(listOf(origem))
    val dist = hashMapOf(origem to 0) // também serve de "visitados"
    while (fila.isNotEmpty()) {
        val v = fila.removeFirst()
        if (v == destino) return dist.getValue(v)
        for (viz in grafo[v].orEmpty()) {
            if (viz !in dist) {
                dist[viz] = dist.getValue(v) + 1
                fila.addLast(viz)
            }
        }
    }
    return -1
}