396. Optimizing Test Execution: Managing Test Dependencies for Sequential Order

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.

Example:

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.

Output:

Test Case Sequence:
F A B C D G E

Related Problems:

- Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Priority Queue – Java Implementation Hard
- Graph – Software Installation Problem Medium
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Min Heap Hard
- Dijkstra’s – Shortest Path Algorithm (SPT) - Adjacency Matrix - Java Implementation Hard
- Graph Implementation – Adjacency List - Better| Set 2 Beginner