Conviene conocer TAD, Map y Set a nivel básico. No necesitas dominar árboles binarios para modelar un grafo.
CONTENIDO ORIGINAL
Avanza en orden. Cada lección está redactada para Palta es Cool, utiliza ejemplos propios y termina con una actividad cuya respuesta puedes desplegar.
ANTES DE EMPEZAR
Ubícate antes de avanzar
Al terminar deberías poder relacionar Vértices y aristas con Matriz de adyacencia y resolver un caso nuevo.
Reserva entre 35 y 55 minutos para lectura, ejemplos, tres comprobaciones y cierre.
04 / PREPARA EL LABORATORIO
Instala un JDK actual y utiliza un editor o IDE con soporte para Java. Trabaja en un proyecto de laboratorio separado.
Abrir la guía de herramientas →Diagnóstico rápido: ¿cómo se relacionan Vértices y aristas y Matriz de adyacencia? ＋
No necesitas acertar todavía. Escribe una hipótesis de dos líneas y compárala con tu respuesta al finalizar; si puedes corregirla y justificar el cambio, hubo aprendizaje.
Aprende el tema paso a paso
Traducirás redes reales a vértices y aristas y elegirás una representación según densidad y operaciones.
Al terminar podrás
- Un grafo representa entidades y conexiones
- La matriz de adyacencia favorece consultas directas
- Las listas de adyacencia guardan solo conexiones existentes
01
Modelo
Un grafo representa entidades y conexiones
Los vértices representan objetos y las aristas relaciones. Una arista puede ser dirigida o no dirigida y puede tener peso. Antes de programar hay que precisar qué significa la dirección, si se permiten lazos o aristas repetidas y qué unidad usa el peso. Un camino es una secuencia de vértices unidos por aristas válidas.
Orden |V|: cantidad de vértices.
Tamaño |E|: cantidad de aristas.
Grado: conexiones incidentes; en un grafo dirigido se separa en grado de entrada y de salida.
¿Una arista con peso 0 significa siempre que no existe?
Mostrar respuesta ＋
No. Cero puede ser un peso válido; conviene representar ausencia de arista de forma separada cuando el dominio admite ese valor.
02
Matriz
La matriz de adyacencia favorece consultas directas
Una matriz V × V permite consultar si u conecta con v en O(1), pero ocupa O(V²) aunque existan pocas aristas. En un grafo no dirigido la matriz es simétrica. Agregar vértices suele requerir redimensionar toda la estructura.
Fila: origen; columna: destino.
No dirigido: m[u][v] y m[v][u] coinciden.
Adecuada para grafos densos o vértices estables.
¿Qué costo espacial tiene una matriz para V vértices?
Mostrar respuesta ＋
O(V²), independiente de la cantidad real de aristas.
03
Lista
Las listas de adyacencia guardan solo conexiones existentes
Cada vértice conserva una colección de vecinos, con costo O(V + E). Recorrer vecinos es eficiente y resulta apropiado para grafos dispersos. La identidad de un vértice debe implementar equals y hashCode de forma coherente si se usa en mapas o conjuntos.
Dirigido: almacena vecinos salientes.
No dirigido: registra ambas direcciones o define una arista compartida.
Elige List o Set según repeticiones y consultas.
¿Qué representación suele ser más compacta cuando E es mucho menor que V²?
Mostrar respuesta ＋
Una lista de adyacencia, porque almacena los vértices y las aristas que realmente existen.
Tu recorrido en tres ideas
- Un grafo representa entidades y conexiones
- La matriz de adyacencia favorece consultas directas
- Las listas de adyacencia guardan solo conexiones existentes
CIERRE DE LA SECCIÓN
Comprueba que puedes usarlo
Antes de continuar, revisa estos tropiezos frecuentes y resuelve un caso sin copiar los ejemplos.
Usar cero para ausencia cuando cero es un peso válido.
Duplicar aristas de un grafo no dirigido sin definir su identidad.
Ahora hazlo sin guía
Modela una red de transporte y constrúyela como matriz y lista de adyacencia.
Mostrar pauta de corrección ＋
Una respuesta sólida:
- Define dirección, peso y unidad.
- Compara espacio y operaciones.
- Valida vértices antes de agregar aristas.