Necesitas un orden para instalar paquetes dadas relaciones 'A depende de B'. ¿Qué algoritmo usas?
Opciones
- Búsqueda binaria en la lista de paquetes
- Ordenación topológica (algoritmo de Kahn o DFS) en un DAG (Opción correcta)
- Algoritmo de Kruskal para un árbol de expansión mínima
- Quickselect sobre el número de dependencias
Respuesta
Ordenación topológica (algoritmo de Kahn o DFS) en un DAG
Por qué
Las dependencias forman un grafo dirigido. Una ordenación topológica lista los nodos de modo que cada uno aparezca después de todo aquello de lo que depende.
Algoritmo de Kahn: toma repetidamente un nodo sin dependencias pendientes (in-degree 0), añádelo a la salida y quita sus aristas.
Si algunos nodos nunca quedan libres, hay un ciclo (dependencia circular) y no existe un orden válido.
Recuerda
Orden con dependencias → ordenación topológica.