🕸️ Algoritmos de Grafos

📊 3.1 Representaciones de Grafos

A: [B, C]
B: [D]
C: [D]
D: []

  A B C D
A 0 1 1 0
B 0 0 0 1
C 0 0 0 1
D 0 0 0 0

Complejidad de Algoritmos

🚶 3.2 BFS & DFS

Visualización: BFS vs DFS

Implementación BFS

vector<int> bfs(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    vector<int> order;
    vector<bool> visited(n, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : graph[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    return order;
}

🎯 3.3 Dijkstra's Algorithm

Key Insight

Enfoque greedy: siempre expandir el vértice no visitado más cercano.

Pasos del Algoritmo

1. Inicializar distancias: d[source] = 0, otros = ∞
2. Usar min-heap para obtener el vértice no visitado más cercano
3. Actualizar distancias a vecinos (relaxation)
4. Repetir hasta procesar todos los vértices

Visualización: Dijkstra

Implementación

vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int src) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;
    
    dist[src] = 0;
    pq.push({0, src});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

import heapq

def dijkstra(graph, src):
    n = len(graph)
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]
    
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    
    return dist

🔄 3.4 Floyd-Warshall

Key Insight

Para cada vértice k, actualizar todos los caminos considerando k como intermediario:

Propiedades

• Funciona con pesos negativos (pero no ciclos negativos)
• Tiempo: O(V³), Espacio: O(V²)
• Puede detectar ciclos negativos (diagonal < 0)

Implementación

void floydWarshall(vector<vector<int>>& dist) {
    int n = dist.size();
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    
    // Detectar ciclos negativos
    for (int i = 0; i < n; i++) {
        if (dist[i][i] < 0) {
            cout << "Ciclo negativo detectado" << endl;
            return;
        }
    }
}

🌲 3.5 Minimum Spanning Tree

Visualización: MST

Kruskal's con Union-Find

class UnionFind {
    vector<int> parent, rank;
public:
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
};

int kruskal(int n, vector<tuple<int,int,int>>& edges) {
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    int mstWeight = 0, count = 0;
    for (auto& [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            mstWeight += w;
            if (++count == n - 1) break;
        }
    }
    return mstWeight;
}

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    edges.sort()
    uf = UnionFind(n)
    mst_weight, count = 0, 0
    for w, u, v in edges:
        if uf.unite(u, v):
            mst_weight += w
            count += 1
            if count == n - 1: break
    return mst_weight

🧳 3.6 Traveling Salesman Problem

Visual: mapa de ciudades y tour

DP con Bitmask

donde mask representa ciudades visitadas e i es la ciudad actual.

Complejidad

• Tiempo: O(n² 2ⁿ)
• Espacio: O(n 2ⁿ)

Implementación

int tsp(vector<vector<int>>& dist) {
    int n = dist.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    
    // Base case: empezar desde ciudad 0
    dp[1][0] = 0;
    
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (!(mask & (1 << u)) || dp[mask][u] == INT_MAX) continue;
            
            for (int v = 0; v < n; v++) {
                if (mask & (1 << v)) continue;
                int newMask = mask | (1 << v);
                dp[newMask][v] = min(dp[newMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    
    // Encontrar mínimo para regresar al inicio
    int result = INT_MAX;
    int finalMask = (1 << n) - 1;
    for (int i = 1; i < n; i++) {
        if (dp[finalMask][i] != INT_MAX) {
            result = min(result, dp[finalMask][i] + dist[i][0]);
        }
    }
    return result;
}

💧 3.7 Maximum Flow

Conceptos Clave

• Grafo Residual: Muestra capacidad restante
• Augmenting Path: Camino de s a t con capacidad positiva
• Max-Flow Min-Cut Theorem: Flujo máximo = capacidad del corte mínimo

Ford-Fulkerson

1. Encontrar augmenting path en grafo residual (DFS/BFS)
2. Determinar bottleneck (capacidad mínima en el camino)
3. Actualizar capacidades residuales
4. Repetir hasta que no exista augmenting path

Implementación

class MaxFlow {
    vector<vector<int>> capacity, flow;
    vector<bool> visited;
    int n;
    
    int dfs(int u, int t, int minFlow) {
        if (u == t) return minFlow;
        visited[u] = true;
        
        for (int v = 0; v < n; v++) {
            if (!visited[v] && capacity[u][v] > flow[u][v]) {
                int bottleneck = min(minFlow, capacity[u][v] - flow[u][v]);
                int result = dfs(v, t, bottleneck);
                if (result > 0) {
                    flow[u][v] += result;
                    flow[v][u] -= result;
                    return result;
                }
            }
        }
        return 0;
    }
    
public:
    int maxFlow(int s, int t) {
        int totalFlow = 0;
        while (true) {
            fill(visited.begin(), visited.end(), false);
            int pathFlow = dfs(s, t, INT_MAX);
            if (pathFlow == 0) break;
            totalFlow += pathFlow;
        }
        return totalFlow;
    }
};

🎨 3.8 Graph Coloring

Aplicaciones

• Scheduling problems
• Register allocation en compiladores
• Asignación de frecuencias
• Coloreo de mapas

Welsh-Powell Algorithm

1. Ordenar vértices por grado (descendente)
2. Asignar el color más pequeño disponible a cada vértice

Visualización: Graph Coloring

Complejidad

Encontrar el número cromático es NP-hard para grafos generales. El algoritmo greedy da una solución válida pero no necesariamente óptima.