Los grafos son una de las estructuras de datos más versátiles y poderosas de la informática. Desde las redes sociales como Facebook o Twitter hasta los sistemas de navegación GPS, pasando por los compiladores de lenguajes de programación y los motores de búsqueda, los grafos están presentes en prácticamente todos los ámbitos de la tecnología moderna. En Java, dominar la teoría de grafos y su implementación es una competencia fundamental para cualquier programador que aspire a resolver problemas complejos de forma eficiente.
Un grafo es, en su forma más elemental, un conjunto de nodos (también llamados vértices) conectados mediante aristas (también llamadas arcos o edges). Esta definición aparentemente simple esconde una riqueza extraordinaria: con solo dos conceptos —nodos y conexiones— se pueden modelar relaciones tan diversas como las rutas entre ciudades, las amistades entre personas, las dependencias entre tareas de un proyecto o el flujo de datos en una red informática. En este artículo exploraremos la teoría de grafos desde sus fundamentos matemáticos hasta su implementación práctica en Java, incluyendo los algoritmos clásicos de recorrido y búsqueda de caminos más cortos.
📜 Origen histórico: Euler y los puentes de Königsberg
La teoría de grafos nació formalmente en 1736 cuando el matemático suizo Leonhard Euler resolvió el famoso problema de los puentes de Königsberg. La ciudad de Königsberg (actual Kaliningrado, Rusia) estaba dividida por el río Pregel, que formaba dos islas conectadas entre sí y con las orillas mediante siete puentes. La pregunta que se planteaban los habitantes era sencilla: ¿es posible recorrer todos los puentes exactamente una vez y regresar al punto de partida?
Mapa histórico de los siete puentes de Königsberg (1736). Leonhard Euler demostró que el recorrido era imposible, dando origen a la teoría de grafos.
Euler demostró que tal recorrido era imposible. Para ello, abstrajo el problema representando cada zona de tierra como un nodo y cada puente como una arista. Con esta representación, Euler estableció que un recorrido que atraviese todas las aristas exactamente una vez (hoy llamado circuito euleriano) solo es posible si todos los nodos tienen grado par. Como los cuatro nodos de Königsberg tenían grado impar, el recorrido era imposible. Este razonamiento marcó el nacimiento formal de la teoría de grafos y de la topología combinatoria.
🔷 ¿Qué es un grafo? Definición formal
Formalmente, un grafo se define como un par G = (V, E), donde V es un conjunto finito de vértices (nodos) y E es un conjunto de aristas (arcos). Cada arista es un par de vértices (v, w) con v, w ∈ V. Si los pares están ordenados, hablamos de un grafo dirigido (o dígrafo); si no están ordenados, hablamos de un grafo no dirigido.
Opcionalmente, se puede definir una función de peso ω: E → ℝ que asigne a cada arista un valor numérico (distancia, coste, capacidad...). En ese caso, el grafo se denomina grafo valorado o grafo ponderado. Un ejemplo cotidiano: un mapa de carreteras es un grafo valorado donde las ciudades son nodos, las carreteras son aristas y los kilómetros son los pesos.
📖 Terminología fundamental
Antes de implementar grafos en Java, es imprescindible dominar la terminología básica. Los siguientes conceptos aparecen constantemente en algoritmos, entrevistas técnicas y documentación profesional.
| Concepto | Definición | Ejemplo |
|---|---|---|
| Vértice adyacente | Dos vértices unidos directamente por una arista | En una red social, dos amigos directos son adyacentes |
| Grado de un nodo | Número de aristas que inciden en él. En grafos dirigidos se distingue grado de entrada y grado de salida | Un nodo con 5 conexiones tiene grado 5 |
| Camino | Secuencia de vértices donde cada par consecutivo es adyacente | Ruta Madrid → Valencia → Barcelona |
| Camino simple | Camino sin vértices repetidos | A → B → C (sin volver a pasar por A ni B) |
| Ciclo | Camino que comienza y termina en el mismo vértice | A → B → C → A |
| Grafo conexo | Existe un camino entre cada par de vértices | Una red donde todos los ordenadores pueden comunicarse |
| Grafo acíclico | Grafo que no contiene ningún ciclo | Un árbol, las dependencias de tareas de un proyecto |
| Bosque | Grafo sin ciclos (colección de árboles) | Varios árboles desconectados entre sí |
| Árbol libre | Bosque conexo (un solo componente sin ciclos) | La estructura jerárquica de un sistema de archivos |
| Componente conexa | Subgrafo maximal conexo dentro de un grafo no conexo | Grupos aislados de islas conectadas por puentes |
🗂️ Tipos de grafos
Los grafos se clasifican según varias propiedades combinables entre sí. Comprender estas clasificaciones permite elegir la representación y los algoritmos adecuados para cada problema.
Grafo dirigido vs. no dirigido
En un grafo no dirigido, la arista (A, B) es idéntica a la arista (B, A). Es como una calle de doble sentido. En un grafo dirigido (dígrafo), la arista (A, B) indica una conexión de A hacia B, pero no necesariamente de B hacia A. Es como una calle de sentido único. Ejemplos reales: una red de carreteras bidireccionales es un grafo no dirigido; la relación "seguir" en Twitter es un grafo dirigido.
Grafo valorado (ponderado) vs. no valorado
Un grafo valorado asocia un peso numérico a cada arista (distancia, coste, tiempo...). Un grafo no valorado simplemente indica si existe o no la conexión. El plano de metro es un grafo no valorado si solo importa la conectividad; se convierte en valorado cuando añadimos el tiempo de viaje entre estaciones.
Grafo denso vs. disperso
Un grafo es denso si el número de aristas se acerca al máximo posible (V² para dirigidos, V(V-1)/2 para no dirigidos). Es disperso (sparse) si tiene pocas aristas comparado con el máximo. Esta distinción es crucial para elegir la representación: los grafos densos funcionan bien con matrices de adyacencia; los dispersos se benefician de listas de adyacencia.
DAG (Directed Acyclic Graph)
Un DAG es un grafo dirigido sin ciclos. Los DAGs son fundamentales en informática: modelan dependencias entre tareas (compilación de proyectos), la historia de commits en Git, y la propagación de valores en redes neuronales. Sobre un DAG se puede aplicar el ordenamiento topológico, que asigna un orden lineal a los nodos respetando las dependencias.
💻 Representación de grafos en Java
Existen dos formas principales de representar un grafo en memoria: la matriz de adyacencia y la lista de adyacencia. Cada una tiene ventajas e inconvenientes que determinan cuál elegir según el problema.
| Característica | Matriz de adyacencia | Lista de adyacencia |
|---|---|---|
| Espacio | O(V²) | O(V + E) |
| Consultar arista (u, v) | O(1) | O(grado de u) |
| Listar vecinos de v | O(V) | O(grado de v) |
| Añadir arista | O(1) | O(1) |
| Ideal para | Grafos densos, consultas frecuentes de existencia de arista | Grafos dispersos, recorridos BFS/DFS |
📊 Matriz de adyacencia: implementación en Java
La matriz de adyacencia es una tabla bidimensional de tamaño V × V donde cada celda matriz[i][j] indica si existe una arista del nodo i al nodo j. En un grafo no valorado, la celda contiene 1 (arista existe) o 0 (no existe). En un grafo valorado, la celda almacena el peso de la arista, usando un valor especial (como Integer.MAX_VALUE o 0) para indicar ausencia de conexión.
/**
* Implementación de un grafo valorado mediante matriz de adyacencia.
* Soporta grafos dirigidos y no dirigidos.
*
* Complejidad espacial: O(V²)
* Consultar arista: O(1)
* Listar vecinos: O(V)
*/
public class GrafoMatriz {
private final int[][] adyacencia;
private final int numVertices;
private final boolean dirigido;
private static final int SIN_ARISTA = 0;
/**
* Crea un grafo con el número de vértices indicado.
*
* @param numVertices número total de vértices (0 a numVertices - 1)
* @param dirigido true si el grafo es dirigido
*/
public GrafoMatriz(int numVertices, boolean dirigido) {
if (numVertices <= 0) {
throw new IllegalArgumentException("El número de vértices debe ser positivo");
}
this.numVertices = numVertices;
this.dirigido = dirigido;
this.adyacencia = new int[numVertices][numVertices];
}
/**
* Añade una arista con peso entre dos vértices.
* En grafos no dirigidos, la arista se añade en ambas direcciones.
*
* @param origen vértice origen (0-indexed)
* @param destino vértice destino (0-indexed)
* @param peso peso de la arista (debe ser distinto de SIN_ARISTA)
*/
public void agregarArista(int origen, int destino, int peso) {
validarVertice(origen);
validarVertice(destino);
if (peso == SIN_ARISTA) {
throw new IllegalArgumentException("El peso no puede ser " + SIN_ARISTA);
}
adyacencia[origen][destino] = peso;
if (!dirigido) {
adyacencia[destino][origen] = peso;
}
}
/**
* Comprueba si existe una arista entre dos vértices.
*
* @return true si hay arista de origen a destino
*/
public boolean existeArista(int origen, int destino) {
validarVertice(origen);
validarVertice(destino);
return adyacencia[origen][destino] != SIN_ARISTA;
}
/**
* Obtiene el peso de la arista entre dos vértices.
*
* @return peso de la arista, o SIN_ARISTA si no existe
*/
public int obtenerPeso(int origen, int destino) {
validarVertice(origen);
validarVertice(destino);
return adyacencia[origen][destino];
}
/**
* Devuelve el grado del vértice (número de aristas incidentes).
* En grafos dirigidos, devuelve el grado de salida.
*/
public int grado(int vertice) {
validarVertice(vertice);
int cuenta = 0;
for (int j = 0; j < numVertices; j++) {
if (adyacencia[vertice][j] != SIN_ARISTA) {
cuenta++;
}
}
return cuenta;
}
/**
* Imprime la matriz de adyacencia en formato tabular.
*/
public void imprimirMatriz() {
System.out.print(" ");
for (int j = 0; j < numVertices; j++) {
System.out.printf("%4d", j);
}
System.out.println();
System.out.println(" " + "----".repeat(numVertices));
for (int i = 0; i < numVertices; i++) {
System.out.printf("%2d |", i);
for (int j = 0; j < numVertices; j++) {
System.out.printf("%4d", adyacencia[i][j]);
}
System.out.println();
}
}
public int getNumVertices() {
return numVertices;
}
public int[][] getAdyacencia() {
return adyacencia;
}
private void validarVertice(int v) {
if (v < 0 || v >= numVertices) {
throw new IllegalArgumentException(
"Vértice " + v + " fuera de rango [0, " + (numVertices - 1) + "]"
);
}
}
// --- Ejemplo de uso ---
public static void main(String[] args) {
// Grafo no dirigido valorado con 5 nodos
GrafoMatriz grafo = new GrafoMatriz(5, false);
grafo.agregarArista(0, 1, 10);
grafo.agregarArista(0, 3, 30);
grafo.agregarArista(0, 4, 100);
grafo.agregarArista(1, 2, 50);
grafo.agregarArista(2, 4, 10);
grafo.agregarArista(3, 2, 20);
grafo.agregarArista(3, 4, 60);
System.out.println("=== Matriz de adyacencia ===");
grafo.imprimirMatriz();
System.out.println("\n¿Existe arista 0→2? " + grafo.existeArista(0, 2));
System.out.println("¿Existe arista 0→1? " + grafo.existeArista(0, 1));
System.out.println("Peso arista 1→2: " + grafo.obtenerPeso(1, 2));
System.out.println("Grado del nodo 0: " + grafo.grado(0));
}
}
=== Matriz de adyacencia ===
0 1 2 3 4
--------------------
0 | 0 10 0 30 100
1 | 10 0 50 0 0
2 | 0 50 0 20 10
3 | 30 0 20 0 60
4 | 100 0 10 60 0
¿Existe arista 0→2? false
¿Existe arista 0→1? true
Peso arista 1→2: 50
Grado del nodo 0: 3
📋 Lista de adyacencia: implementación en Java
La lista de adyacencia es la representación más utilizada en la práctica profesional. En lugar de una matriz V × V, cada nodo almacena únicamente la lista de sus vecinos. Esto ahorra memoria en grafos dispersos y permite iterar eficientemente sobre los vecinos de cada nodo, que es la operación más frecuente en BFS y DFS.
import java.util.*;
/**
* Implementación de un grafo valorado mediante listas de adyacencia.
* Usa Map<Integer, List<Arista>> para flexibilidad.
*
* Complejidad espacial: O(V + E)
* Listar vecinos: O(grado del nodo)
* Consultar arista: O(grado del nodo)
*/
public class GrafoLista {
/**
* Representa una arista con destino y peso.
*/
public static class Arista {
private final int destino;
private final int peso;
public Arista(int destino, int peso) {
this.destino = destino;
this.peso = peso;
}
public int getDestino() { return destino; }
public int getPeso() { return peso; }
@Override
public String toString() {
return "→" + destino + "(peso=" + peso + ")";
}
}
private final Map<Integer, List<Arista>> adyacencia;
private final boolean dirigido;
public GrafoLista(boolean dirigido) {
this.dirigido = dirigido;
this.adyacencia = new LinkedHashMap<>();
}
/**
* Añade un vértice al grafo (sin aristas).
*/
public void agregarVertice(int vertice) {
adyacencia.putIfAbsent(vertice, new ArrayList<>());
}
/**
* Añade una arista valorada entre dos vértices.
* Crea los vértices automáticamente si no existen.
*/
public void agregarArista(int origen, int destino, int peso) {
agregarVertice(origen);
agregarVertice(destino);
adyacencia.get(origen).add(new Arista(destino, peso));
if (!dirigido) {
adyacencia.get(destino).add(new Arista(origen, peso));
}
}
/**
* Devuelve la lista de aristas salientes de un vértice.
*/
public List<Arista> obtenerVecinos(int vertice) {
List<Arista> vecinos = adyacencia.get(vertice);
if (vecinos == null) {
throw new IllegalArgumentException("Vértice " + vertice + " no existe");
}
return Collections.unmodifiableList(vecinos);
}
/**
* Devuelve el conjunto de todos los vértices del grafo.
*/
public Set<Integer> obtenerVertices() {
return Collections.unmodifiableSet(adyacencia.keySet());
}
/**
* Imprime el grafo en formato lista de adyacencia.
*/
public void imprimir() {
for (Map.Entry<Integer, List<Arista>> entrada : adyacencia.entrySet()) {
System.out.println(entrada.getKey() + " → " + entrada.getValue());
}
}
// --- Ejemplo de uso ---
public static void main(String[] args) {
GrafoLista grafo = new GrafoLista(false);
grafo.agregarArista(0, 1, 10);
grafo.agregarArista(0, 3, 30);
grafo.agregarArista(0, 4, 100);
grafo.agregarArista(1, 2, 50);
grafo.agregarArista(2, 4, 10);
grafo.agregarArista(3, 2, 20);
grafo.agregarArista(3, 4, 60);
System.out.println("=== Lista de adyacencia ===");
grafo.imprimir();
System.out.println("\nVecinos del nodo 0:");
for (Arista a : grafo.obtenerVecinos(0)) {
System.out.println(" " + a);
}
}
}=== Lista de adyacencia === 0 → [→1(peso=10), →3(peso=30), →4(peso=100)] 1 → [→0(peso=10), →2(peso=50)] 2 → [→1(peso=50), →4(peso=10), →3(peso=20)] 3 → [→0(peso=30), →2(peso=20), →4(peso=60)] 4 → [→0(peso=100), →2(peso=10), →3(peso=60)] Vecinos del nodo 0: →1(peso=10) →3(peso=30) →4(peso=100)
🌊 Recorrido en anchura (BFS)
El recorrido BFS (Breadth-First Search) explora el grafo por niveles: primero visita todos los vecinos directos del nodo origen, después todos los vecinos de esos vecinos, y así sucesivamente. Utiliza una cola (Queue) como estructura auxiliar. BFS garantiza encontrar el camino más corto (en número de aristas) desde el origen hasta cualquier nodo alcanzable en grafos no valorados.
Las aplicaciones de BFS incluyen: encontrar el camino más corto en grafos no valorados, detectar si un grafo es bipartito, calcular la distancia mínima entre dos nodos en redes sociales (los "grados de separación"), y rastrear páginas web (web crawling).
import java.util.*;
/**
* Implementación de BFS (Breadth-First Search) sobre un grafo
* representado con lista de adyacencia.
*
* Complejidad temporal: O(V + E)
* Complejidad espacial: O(V)
*/
public class BFS {
/**
* Realiza un recorrido BFS desde el nodo origen.
* Devuelve un mapa con la distancia (en aristas) desde el origen
* a cada nodo alcanzable.
*
* @param grafo grafo representado con lista de adyacencia
* @param origen nodo de inicio del recorrido
* @return mapa {nodo → distancia desde origen}
*/
public static Map<Integer, Integer> bfs(GrafoLista grafo, int origen) {
Map<Integer, Integer> distancias = new LinkedHashMap<>();
Queue<Integer> cola = new LinkedList<>();
distancias.put(origen, 0);
cola.add(origen);
while (!cola.isEmpty()) {
int actual = cola.poll();
int distActual = distancias.get(actual);
for (GrafoLista.Arista arista : grafo.obtenerVecinos(actual)) {
int vecino = arista.getDestino();
if (!distancias.containsKey(vecino)) {
distancias.put(vecino, distActual + 1);
cola.add(vecino);
}
}
}
return distancias;
}
/**
* Encuentra el camino más corto (en aristas) entre origen y destino.
*
* @return lista con los nodos del camino, o lista vacía si no hay camino
*/
public static List<Integer> caminoMasCorto(GrafoLista grafo, int origen, int destino) {
Map<Integer, Integer> padre = new LinkedHashMap<>();
Queue<Integer> cola = new LinkedList<>();
padre.put(origen, -1);
cola.add(origen);
while (!cola.isEmpty()) {
int actual = cola.poll();
if (actual == destino) {
break; // encontrado
}
for (GrafoLista.Arista arista : grafo.obtenerVecinos(actual)) {
int vecino = arista.getDestino();
if (!padre.containsKey(vecino)) {
padre.put(vecino, actual);
cola.add(vecino);
}
}
}
// Reconstruir camino desde destino hasta origen
List<Integer> camino = new ArrayList<>();
if (!padre.containsKey(destino)) {
return camino; // no hay camino
}
for (int nodo = destino; nodo != -1; nodo = padre.get(nodo)) {
camino.add(nodo);
}
Collections.reverse(camino);
return camino;
}
public static void main(String[] args) {
GrafoLista grafo = new GrafoLista(false);
grafo.agregarArista(0, 1, 1);
grafo.agregarArista(0, 2, 1);
grafo.agregarArista(1, 3, 1);
grafo.agregarArista(2, 3, 1);
grafo.agregarArista(3, 4, 1);
grafo.agregarArista(4, 5, 1);
System.out.println("=== BFS desde nodo 0 ===");
Map<Integer, Integer> distancias = bfs(grafo, 0);
distancias.forEach((nodo, dist) ->
System.out.println(" Nodo " + nodo + " → distancia " + dist)
);
System.out.println("\nCamino más corto 0 → 5:");
List<Integer> camino = caminoMasCorto(grafo, 0, 5);
System.out.println(" " + camino);
}
}=== BFS desde nodo 0 === Nodo 0 → distancia 0 Nodo 1 → distancia 1 Nodo 2 → distancia 1 Nodo 3 → distancia 2 Nodo 4 → distancia 3 Nodo 5 → distancia 4 Camino más corto 0 → 5: [0, 1, 3, 4, 5]
🔍 Recorrido en profundidad (DFS)
El recorrido DFS (Depth-First Search) explora el grafo avanzando lo más profundo posible por cada rama antes de retroceder (backtracking). Se puede implementar de forma recursiva (usando la pila de llamadas del sistema) o de forma iterativa (usando una pila explícita). DFS es la base de numerosos algoritmos: detección de ciclos, ordenamiento topológico, búsqueda de componentes fuertemente conexas (Tarjan, Kosaraju) y resolución de laberintos.
import java.util.*;
/**
* Implementación de DFS (Depth-First Search).
* Incluye versión recursiva e iterativa.
*
* Complejidad temporal: O(V + E)
* Complejidad espacial: O(V)
*/
public class DFS {
/**
* DFS recursivo. Visita todos los nodos alcanzables desde origen.
*/
public static List<Integer> dfsRecursivo(GrafoLista grafo, int origen) {
List<Integer> orden = new ArrayList<>();
Set<Integer> visitados = new LinkedHashSet<>();
dfsHelper(grafo, origen, visitados, orden);
return orden;
}
private static void dfsHelper(GrafoLista grafo, int nodo,
Set<Integer> visitados, List<Integer> orden) {
visitados.add(nodo);
orden.add(nodo);
for (GrafoLista.Arista arista : grafo.obtenerVecinos(nodo)) {
if (!visitados.contains(arista.getDestino())) {
dfsHelper(grafo, arista.getDestino(), visitados, orden);
}
}
}
/**
* DFS iterativo usando una pila explícita.
* Útil para grafos grandes donde la recursión podría causar
* StackOverflowError.
*/
public static List<Integer> dfsIterativo(GrafoLista grafo, int origen) {
List<Integer> orden = new ArrayList<>();
Set<Integer> visitados = new LinkedHashSet<>();
Deque<Integer> pila = new ArrayDeque<>();
pila.push(origen);
while (!pila.isEmpty()) {
int actual = pila.pop();
if (visitados.contains(actual)) {
continue;
}
visitados.add(actual);
orden.add(actual);
// Añadir vecinos en orden inverso para mantener el orden natural
List<GrafoLista.Arista> vecinos = grafo.obtenerVecinos(actual);
for (int i = vecinos.size() - 1; i >= 0; i--) {
int destino = vecinos.get(i).getDestino();
if (!visitados.contains(destino)) {
pila.push(destino);
}
}
}
return orden;
}
/**
* Detecta si el grafo (dirigido) contiene ciclos usando DFS.
*/
public static boolean tieneCiclo(GrafoLista grafo) {
Set<Integer> visitados = new HashSet<>();
Set<Integer> enPila = new HashSet<>();
for (int nodo : grafo.obtenerVertices()) {
if (detectarCiclo(grafo, nodo, visitados, enPila)) {
return true;
}
}
return false;
}
private static boolean detectarCiclo(GrafoLista grafo, int nodo,
Set<Integer> visitados, Set<Integer> enPila) {
if (enPila.contains(nodo)) return true; // ciclo detectado
if (visitados.contains(nodo)) return false; // ya procesado
visitados.add(nodo);
enPila.add(nodo);
for (GrafoLista.Arista arista : grafo.obtenerVecinos(nodo)) {
if (detectarCiclo(grafo, arista.getDestino(), visitados, enPila)) {
return true;
}
}
enPila.remove(nodo);
return false;
}
public static void main(String[] args) {
GrafoLista grafo = new GrafoLista(false);
grafo.agregarArista(0, 1, 1);
grafo.agregarArista(0, 2, 1);
grafo.agregarArista(1, 3, 1);
grafo.agregarArista(2, 4, 1);
grafo.agregarArista(3, 5, 1);
System.out.println("DFS recursivo desde 0: " + dfsRecursivo(grafo, 0));
System.out.println("DFS iterativo desde 0: " + dfsIterativo(grafo, 0));
}
}DFS recursivo desde 0: [0, 1, 3, 5, 2, 4] DFS iterativo desde 0: [0, 1, 3, 5, 2, 4]
🚀 Algoritmo de Dijkstra: camino más corto en grafos valorados
El algoritmo de Dijkstra (1959, Edsger Dijkstra) es el algoritmo clásico para encontrar el camino de menor coste desde un nodo origen a todos los demás nodos en un grafo con pesos no negativos. Utiliza una estrategia voraz (greedy): en cada paso selecciona el nodo no visitado con menor distancia acumulada y relaja sus aristas vecinas.
La implementación eficiente utiliza una cola de prioridad (PriorityQueue) que permite extraer el nodo de menor distancia en O(log V). La complejidad resultante es O((V + E) log V), significativamente mejor que la versión cuadrática O(V²) que recorre todos los nodos en cada iteración.
import java.util.*;
/**
* Algoritmo de Dijkstra para encontrar caminos de coste mínimo
* desde un nodo origen en un grafo con pesos no negativos.
*
* Complejidad temporal: O((V + E) log V) con PriorityQueue
* Complejidad espacial: O(V)
*/
public class Dijkstra {
/**
* Par (nodo, distancia) para la cola de prioridad.
*/
private static class NodoDistancia implements Comparable<NodoDistancia> {
final int nodo;
final int distancia;
NodoDistancia(int nodo, int distancia) {
this.nodo = nodo;
this.distancia = distancia;
}
@Override
public int compareTo(NodoDistancia otro) {
return Integer.compare(this.distancia, otro.distancia);
}
}
/**
* Ejecuta Dijkstra desde el nodo origen.
*
* @param grafo grafo valorado con pesos no negativos
* @param origen nodo de inicio
* @return mapa {nodo → distancia mínima desde origen}
*/
public static Map<Integer, Integer> dijkstra(GrafoLista grafo, int origen) {
Map<Integer, Integer> distancias = new HashMap<>();
Map<Integer, Integer> predecesores = new HashMap<>();
PriorityQueue<NodoDistancia> cola = new PriorityQueue<>();
// Inicializar distancias a infinito
for (int v : grafo.obtenerVertices()) {
distancias.put(v, Integer.MAX_VALUE);
}
distancias.put(origen, 0);
predecesores.put(origen, -1);
cola.add(new NodoDistancia(origen, 0));
while (!cola.isEmpty()) {
NodoDistancia actual = cola.poll();
// Si la distancia extraída es mayor que la conocida, ignorar
if (actual.distancia > distancias.get(actual.nodo)) {
continue;
}
// Relajar aristas vecinas
for (GrafoLista.Arista arista : grafo.obtenerVecinos(actual.nodo)) {
int vecino = arista.getDestino();
int nuevaDist = actual.distancia + arista.getPeso();
if (nuevaDist < distancias.get(vecino)) {
distancias.put(vecino, nuevaDist);
predecesores.put(vecino, actual.nodo);
cola.add(new NodoDistancia(vecino, nuevaDist));
}
}
}
return distancias;
}
public static void main(String[] args) {
GrafoLista grafo = new GrafoLista(false);
// Red de ciudades con distancias en km
grafo.agregarArista(0, 1, 10); // Madrid - Toledo
grafo.agregarArista(0, 3, 30); // Madrid - Segovia
grafo.agregarArista(1, 2, 50); // Toledo - Valencia
grafo.agregarArista(2, 4, 10); // Valencia - Alicante
grafo.agregarArista(3, 2, 20); // Segovia - Valencia
grafo.agregarArista(3, 4, 60); // Segovia - Alicante
System.out.println("=== Dijkstra desde nodo 0 (Madrid) ===");
Map<Integer, Integer> distancias = dijkstra(grafo, 0);
String[] ciudades = {"Madrid", "Toledo", "Valencia", "Segovia", "Alicante"};
for (Map.Entry<Integer, Integer> e : distancias.entrySet()) {
String dist = e.getValue() == Integer.MAX_VALUE ? "∞" : String.valueOf(e.getValue());
System.out.println(" " + ciudades[e.getKey()] + " → distancia: " + dist);
}
}
}=== Dijkstra desde nodo 0 (Madrid) === Madrid → distancia: 0 Toledo → distancia: 10 Valencia → distancia: 50 Segovia → distancia: 30 Alicante → distancia: 60
🏗️ Ejemplo integrador: red de transporte metropolitano
Este ejemplo combina todos los conceptos del artículo en un escenario realista: un sistema de transporte metropolitano donde las estaciones son nodos, las líneas de metro/bus son aristas, y los tiempos de viaje son los pesos. El programa permite consultar la ruta más rápida entre dos estaciones, las estaciones alcanzables desde un punto y los recorridos BFS/DFS.
import java.util.*;
/**
* Sistema de red de transporte metropolitano.
* Modela estaciones y conexiones como un grafo valorado.
* Permite consultar rutas óptimas usando Dijkstra.
*/
public class RedTransporte {
private final GrafoLista grafo;
private final Map<String, Integer> nombreAId;
private final Map<Integer, String> idANombre;
private int contadorId = 0;
public RedTransporte() {
this.grafo = new GrafoLista(false);
this.nombreAId = new LinkedHashMap<>();
this.idANombre = new LinkedHashMap<>();
}
/**
* Registra una estación en la red.
*/
public void agregarEstacion(String nombre) {
if (!nombreAId.containsKey(nombre)) {
nombreAId.put(nombre, contadorId);
idANombre.put(contadorId, nombre);
grafo.agregarVertice(contadorId);
contadorId++;
}
}
/**
* Conecta dos estaciones con un tiempo de viaje (en minutos).
*/
public void conectar(String estacion1, String estacion2, int minutos) {
agregarEstacion(estacion1);
agregarEstacion(estacion2);
grafo.agregarArista(nombreAId.get(estacion1), nombreAId.get(estacion2), minutos);
}
/**
* Encuentra la ruta más rápida entre dos estaciones.
*/
public String rutaMasRapida(String origen, String destino) {
Integer idOrigen = nombreAId.get(origen);
Integer idDestino = nombreAId.get(destino);
if (idOrigen == null || idDestino == null) {
return "Estación no encontrada.";
}
Map<Integer, Integer> distancias = Dijkstra.dijkstra(grafo, idOrigen);
int tiempo = distancias.getOrDefault(idDestino, Integer.MAX_VALUE);
if (tiempo == Integer.MAX_VALUE) {
return "No hay ruta entre " + origen + " y " + destino;
}
return origen + " → " + destino + ": " + tiempo + " minutos";
}
/**
* Lista las estaciones alcanzables desde una estación dada (BFS).
*/
public List<String> estacionesAlcanzables(String desde) {
Integer id = nombreAId.get(desde);
if (id == null) return Collections.emptyList();
Map<Integer, Integer> distancias = BFS.bfs(grafo, id);
List<String> resultado = new ArrayList<>();
for (int nodo : distancias.keySet()) {
if (nodo != id) {
resultado.add(idANombre.get(nodo));
}
}
return resultado;
}
public static void main(String[] args) {
RedTransporte metro = new RedTransporte();
// Línea 1: Sol — Atocha — Retiro — Príncipe de Vergara
metro.conectar("Sol", "Atocha", 3);
metro.conectar("Atocha", "Retiro", 2);
metro.conectar("Retiro", "Príncipe de Vergara", 2);
// Línea 2: Sol — Gran Vía — Tribunal — Alonso Martínez
metro.conectar("Sol", "Gran Vía", 1);
metro.conectar("Gran Vía", "Tribunal", 2);
metro.conectar("Tribunal", "Alonso Martínez", 1);
// Línea 3: Atocha — Embajadores — Lavapiés
metro.conectar("Atocha", "Embajadores", 2);
metro.conectar("Embajadores", "Lavapiés", 1);
// Conexión entre líneas: Alonso Martínez — Retiro
metro.conectar("Alonso Martínez", "Retiro", 4);
System.out.println("=== Red de Transporte Metropolitano ===\n");
System.out.println(metro.rutaMasRapida("Lavapiés", "Príncipe de Vergara"));
System.out.println(metro.rutaMasRapida("Gran Vía", "Retiro"));
System.out.println(metro.rutaMasRapida("Sol", "Alonso Martínez"));
System.out.println("\nEstaciones alcanzables desde Atocha:");
for (String est : metro.estacionesAlcanzables("Atocha")) {
System.out.println(" • " + est);
}
}
}=== Red de Transporte Metropolitano === Lavapiés → Príncipe de Vergara: 8 minutos Gran Vía → Retiro: 6 minutos Sol → Alonso Martínez: 4 minutos Estaciones alcanzables desde Atocha: • Sol • Retiro • Embajadores • Príncipe de Vergara • Gran Vía • Lavapiés • Tribunal • Alonso Martínez
⚠️ Errores frecuentes al trabajar con grafos
Error 1: No marcar nodos como visitados en BFS/DFS
// ❌ ERROR: No se usa un conjunto de visitados
public static void bfsMal(GrafoLista grafo, int origen) {
Queue<Integer> cola = new LinkedList<>();
cola.add(origen);
while (!cola.isEmpty()) {
int actual = cola.poll();
System.out.println(actual);
for (GrafoLista.Arista a : grafo.obtenerVecinos(actual)) {
cola.add(a.getDestino()); // ¡Añade vecinos ya visitados!
}
}
}// ✅ CORRECTO: Se usa un Set para evitar revisitar nodos
public static void bfsBien(GrafoLista grafo, int origen) {
Set<Integer> visitados = new HashSet<>();
Queue<Integer> cola = new LinkedList<>();
visitados.add(origen);
cola.add(origen);
while (!cola.isEmpty()) {
int actual = cola.poll();
System.out.println(actual);
for (GrafoLista.Arista a : grafo.obtenerVecinos(actual)) {
if (!visitados.contains(a.getDestino())) {
visitados.add(a.getDestino());
cola.add(a.getDestino());
}
}
}
}Explicación: Sin un conjunto de nodos visitados, el recorrido puede entrar en un bucle infinito al re-encolar nodos que ya fueron procesados. Esto ocurre siempre que el grafo contiene ciclos, que es el caso más habitual en la práctica.
Error 2: Usar Dijkstra con pesos negativos
// ❌ ERROR: El grafo tiene arista con peso negativo
grafo.agregarArista(0, 1, 5);
grafo.agregarArista(1, 2, -3); // ¡Peso negativo!
grafo.agregarArista(0, 2, 4);
// Dijkstra puede devolver distancia 4 para nodo 2,
// pero el camino 0→1→2 cuesta solo 2.
// Dijkstra no revisita nodos, así que pierde la mejora.Solución: Si hay pesos negativos (pero no ciclos negativos), usar el algoritmo de Bellman-Ford, cuya complejidad es O(V·E).
Error 3: Confundir grafo dirigido con no dirigido en la representación
// ❌ ERROR: Se olvida de añadir la arista inversa
// para un grafo no dirigido
int[][] matriz = new int[5][5];
matriz[0][1] = 10; // Falta: matriz[1][0] = 10;// ✅ CORRECTO: Arista bidireccional
matriz[0][1] = 10;
matriz[1][0] = 10; // Grafo no dirigido: simétricoExplicación: En un grafo no dirigido, la matriz de adyacencia debe ser simétrica. Olvidar añadir la arista inversa es uno de los errores más comunes y difíciles de depurar, porque el grafo "funciona" parcialmente pero produce resultados incorrectos en ciertos caminos.
✏️ Ejercicios prácticos
Ejercicio 1 — Análisis de recorridos (comprensión)
Dado el siguiente grafo no dirigido:
Aristas: (0,1), (0,2), (1,3), (1,4), (2,4), (3,5), (4,5)
a) ¿Cuál es el orden de visita en un BFS desde el nodo 0?
b) ¿Cuál es el camino más corto (en aristas) de 0 a 5?
c) ¿Cuál es el grado de cada nodo?
Ejercicio 2 — Implementar grafo con nombres (aplicación)
Implementa una clase GrafoNombres que permita crear un grafo donde los nodos se identifiquen por nombre (String) en lugar de por número. La clase debe soportar:
— Añadir nodos por nombre.
— Conectar dos nodos por nombre con un peso.
— Obtener los vecinos de un nodo por nombre.
— Verificar si dos nodos están conectados.
Prueba tu implementación modelando un grafo de ciudades españolas con distancias reales.
Ejercicio 3 — Detectar componentes conexas (diseño)
Implementa un método componentesConexas(GrafoLista grafo) que devuelva una lista de listas, donde cada sublista contiene los nodos de una componente conexa del grafo. Usa BFS o DFS como herramienta interna.
Ejemplo: para un grafo con aristas {(0,1), (1,2), (3,4)}, el resultado debe ser [[0, 1, 2], [3, 4]].
❓ Preguntas frecuentes sobre Grafos en Java
Las dudas más comunes respondidas de forma clara y directa.
💬 Foro de discusión
¿Tienes dudas sobre Grafos en Java? Comparte tu pregunta con la comunidad.
Todavía no hay mensajes. ¡Sé el primero en participar!