Generado con IA · Supuesto práctico

Estructuras de datos y algoritmos: el grafo de dependencias de los módulos y el camino más corto en el campus

Caso único con preguntas Informática Comunidad Valenciana
Descargar:
Supuesto práctico generado por la IA de OposicionesIA, con su orientación y solución modelo más abajo. Dentro de la plataforma, además, puedes resolverlo y recibir una corrección con rúbrica y nota.

Estructuras de datos y algoritmos: el grafo de dependencias de los módulos y el camino más corto en el campus

Contexto

En el módulo de Programación / Sistemas Informáticos (DAM) se modela el plano del centro como un grafo no dirigido y ponderado: los vértices son ubicaciones (aulas, conserjería, biblioteca, taller) y las aristas son pasillos con su distancia en metros. El objetivo es calcular el camino más corto desde la conserjería a cualquier otra ubicación para guiar a un robot mensajero. Se usa este grafo de ejemplo (peso = metros):

A (Conserjería) --4-- B (Aula 1)
A --2-- C (Biblioteca)
C --1-- B
B --5-- D (Taller)
C --8-- D
B --10-- E (Gimnasio)
D --2-- E

Cuestiones

1. Representación y justificación. Representa el grafo de dos formas: como matriz de adyacencia y como lista de adyacencia. Indica el espacio que ocupa cada una en función del número de vértices V y de aristas E (O(V²) frente a O(V+E)) y justifica cuál elegirías para el plano de un centro real, sabiendo que es un grafo disperso (pocos pasillos por ubicación). ¿En qué situación sería preferible la matriz?

2. Recorridos BFS y DFS. Partiendo del vértice A y visitando los vecinos en orden alfabético, indica el orden de visita de un recorrido en anchura (BFS) y de uno en profundidad (DFS). Para el BFS describe el papel de la cola y para el DFS el de la pila (o la recursión). Indica la complejidad temporal de ambos recorridos sobre lista de adyacencia y justifica por qué es O(V+E).

3. Dijkstra paso a paso. Aplica el algoritmo de Dijkstra desde A para obtener la distancia mínima a todos los demás vértices. Presenta una tabla de la traza: en cada iteración indica el vértice que se extrae (el de menor distancia provisional no visitado), las distancias que se relajan y el conjunto de visitados. Da la distancia final a cada vértice y reconstruye el camino más corto de A a E (la secuencia de vértices). Razona por qué Dijkstra no admite aristas de peso negativo.

4. Complejidad y estructura auxiliar. Justifica la complejidad de Dijkstra según la estructura usada para extraer el mínimo: O(V²) con búsqueda lineal frente a O((V+E)·log V) con una cola de prioridad (montículo binario). ¿Cuál conviene para un grafo disperso y grande? Explica qué operación del montículo da el factor log V.

5. Tabla hash (estructura alternativa). Para localizar rápidamente un vértice por su nombre ("Biblioteca") se usa una tabla hash nombre → índice. (a) Explica qué es una colisión y compara encadenamiento separado frente a direccionamiento abierto. (b) Si el factor de carga crece y degrada el rendimiento, ¿qué operación se realiza y cómo afecta al coste? (c) Justifica por qué el coste medio de búsqueda es O(1) pero el peor caso es O(n), y de qué depende.

Orientación cómo resolverlo por tu cuenta

Este supuesto recorre la teoría de grafos del bloque de estructuras de datos. Aborda cada cuestión con método.

Cuestión 1 (representaciones). Recuerda las dos estructuras canónicas: matriz V×V (celda = peso o ∞/0) y lista de adyacencia (un contenedor por vértice con sus pares vecino-peso). Compara su coste espacial razonando cuántas celdas/nodos genera cada una; relaciona la elección con la densidad del grafo (E cercano a V² → denso; E del orden de V → disperso). No olvides que en grafo no dirigido cada arista aparece dos veces en la lista. Error típico: olvidar la simetría de la matriz o confundir coste espacial con temporal.

Cuestión 2 (BFS/DFS). Repasa que BFS explora por niveles con una cola FIFO (marca al encolar) y DFS por ramas con pila LIFO o recursión. La clave del orden es respetar el criterio alfabético al elegir vecinos. Justifica la complejidad contando: cada vértice se procesa una vez y cada arista se examina dos veces. Error típico: revisitar vértices ya marcados o desordenar los vecinos.

