Grafos: Matriz, Lista de Adyacencia, BFS, DFS y Dijkstra
Respondé todas las preguntas y presioná Calificar para ver tu puntaje.
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)$.
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.
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)$.
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.
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).
¿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.
Set<Vertice> visitados
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.
Set
¿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*).
Puntaje: