6. Grafos

Un grafo es vértices y aristas. Los nodos de listas enlazadas son un caso degenerado (cadena); acá cada vértice puede tener muchas aristas salientes.

Representación

Matriz (n×n)

     0  1  2  3
 0 [ 0  1  0  1 ]
 1 [ 1  0  1  0 ]
 2 [ 0  1  0  1 ]
 3 [ 1  0  1  0 ]

Consulta "¿hay arista i→j?": O(1)
Memoria: O(n²)

Lista por vértice

0: → 1 → 3
1: → 0 → 2
2: → 1 → 3
3: → 0 → 2

Vecinos de v: O(grado(v))
Memoria: O(V + E)

En Java, List<List<Integer>> ady o Map<V, List<V>> son patrones habituales. Para pesos: List<Arista> o mapa de listas de pares (vecino, peso).

BFS y DFS

BFS (cola): capas por distancia en grafos no ponderados — útil para el camino mínimo en número de aristas. DFS (pila o recursión): explora hondo; base para detectar ciclos, componentes conexas, orden topológico.

Esquema BFS (pseudocódigo Java)

JAVA

  Queue<Integer> q = new ArrayDeque<>(); 
  boolean[] visitado = new boolean[n]; 
  q.add(origen); 
  visitado[origen] = true; 
  while (!q.isEmpty()) { 
      int v = q.poll(); 
      for (int w : ady.get(v)) { 
          if (!visitado[w]) { 
              visitado[w] = true; 
              q.add(w); 
          } 
      } 
  } 

Camino mínimo con pesos: Dijkstra

Aristas con peso no negativo; mantiene distancias provisorias y va «relajando» con una cola de prioridad. Complejidad típica O((V + E) log V) con binary heap.

dist[s] = 0, resto = ∞
Extraer vértice u con menor dist provisoria
Para cada arista u→v con peso w:
    si dist[u] + w < dist[v]  →  dist[v] = dist[u] + w  (relajar)

Herramientas que usarás en Java (resumen del curso)

Clases y objetos: cada nodo, vértice o entrada de tabla es un objeto.
Interfaces: contratos insertar, relajar, vecinos, etc.
Visualgo.net para anclar la intuición mientras depurás referencias en el IDE.

Recordá: en Java no hay punteros explícitos; las variables de tipo referencia son el enlace entre nodos en memoria.

Contenido

📚 Elige un curso