Cuestión 3 (Dijkstra). Plantea la traza con columnas: vértice extraído, distancias provisionales y conjunto de visitados. En cada paso extrae el no visitado de menor distancia y relaja sus aristas (compara distancia actual con la suma por el nuevo camino). Mantén un vector de predecesores para reconstruir el camino hacia atrás. Razona la prohibición de pesos negativos a partir de la hipótesis greedy (una vez fijado un vértice, no mejora). Error típico: relajar desde un vértice aún no consolidado.

Cuestión 4 (complejidad). Distingue la implementación con búsqueda lineal del mínimo frente a cola de prioridad (montículo binario). Identifica qué operación aporta el factor logarítmico y relaciona la elección con la densidad.

Cuestión 5 (hash). Define colisión y contrasta encadenamiento separado frente a direccionamiento abierto; conecta factor de carga con el rehashing y explica por qué el caso medio es O(1) y el peor O(n). Error típico: confundir factor de carga con tamaño.

Solución modelo respuesta completa — intenta resolverlo antes de mirar

Cuestión 1 — Representación y justificación

Datos del grafo (no dirigido, ponderado): V = 5 vértices {A, B, C, D, E} y E = 6 aristas: A–B(4), A–C(2), C–B(1), B–D(5), C–D(8), B–E(10), D–E(2). En realidad son 7 aristas (corrijo el recuento: A–B, A–C, C–B, B–D, C–D, B–E, D–E ⇒ E = 7).

Matriz de adyacencia (simétrica; 0 = sin arista, en la diagonal; valores = metros):

      A    B    C    D    E
A  [  0    4    2    -    -  ]
B  [  4    0    1    5   10  ]
C  [  2    1    0    8    -  ]
D  [  -    5    8    0    2  ]
E  [  -   10    -    2    0  ]

(El guion - representa ausencia de pasillo; en código se almacena como ∞ para Dijkstra o 0 para la mera existencia.) Ocupa V² = 25 celdas → coste espacial O(V²), independiente de cuántas aristas existan.

Lista de adyacencia (cada vértice apunta a sus pares vecino-peso; por ser no dirigido cada arista aparece dos veces):

A -> [ (B,4), (C,2) ]
B -> [ (A,4), (C,1), (D,5), (E,10) ]
C -> [ (A,2), (B,1), (D,8) ]
D -> [ (B,5), (C,8), (E,2) ]
E -> [ (B,10), (D,2) ]

Almacena V cabeceras + 2E nodos → coste espacial O(V + E).

Justificación de la elección. El plano de un centro real es un grafo disperso: cada ubicación conecta con pocos pasillos, de modo que E es del orden de V y muy inferior a V². La matriz desperdiciaría memoria almacenando ceros (O(V²)), mientras que la lista crece linealmente con lo que de verdad existe (O(V+E)) y permite recorrer los vecinos de un vértice en tiempo proporcional a su grado. Por tanto se elige la lista de adyacencia.

La matriz sería preferible en grafos densos (E ≈ V²), o cuando la operación dominante es consultar si existe arista entre dos vértices concretos, pues la matriz responde en O(1) frente al O(grado) de la lista; también facilita operaciones algebraicas (multiplicación de matrices para caminos, potencias de adyacencia).

Cuestión 2 — Recorridos BFS y DFS

Vecinos en orden alfabético. Partimos de A.

BFS (anchura) — papel de la COLA (FIFO): se encola A y se marca como visitado. Se desencola un vértice, se procesan sus vecinos no visitados (en orden alfabético) marcándolos y encolándolos. Así se exploran primero todos los vértices a distancia 1, luego los de distancia 2, etc. (exploración por niveles).

Cola inicial: [A]                       Visita: A
Desencola A -> encola B, C              Cola: [B, C]      Visita: A B
Desencola B -> vecinos A(✓) C(en cola) D, E -> encola D, E   Cola: [C, D, E]  Visita: A B C
Desencola C -> vecinos A(✓) B(✓) D(en cola)                  Cola: [D, E]
Desencola D -> vecinos B(✓) C(✓) E(en cola)                  Cola: [E]
Desencola E -> vecinos B(✓) D(✓)                             Cola: []

