This post is completed by 1 user

  • 0
 Add to List
Medium

272. Graph – Software Installation Problem

Objective: Given a list of software’s which you need to install in a computer. Few software’s has dependency on other software’s in the list, means these software can be installed only when all of its dependent software’s are installed. Write an algorithm to print the sequence in which all the software’s in the list can be installed.

Example:

Software’s: A B C D E F
E depends on B, D
D depends on B, C
C depends on A
B depends on A
F no dependency
Output: F A B C D E

Approach: Topological Sorting

  • This problem is the classic example of “topological sorting”.
  • Let’s consider each software as Vertex and dependency between two software’s as Edge between two vertices. So for example B depends on A can be seen as A->B, A has a directed edge towards B. OR it can be read as B can be installed only when the A is installed.
  • Now we can draw a graph and do the topological sort which we have discussed here. So graph for example above is

See the code below for more understanding.

Time Complexity: O(N) n – Number of software’s.

Output:

Software Sequence:
F A B C D E

Related Problems: