Algoritmos de grafos en C++: Dijkstra, Kruskal, DFS, BFS y ordenamiento topológico

Algoritmos de grafos en C++

A continuación se presentan implementaciones en C++ de algoritmos clásicos sobre grafos: el algoritmo de Dijkstra, el algoritmo de Kruskal, los recorridos DFS y BFS, y el ordenamiento topológico.

1. Algoritmo de Dijkstra

Calcula las distancias mínimas desde un vértice inicial a todos los demás vértices de un grafo con pesos no negativos, utilizando una cola de prioridad.

void dijkstra(vector<vector<pair<int, int>>> &grafo, vector<int> &dist, int inicio)
{
    dist[inicio] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> colaprio;
    colaprio.push(make_pair(0, inicio));
    while (!colaprio.empty())
    {
        int u = colaprio.top().second;
        colaprio.pop();
        vector<pair<int, int>>::iterator it;
        for (it = grafo[u].begin(); it != grafo[u].end(); it++)
        {
            int v = it->first;
            int peso = it->second;
            if (dist[v] > dist[u] + peso)
            {
                dist[v] = dist[u] + peso;
                colaprio.push(make_pair(dist[v], v));
                MostrarCola(colaprio);
                MostrarVector(dist, inicio);
            }
        }
    }
}

2. Algoritmo de Kruskal

Construye un árbol de expansión mínima ordenando las aristas por peso y uniendo vértices mediante la estructura Union-Find.

void kruskal()
{
    mostrar(); cout << endl;
    sort(aristas.begin(), aristas.end(), compararAristas);
    mostrar(); cout << endl;
    vector<int> padres(numVertices);
    for (int i = 0; i < numVertices; i++)
    {
        padres[i] = i;
    }
    vector<vector<int>> arbolExpansion;
    for (const Arista& arista : aristas)
    {
        int origen = arista.origen;
        int destino = arista.destino;
        int raizOrigen = encontrarRaiz(padres, origen);
        int raizDestino = encontrarRaiz(padres, destino);
        if (raizOrigen != raizDestino)
        {
            arbolExpansion.push_back({ origen, destino });
            unirConjuntos(padres, raizOrigen, raizDestino);
        }
    }
    for (const auto& arista : arbolExpansion)
    {
        cout << arista[0] << " - " << arista[1] << endl;
    }
}

3. Búsqueda en profundidad (DFS) con ordenamiento topológico

Recorre el grafo en profundidad y apila los vértices al finalizar su exploración; el resultado invertido corresponde a un orden topológico.

void dfs(int v, vector<int> &visitado, stack<int> &Pila, const vector<vector<pair<int, int>>> &grafo)
{
    visitado[v] = 1;
    for (const auto& arista : grafo[v])
    {
        int u = arista.first; // Obtener el destino
        if (!visitado[u])
        {
            cout << "bajada v : " << v << " - ";
            Mostrar(Pila);
            dfs(u, visitado, Pila, grafo);
            cout << "subida v : " << v << " - ";
            Mostrar(Pila);
        }
    }
    Pila.push(v);
}

void ordenTopologico(int V, const vector<vector<pair<int, int>>> &grafo)
{
    stack<int> Pila;
    vector<int> visitado(V, 0);
    for (int i = 0; i < V; ++i)
    {
        if (!visitado[i]) dfs(i, visitado, Pila, grafo);
    }
    cout << "Solución" << endl;
    Mostrar(Pila);
}

4. Implementación con lista de adyacencia

Se define la inserción de aristas en una lista de adyacencia y dos recorridos: DFS iterativo con pila y BFS con cola.

void agregarArista(int origen, int destino)
{
    LAdyac[origen].push_back(destino);
}

void DFS(int verticeInicial)
{
    vector<int> visitado(Nver, 0);
    stack<int> pila;
    visitado[verticeInicial] = 1;
    pila.push(verticeInicial);
    while (!pila.empty())
    {
        int verticeActual = pila.top();
        pila.pop();
        cout << verticeActual << " ";
        for (int i = LAdyac[verticeActual].size() - 1; i >= 0; i--)
        {
            int adyacente = LAdyac[verticeActual][i];
            if (!visitado[adyacente])
            {
                visitado[adyacente] = 1;
                pila.push(adyacente);
            }
        }
    }
}

void BFS(int verticeInicial)
{
    vector<int> visitado(Nver, 0);
    queue<int> cola;
    visitado[verticeInicial] = 1;
    cola.push(verticeInicial);
    while (!cola.empty())
    {
        int verticeActual = cola.front();
        cola.pop();
        cout << verticeActual << " ";
        for (int adyacente : LAdyac[verticeActual])
        {
            if (!visitado[adyacente])
            {
                visitado[adyacente] = 1;
                cola.push(adyacente);
            }
        }
    }
}