Orden BFS: A, B, C, D, E.

DFS (profundidad) — papel de la PILA (LIFO) o recursión: desde A se desciende por el primer vecino no visitado (alfabético), y solo cuando una rama se agota se retrocede (backtracking) al vértice anterior. Con recursión la propia pila de llamadas hace de pila explícita.

A -> primer vecino B
B -> primer vecino no visitado C
C -> primer vecino no visitado D     (A,B ya visitados)
D -> primer vecino no visitado E     (B,C ya visitados)
E -> sin vecinos nuevos -> backtrack hasta agotar

Orden DFS: A, B, C, D, E. (Coincide con BFS en este grafo concreto por el encadenamiento alfabético, pero conceptualmente difieren: BFS por niveles, DFS por ramas.)

Complejidad — O(V + E) sobre lista de adyacencia. Cada vértice se marca y se procesa una sola vez (lo cubre la marca de visitado): aporta O(V). Al procesar cada vértice se recorre su lista de adyacencia; sumando los grados de todos los vértices se examinan 2E referencias (cada arista no dirigida se ve dos veces): aporta O(E). El total es O(V + E), lineal en el tamaño del grafo. (Con matriz de adyacencia sería O(V²), pues hallar los vecinos de cada vértice exige recorrer una fila completa de V celdas.)

Cuestión 3 — Dijkstra paso a paso desde A

Inicialización: dist(A)=0, resto = ∞. Conjunto de visitados S = {}. Vector de predecesores prev.

Tabla de la traza (en cada iteración se extrae el vértice no visitado de menor distancia y se relajan sus aristas):

Iter Extrae (dist) Relajaciones dist[A,B,C,D,E] Visitados S
0 — (init) — [0, ∞, ∞, ∞, ∞] { }
1 A (0) B←0+4=4 (prev=A); C←0+2=2 (prev=A) [0, 4, 2, ∞, ∞] {A}
2 C (2) B←min(4, 2+1=3)=3 (prev=C); D←2+8=10 (prev=C) [0, 3, 2, 10, ∞] {A,C}
3 B (3) D←min(10, 3+5=8)=8 (prev=B); E←3+10=13 (prev=B) [0, 3, 2, 8, 13] {A,C,B}
4 D (8) E←min(13, 8+2=10)=10 (prev=D) [0, 3, 2, 8, 10] {A,C,B,D}
5 E (10) (sin mejoras) [0, 3, 2, 8, 10] {A,C,B,D,E}

Distancias finales desde A:

dist(A) = 0
dist(B) = 3     (A -> C -> B)
dist(C) = 2     (A -> C)
dist(D) = 8     (A -> C -> B -> D)
dist(E) = 10    (A -> C -> B -> D -> E)

Reconstrucción del camino más corto de A a E usando prev hacia atrás: E ← prev(E)=D ← prev(D)=B ← prev(B)=C ← prev(C)=A. Invertido: A → C → B → D → E, con coste 2 + 1 + 5 + 2 = 10 metros. (Obsérvese que el camino directo B→E pesaba 10, pero rodeando por D se obtiene también 10; y que la arista A–B(4) nunca se usa porque llegar a B por C cuesta solo 3.)

Por qué Dijkstra no admite pesos negativos. Dijkstra es un algoritmo voraz que se basa en una invariante: cuando un vértice se extrae y se añade a S, su distancia es definitiva y no podrá mejorarse después. Esto solo es cierto si todos los pesos son ≥ 0, porque entonces cualquier camino alternativo que pase por vértices aún no fijados solo puede sumar distancia. Con una arista negativa, un camino más largo en número de saltos podría reducir el coste después de haber consolidado el vértice, violando la invariante y produciendo distancias erróneas. Para pesos negativos (sin ciclos negativos) debe usarse Bellman-Ford (O(V·E)).

Cuestión 4 — Complejidad y estructura auxiliar

Dijkstra repite V veces dos tareas: (1) extraer el mínimo de las distancias provisionales y (2) relajar las aristas del vértice extraído. El coste global depende de cómo se implemente la extracción del mínimo:

  • Búsqueda lineal (array sin estructura auxiliar): extraer el mínimo recorre los V candidatos ⇒ V extracciones × O(V) = O(V²); las relajaciones suman O(E) (acceso directo al array, O(1) cada una). Total O(V² + E) = O(V²).

  • Cola de prioridad (montículo binario / min-heap): la extracción del mínimo (extract-min) y la actualización de prioridad (decrease-key) cuestan O(log V). Hay V extracciones y hasta E relajaciones, cada una con una operación de heap ⇒ O((V + E)·log V).

¿Cuál conviene? Para un grafo disperso y grande (E del orden de V, como el plano del centro), la versión con montículo da O((V+E)·log V) ≈ O(V·log V), mucho mejor que O(V²). En cambio, para un grafo muy denso (E ≈ V²) la versión lineal O(V²) puede igualar o superar a la del heap (O(V²·log V)), por lo que allí no compensa el montículo.

Operación que aporta el factor log V. Las operaciones del montículo binario —extract-min (reordenar tras quitar la raíz, sift-down) y decrease-key/inserción (sift-up)— se propagan a lo largo de la altura del árbol, que es ⌊log₂ V⌋. De ahí el factor log V que multiplica al número de operaciones.

Cuestión 5 — Tabla hash (estructura alternativa)

Se mapea nombre → índice con una función hash h(clave) que devuelve una posición en un array de tamaño m.

(a) Colisión y estrategias de resolución. Una colisión ocurre cuando dos claves distintas producen el mismo índice (h(k1) = h(k2)); es inevitable porque el espacio de claves es mayor que el de posiciones (principio del palomar).

  • Encadenamiento separado (separate chaining): cada cubeta es una lista enlazada (o estructura dinámica) que guarda todos los elementos que colisionan en ese índice. Ventajas: simple, soporta factor de carga > 1, el borrado es trivial. Inconveniente: memoria extra por los punteros y peor localidad de caché.
  • Direccionamiento abierto (open addressing): todos los elementos viven dentro del propio array; ante colisión se busca otra celda libre mediante sondeo (lineal, cuadrático o doble hashing). Ventajas: mejor localidad de caché, sin punteros. Inconvenientes: exige factor de carga < 1, sufre agrupamiento (clustering) y el borrado requiere marcas tombstone.

(b) Factor de carga y rehashing. El factor de carga es α = n / m (elementos almacenados / tamaño de la tabla). Cuando α supera un umbral (típicamente 0,75) el número de colisiones crece y el rendimiento se degrada. La operación que se realiza es el rehashing (redimensionado): se crea una tabla nueva más grande (habitualmente se duplica m) y se reinsertan todos los elementos recalculando h(k) mod m'. Un rehash concreto cuesta O(n), pero como se hace de forma esporádica (al duplicar), su coste amortizado por inserción sigue siendo O(1). El efecto es restaurar un α bajo y, con él, el coste medio constante.

(c) Coste medio O(1) frente a peor caso O(n). Con una buena función hash que distribuya las claves de forma uniforme y un factor de carga acotado, cada cubeta contiene en media ≈ α elementos (una constante), de modo que insertar, buscar o borrar cuesta O(1) en promedio. El peor caso es O(n): si todas las claves colisionan en la misma cubeta (función hash pésima, datos adversarios o muchas colisiones), la búsqueda degenera en recorrer una lista/secuencia de sondeo de longitud n. Por tanto el coste depende de la calidad de la función hash y del factor de carga: con dispersión uniforme y α bajo se mantiene O(1); con mala dispersión o tabla saturada degenera a O(n).

Practica con supuestos como este

Genera supuestos de tu especialidad y comunidad en cualquiera de los cuatro formatos, resuélvelos y recibe corrección con nota al instante.

Crear cuenta Ver planes

🍪 Esta web usa cookies

Utilizamos cookies técnicas imprescindibles para el funcionamiento del sitio y, con tu consentimiento, cookies analíticas para medir el uso (Google Analytics). Puedes aceptar todas, rechazarlas o configurar tu elección. Consulta nuestra Política de cookies.

Configuración de cookies

Elige qué categorías de cookies deseas permitir. Puedes cambiar tu elección en cualquier momento desde el enlace "Configurar cookies" del pie de página.