Grafos: Matriz, Lista de Adyacencia, BFS, DFS y Dijkstra

Un árbol tiene una regla estricta: cada nodo tiene exactamente un padre y no hay ciclos. Eso alcanza para jerarquías, pero se queda corto para casi todo lo demás.

En una red social, si vos sos amigo de Ana y Ana es amiga de Luis, y Luis también es amigo tuyo, ¿quién es el padre de quién? En un mapa de calles, ¿cuál es la raíz? Ninguna de esas preguntas tiene sentido, porque eso no es un árbol: es un grafo.

Un grafo es la estructura más general de todas. De hecho, un árbol es simplemente un grafo con restricciones: conectado, sin ciclos y con una raíz elegida.

1. Vocabulario

Ejemplos que ya usás todos los días:

2. Las dos formas de representarlo

Un grafo no se guarda “como se ve”. Hay dos representaciones estándar, y elegir mal cuesta caro.

En Java, la lista de adyacencia se escribe con un Map, que ya conocés de la lección Colecciones en Java y Genéricos (JCF):

public class Grafo<V> {
    private final Map<V, List<V>> adyacencia = new HashMap<>();

    public void agregarVertice(V v) {
        adyacencia.putIfAbsent(v, new ArrayList<>());
    }

    // No dirigido: la arista se agrega en los dos sentidos
    public void agregarArista(V origen, V destino) {
        adyacencia.computeIfAbsent(origen,  k -> new ArrayList<>()).add(destino);
        adyacencia.computeIfAbsent(destino, k -> new ArrayList<>()).add(origen);
    }

    public List<V> vecinos(V v) {
        return adyacencia.getOrDefault(v, List.of());
    }
}

Fijate que computeIfAbsent y getOrDefault —los métodos de Map de la lección Colecciones en Java y Genéricos (JCF)— hacen todo el trabajo pesado. Sin ellos harían falta cuatro if extra.

3. BFS y DFS: el mismo algoritmo con distinta memoria

Recorrer un grafo tiene un problema que los árboles no tenían: los ciclos. Si A conecta con B, B con C y C con A, un recorrido ingenuo da vueltas para siempre.

La solución es un Set de visitados. Y con eso, los dos recorridos clásicos difieren en una sola cosa: qué estructura guarda los vértices pendientes.

// BFS — cola: primero en entrar, primero en salir
public List<V> bfs(V inicio) {
    List<V> orden = new ArrayList<>();
    Set<V> visitados = new HashSet<>();
    Queue<V> pendientes = new ArrayDeque<>();

    visitados.add(inicio);       // ← marcar AL ENCOLAR, no al desencolar
    pendientes.offer(inicio);

    while (!pendientes.isEmpty()) {
        V actual = pendientes.poll();
        orden.add(actual);

        for (V vecino : vecinos(actual)) {
            if (visitados.add(vecino)) {     // add devuelve false si ya estaba
                pendientes.offer(vecino);
            }
        }
    }
    return orden;
}

// DFS — recursivo: la pila de llamadas de la JVM hace de pila
public List<V> dfs(V inicio) {
    List<V> orden = new ArrayList<>();
    dfs(inicio, new HashSet<>(), orden);
    return orden;
}

private void dfs(V actual, Set<V> visitados, List<V> orden) {
    if (!visitados.add(actual)) return;   // ya lo visitamos: cortar
    orden.add(actual);
    for (V vecino : vecinos(actual)) {
        dfs(vecino, visitados, orden);
    }
}

Marcá como visitado al encolar, no al desencolar. Si esperás a sacarlo de la cola, un mismo vértice puede entrar varias veces antes de procesarse por primera vez. En un grafo grande eso no es un detalle: multiplica el trabajo y puede agotar la memoria.

4. Dijkstra: el camino más barato

BFS encuentra el camino con menos aristas. Pero si las aristas tienen peso —kilómetros, minutos, costo— el camino más corto en cantidad de saltos puede ser carísimo.

public Map<V, Integer> dijkstra(V origen) {
    Map<V, Integer> distancia = new HashMap<>();
    Set<V> visitados = new HashSet<>();

    // La cola de prioridad de Colecciones en Java y Genéricos (JCF): siempre saca el más barato
    PriorityQueue<V> cola = new PriorityQueue<>(
        Comparator.comparingInt(v -> distancia.getOrDefault(v, Integer.MAX_VALUE))
    );

    distancia.put(origen, 0);
    cola.offer(origen);

    while (!cola.isEmpty()) {
        V actual = cola.poll();
        if (!visitados.add(actual)) continue;   // ya lo procesamos

        for (Arista<V> arista : aristasDe(actual)) {
            int nueva = distancia.get(actual) + arista.peso();
            // "Relajar": si por acá sale más barato, actualizamos
            if (nueva < distancia.getOrDefault(arista.destino(), Integer.MAX_VALUE)) {
                distancia.put(arista.destino(), nueva);
                cola.offer(arista.destino());
            }
        }
    }
    return distancia;
}

