DSA

Question 1

Solution for traversing a dependency graph - like courses dependent on other courses, or a build sequence with dependencies

Answer 1

Topological Sort

Question 2

How does Kahns Algorithm (for Topological sort) work ?

Answer 2

Find in_degrees of all nodes. Then repeatedly remove nodes that have no dependencies (in_degree = 0), reducing the in_degree of their neighbors and making them candidates if it comes down to 0.
The excercise is complete if all nodes are reduced to 0 in the end, which will not happen if there are cycles because all nodes in the cycle will retain in_degree of >=1