← Volver a actividades
Autoevaluación

Autoevaluación: Grafos, Representaciones, BFS, DFS y Dijkstra

Grafos: Matriz, Lista de Adyacencia, BFS, DFS y Dijkstra

Respondé todas las preguntas y presioná Calificar para ver tu puntaje.

1. Para un grafo disperso (con pocos aristas en relación a la cantidad de vértices), ¿por qué es preferible usar una Lista de Adyacencia en lugar de una Matriz de Adyacencia?
Correcto Incorrecto Sin responder

Respuesta correcta: Porque la lista de adyacencia consume O(V + E) en memoria, mientras que la matriz consume O(V^2) desperdiciando espacio en ceros o celdas vacías.

¿Por qué? En redes del mundo real con miles de vértices y pocas conexiones (grafos dispersos), una matriz de $100.000 \times 100.000$ exigiría $10^{10}$ posiciones de memoria (inviable), mientras que la lista de adyacencia solo almacena las aristas existentes en espacio $O(V + E)$.

2. La Búsqueda en Anchura (BFS) garantiza encontrar el camino más corto en cantidad de aristas (o saltos) entre dos nodos en cualquier grafo no ponderado.
Correcto Incorrecto Sin responder

Respuesta correcta: Verdadero

¿Por qué? Verdadero. Al explorar exhaustivamente por niveles concéntricos (primero a distancia 1, luego distancia 2, etc.) mediante una Cola FIFO, el primer momento en que BFS alcanza el nodo destino corresponde necesariamente al camino con menor número de saltos.

3. ¿Qué estructura de datos es el motor fundamental para implementar el algoritmo de Dijkstra de forma eficiente?
Correcto Incorrecto Sin responder

Respuesta correcta: Una Cola de Prioridad (PriorityQueue / Min-Heap).

¿Por qué? Dijkstra es un algoritmo codicioso (*greedy*) que en cada paso extrae el nodo no visitado con la menor distancia acumulada hasta el momento. La Cola de Prioridad permite extraer este mínimo en tiempo $O(\log V)$.

4. El algoritmo de Dijkstra funciona correctamente y garantiza la ruta óptima incluso si el grafo contiene aristas con pesos negativos.
Correcto Incorrecto Sin responder

Respuesta correcta: Falso

¿Por qué? Falso. Dijkstra asume que una vez que un nodo es extraído de la cola de prioridad con la distancia mínima actual, su costo nunca podrá reducirse en el futuro. Si existen aristas negativas, esta premisa se rompe (pudiendo existir ciclos de costo negativo). Para aristas negativas se debe recurrir al algoritmo de Bellman-Ford.

5. ¿Cuál es la principal diferencia funcional entre BFS (Búsqueda en Anchura) y DFS (Búsqueda en Profundidad)?
Correcto Incorrecto Sin responder

Respuesta correcta: BFS explora nivel por nivel usando una Cola; DFS desciende por una rama hasta el fondo antes de retroceder (backtracking) usando una Pila o recursión.

¿Por qué? BFS se expande radialmente en amplitud mediante una Cola (FIFO), mientras que DFS profundiza por un camino hasta no poder avanzar más utilizando la pila de llamadas o una estructura Pila explícita (LIFO).

6. En un grafo no dirigido, si existe una arista entre el nodo A y el nodo B, la lista de adyacencia debe registrar a B como vecino de A, y también a A como vecino de B.
Correcto Incorrecto Sin responder

Respuesta correcta: Verdadero

¿Por qué? Verdadero. En un grafo no dirigido la relación es simétrica y bidireccional; por ende, la conexión debe representarse en las listas de vecinos de ambos vértices.

7. ¿Qué mecanismo es indispensable incluir en BFS y DFS al recorrer un grafo con ciclos para evitar bucles infinitos?
Correcto Incorrecto Sin responder

Respuesta correcta: Una colección de nodos visitados (Set<Vertice> visitados) para no volver a encolar o procesar vértices ya explorados.

¿Por qué? Como los grafos pueden tener ciclos o múltiples caminos hacia un mismo vértice, registrar los nodos visitados en un Set impide entrar en un bucle infinito y garantiza que cada vértice se procese una sola vez.

8. En un grafo dirigido, el "grado de entrada" de un vértice es la cantidad de aristas que llegan a él, y el "grado de salida" es la cantidad de aristas que parten de él.
Correcto Incorrecto Sin responder

Respuesta correcta: Verdadero

¿Por qué? Verdadero. A diferencia de un grafo no dirigido donde solo existe el concepto de grado (total de aristas incidentes), en grafos dirigidos se distingue entre grado de entrada (*in-degree*) y grado de salida (*out-degree*).