You need an order to install packages given 'A depends on B' relations. Algorithm?
Options
- Binary search on the list of packages
- Topological sort (Kahn's algorithm or DFS) on a DAG (Correct option)
- Kruskal's algorithm for a minimum spanning tree
- Quickselect on the number of dependencies
Answer
Topological sort (Kahn's algorithm or DFS) on a DAG
Why
Dependencies form a directed graph. A topological sort lists the nodes so every node comes after everything it depends on.
Kahn's algorithm: repeatedly take a node with no remaining dependencies (in-degree 0), output it, and remove its edges.
If some nodes are never freed, there is a cycle (circular dependency), and no valid order exists.
Remember
Order with dependencies → topological sort.