Dijkstra no funciona con pesos negativos. Su garantía se basa en que una vez que visitás un vértice, su distancia ya es definitiva; con un peso negativo eso deja de ser cierto. Para ese caso existe Bellman-Ford.

5. Errores frecuentes

6. Ejercicio práctico guiado

Desafío: grados de separación en una red social

Implementá saltosMinimos(String desde, String hasta) que devuelva la cantidad mínima de intermediarios entre dos personas, y caminoMasCorto(...) que devuelva la cadena de personas.

Pensá por qué BFS es la única opción correcta acá, y por qué DFS daría un resultado equivocado.

import java.util.*;

public class RedSocial {

    private final Map<String, List<String>> amigos = new HashMap<>();

    public void agregarAmistad(String a, String b) {
        // No dirigido: la amistad va en los dos sentidos
        amigos.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
        amigos.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    }

    /**
     * BFS: devuelve la cantidad mínima de saltos, o -1 si no hay conexión.
     * DFS NO sirve acá: encontraría *un* camino, no el más corto.
     */
    public int saltosMinimos(String desde, String hasta) {
        if (!amigos.containsKey(desde) || !amigos.containsKey(hasta)) return -1;
        if (desde.equals(hasta)) return 0;

        Set<String> visitados = new HashSet<>();
        Queue<String> cola = new ArrayDeque<>();

        visitados.add(desde);
        cola.offer(desde);
        int saltos = 0;

        while (!cola.isEmpty()) {
            int personasEnEsteNivel = cola.size();   // ← la clave del conteo por niveles
            saltos++;

            for (int i = 0; i < personasEnEsteNivel; i++) {
                String actual = cola.poll();

                for (String amigo : amigos.getOrDefault(actual, List.of())) {
                    if (amigo.equals(hasta)) return saltos;
                    if (visitados.add(amigo)) {      // add devuelve false si ya estaba
                        cola.offer(amigo);
                    }
                }
            }
        }
        return -1;   // recorrimos todo lo alcanzable y no apareció
    }

    /**
     * Misma idea, pero guardando de dónde vino cada persona
     * para poder reconstruir el camino al final.
     */
    public List<String> caminoMasCorto(String desde, String hasta) {
        if (!amigos.containsKey(desde) || !amigos.containsKey(hasta)) return List.of();

        Map<String, String> vinoDe = new HashMap<>();
        Set<String> visitados = new HashSet<>();
        Queue<String> cola = new ArrayDeque<>();

        visitados.add(desde);
        cola.offer(desde);

        while (!cola.isEmpty()) {
            String actual = cola.poll();

            if (actual.equals(hasta)) {
                // Reconstruimos el camino yendo hacia atrás desde el destino
                LinkedList<String> camino = new LinkedList<>();
                for (String p = hasta; p != null; p = vinoDe.get(p)) {
                    camino.addFirst(p);
                }
                return camino;
            }

            for (String amigo : amigos.getOrDefault(actual, List.of())) {
                if (visitados.add(amigo)) {
                    vinoDe.put(amigo, actual);   // recordamos el padre en el recorrido
                    cola.offer(amigo);
                }
            }
        }
        return List.of();
    }

    public static void main(String[] args) {
        RedSocial red = new RedSocial();
        red.agregarAmistad("Ana",    "Beto");
        red.agregarAmistad("Beto",   "Carla");
        red.agregarAmistad("Carla",  "Diego");
        red.agregarAmistad("Ana",    "Elena");
        red.agregarAmistad("Elena",  "Diego");
        red.agregarAmistad("Fabián", "Gala");   // grupo desconectado del resto

        System.out.println("Ana → Diego  : " + red.saltosMinimos("Ana", "Diego"));
        System.out.println("Camino       : " + red.caminoMasCorto("Ana", "Diego"));
        System.out.println("Ana → Fabián : " + red.saltosMinimos("Ana", "Fabián"));
        System.out.println("Ana → Ana    : " + red.saltosMinimos("Ana", "Ana"));
    }
}

Ana → Diego  : 2
Camino       : [Ana, Elena, Diego]
Ana → Fabián : -1
Ana → Ana    : 0

8. Floyd–Warshall: caminos mínimos entre todos los pares

Dijkstra responde desde un origen y exige pesos no negativos. Floyd–Warshall calcula los caminos más cortos entre todos los pares de vértices y admite aristas negativas, siempre que el resultado no esté afectado por un ciclo negativo.

Inicializar la matriz de distancias

Para V vértices se construye dist[V][V]:

• dist[i][i] = 0;
• dist[i][j] = peso(i, j) si existe una arista;
• dist[i][j] = INF si j es inalcanzable directamente desde i.

INF no debe ser Long.MAX_VALUE: sumarle un peso desbordaría y podría convertirse en un número negativo. Se usa un centinela seguro, Long.MAX_VALUE / 4, y nunca se suman distancias inalcanzables.

Invariante y evolución

Antes de procesar k, dist[i][j] es el mejor costo conocido cuyos vértices intermedios pertenecen a 0..k-1. Para cada par se decide si conviene conservarlo o pasar por k:

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Ejemplo (∞ significa inalcanzable), con aristas A→B=4, B→C=-2 y A→C=5:

Inicial             Después de permitir B
    A   B   C           A   B   C
A   0   4   5       A   0   4   2
B   ∞   0  -2       B   ∞   0  -2
C   ∞   ∞   0       C   ∞   ∞   0

El valor A→C baja de 5 a 2 porque aparece el camino A→B→C. La matriz completa evoluciona una vez por cada posible intermediario.

Implementación segura en Java

El método valida que la entrada sea una matriz cuadrada, rechaza filas nulas, valores fuera del rango seguro y matrices vacías. La entrada utiliza el mismo INF para indicar ausencia de arista.

public final class FloydWarshall {
    public static final long INF = Long.MAX_VALUE / 4;

    public record Resultado(long[][] distancias, boolean tieneCicloNegativo) {}

    public static Resultado calcular(long[][] pesos) {
        validarMatriz(pesos);
        int vertices = pesos.length;
        long[][] dist = new long[vertices][vertices];

        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                long peso = pesos[i][j];
                dist[i][j] = i == j ? Math.min(0, peso) : peso;
            }
        }

        for (int k = 0; k < vertices; k++) {
            for (int i = 0; i < vertices; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 0; j < vertices; j++) {
                    if (dist[k][j] == INF) continue;
                    long pasandoPorK = dist[i][k] + dist[k][j];
                    if (pasandoPorK < dist[i][j]) {
                        dist[i][j] = pasandoPorK;
                    }
                }
            }
        }

        boolean cicloNegativo = false;
        for (int v = 0; v < vertices; v++) {
            if (dist[v][v] < 0) {
                cicloNegativo = true;
                break;
            }
        }
        return new Resultado(copiar(dist), cicloNegativo);
    }

    private static void validarMatriz(long[][] pesos) {
        if (pesos == null || pesos.length == 0) {
            throw new IllegalArgumentException("la matriz es obligatoria y no puede estar vacía");
        }
        int vertices = pesos.length;
        for (int i = 0; i < vertices; i++) {
            if (pesos[i] == null || pesos[i].length != vertices) {
                throw new IllegalArgumentException("se requiere una matriz cuadrada");
            }
            for (long peso : pesos[i]) {
                if (peso < -INF || peso > INF) {
                    throw new IllegalArgumentException("peso fuera del rango seguro");
                }
            }
        }
    }

    private static long[][] copiar(long[][] matriz) {
        long[][] copia = new long[matriz.length][];
        for (int i = 0; i < matriz.length; i++) {
            copia[i] = matriz[i].clone();
        }
        return copia;
    }
}

La suma es segura porque dos valores finitos, cada uno entre -INF e INF, no alcanzan los límites de long. Un par permanece inalcanzable si su celda termina en INF; no debe imprimirse como una distancia real.

Aristas y ciclos negativos

Una arista negativa es válida: puede representar crédito, ganancia o una corrección de costo. Dijkstra falla con aristas negativas porque da por definitiva una distancia que luego podría reducirse. Floyd–Warshall sí las incorpora.

Un ciclo negativo permite reducir el costo indefinidamente. Después de las tres vueltas, dist[v][v] < 0 detecta que v participa en uno de esos ciclos. En ese caso, las “distancias mínimas” afectadas no están definidas; el llamador debe tratar tieneCicloNegativo como un fallo explícito, no consumir la matriz como si fuera válida.

Complejidad y elección

Floyd–Warshall usa O(V³) tiempo por sus tres bucles y O(V²) espacio por la matriz. Es directo para todos los pares y adecuado para grafos densos o de tamaño moderado.

Repetir Dijkstra desde cada vértice suele costar O(V · (E log V)) con lista de adyacencia y puede ser mejor en grafos dispersos, pero solo cuando todas las aristas son no negativas. La representación, los pesos permitidos y la consulta requerida deciden el algoritmo; no existe un ganador universal.

Para llevarte

• Un grafo es la estructura más general: un árbol es un grafo conectado, sin ciclos y con raíz.
• Lista de adyacencia para grafos dispersos (casi todos los reales); matriz solo si es denso.
• En Java, la lista de adyacencia es un Map<V, List<V>>, y computeIfAbsent hace el trabajo pesado.
• Sin un Set de visitados, cualquier ciclo convierte el recorrido en un bucle infinito.
• BFS y DFS son el mismo algoritmo: solo cambia si los pendientes están en una cola o en una pila.
• Marcá los vértices como visitados al encolar, nunca al desencolar.
• BFS da el camino con menos aristas; si las aristas tienen peso, hace falta Dijkstra.
• Dijkstra visita siempre el pendiente más barato y relaja las aristas. No sirve con pesos negativos.