Búsqueda en amplitud (BFS) y profundidad (DFS)

BFS — Búsqueda en amplitud

Explora nivel por nivel usando una cola. Garantiza encontrar el camino más corto en grafos no ponderados.

Esquema:

cola.push(inicio)
mientras cola no esté vacía:
    u = cola.front(); cola.pop()
    para cada vecino v de u:
        si v no visitado:
            visitado[v] = true
            dist[v] = dist[u] + 1
            cola.push(v)

Usos: camino más corto en grids/grafos sin pesos, componentes conexas, flood fill.

DFS — Búsqueda en profundidad

Explora tan profundo como sea posible usando una pila (o recursión).

Esquema recursivo:

dfs(u):
    visitado[u] = true
    para cada vecino v de u:
        si v no visitado:
            dfs(v)

Usos: detectar ciclos, componentes conexas, ordenamiento topológico, backtracking.

Representación de grafos

// Lista de adyacencia (preferir)
vector<int> adj[MAXN];
adj[u].push_back(v);
adj[v].push_back(u); // si no dirigido

// Matriz de adyacencia (solo si n ≤ 1000)
bool adj[1001][1001];