Objective: You are working on a project where QA team has automated set of test cases for the project, but these test cases have to be executed in a specific order since test cases has dependencies on each other, for example if test case A and dependency on test case B then test case B has to be executed before test case A. Given a set of test cases, Write an algorithm to print the execution sequence for the test cases.
Test Cases: A B C D E F G E depends on B, D, G D depends on B, C C depends on A B depends on A F no dependency G depends on A Output: Test Case sequence: F A B C D E
Approach: Topological Sorting
- This problem is the classic example of “topological sorting“.
- Let’s consider each test case as Vertex and dependency between two tests 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 test B can be executed only when test A is executed.
- Now we can draw a graph and do the topological sort which we have discussed here. So the graph for the example above is
See the code below for more understanding.
Time Complexity: O(N), N – Number of test cases.
Test Case Sequence: F A B C D G E