Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

Build Order

problem

You are given a list of projects and a list of dependencies ( which is a list of pairs of projects, where the second project is dependent on the first project). All of a project’s dependencies must be built before the project is. Find a build order that will allow the projects to be built. If there is no valid build order, return an error.

how to solve

This problem is topological sort. Topological sort algorithm is the following approach.

  • Identify all nodes with no incoming edges and add those nodes to our topological sort.
  • When we do the above, decline the number of incoming edges as the out coming from the added node.
  • Repeat the above, When all the nodes have been added to the topological sort, then we done.

This algorithm is executed in time complexity O(V + E).

code

Remove all ads