Grafos y algoritmos sobre grafos

Conceptos de grafos

• Grafo: conjunto de vértices (nodos) y aristas (conexiones)
• Dirigido: las aristas tienen dirección (u → v)
• No dirigido: las aristas son bidireccionales
• Ponderado: las aristas tienen peso/costo

Algoritmos clave

Dijkstra — Camino más corto con pesos ≥ 0

Usa priority_queue (min-heap). Complejidad: O((V+E) log V).

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
dist[inicio] = 0;
pq.push({0, inicio});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;
    for (auto [v, w] : adj[u])
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
}

Union-Find (DSU) — Componentes conexas

Estructura para unir conjuntos y verificar conectividad en O(α(n)) ≈ O(1).

Árbol de expansión mínima (MST)

• Kruskal: ordenar aristas por peso + Union-Find. O(E log E).
• Prim: similar a Dijkstra. O((V+E) log V).