GUÍA 26-10-26 Estructuras de Datos

CN122 · lunes 26/10/2026 · 13:00-14:15 · Sesión 22

Grafos: representación y recorridos

DEFINICIÓN

Un grafo G = (V, E) es un conjunto de vértices y un conjunto de aristas que los conectan. Es la estructura más general del curso: listas y árboles son casos particulares de grafo.

• Dirigido o no dirigido, según si las aristas tienen sentido.
• Ponderado, si las aristas llevan peso.
• Denso o disperso, según cuántas aristas haya respecto al máximo posible.

MATRIZ DE ADYACENCIA

• Matriz V×V donde la celda [i][j] indica si hay arista de i a j.
• Consultar si existe una arista: O(1).
• Espacio: O(V²) siempre, haya o no aristas.
• Recorrer los vecinos de un vértice: O(V), aunque tenga dos.

LISTA DE ADYACENCIA

• Un arreglo de listas ligadas: cada vértice guarda la lista de sus vecinos.
• Espacio: O(V + E), proporcional a lo que realmente hay.
• Recorrer vecinos: O(grado), que es lo óptimo.
• Consultar una arista específica: O(grado), peor que la matriz.

CUÁL ELEGIR

Si el grafo es denso o se consultan aristas puntuales, matriz. Si es disperso o el algoritmo recorre vecinos —que es el caso de casi todos—, lista. Los grafos del mundo real suelen ser dispersos, así que la lista domina en la práctica.

RECORRIDO EN PROFUNDIDAD (DFS)

Se avanza tan lejos como se pueda antes de retroceder. Usa una pila, explícita o la de la recursión. Sirve para detectar ciclos, ordenar topológicamente y hallar componentes conexas.

RECORRIDO EN ANCHURA (BFS)

Se visitan todos los vecinos antes de avanzar un nivel. Usa una cola. En un grafo no ponderado encuentra el camino más corto en número de aristas.

La única diferencia entre ambos es la estructura auxiliar: pila contra cola. Es la mejor evidencia de que elegir la estructura es elegir el algoritmo.

PRÁCTICA

Representar un grafo en ambas formas e implementar DFS y BFS con marcado de visitados.