Hello! Today we will learn about Topological Sorting<\/strong>, which frequently appears in coding tests using Java. Topological sorting is an algorithm used in Directed Acyclic Graphs (DAGs) that is very useful for determining the order of tasks considering the precedence relations between them.<\/p>\n Topological sorting refers to the arrangement of vertices in a directed graph such that every vertex appears after all its preceding vertices. Generally, topological sorting is used in the following cases:<\/p>\n Let’s solve the following problem:<\/p>\n There are two methods to perform topological sorting: one utilizing ‘in-degree’ and the other based on ‘DFS’. Here we will explain the in-degree based topological sorting method.<\/p>\n The in-degree based topological sorting consists of the following steps:<\/p>\n Let’s implement the topological sorting algorithm in Java. Below is the Java code to solve the problem.<\/p>\n The above Java code works as follows:<\/p>\n Let’s test with the following input:<\/p>\n This example includes 5 classes and 4 relations, so it can be executed appropriately. The correct output will be the possible order in which the classes can be taken.<\/p>\n The time complexity of topological sorting is O(V + E), where V is the number of vertices (N) and E is the number of edges (M), so it operates efficiently even for large graphs.<\/p>\n Today we learned about the topological sorting algorithm with Java. This algorithm can be applied effectively in various fields and frequently appears in coding tests, so be sure to practice. Topological sorting will be a great help in solving complex problems!<\/p>\n1. What is Topological Sorting?<\/h2>\n
\n
2. Problem Description<\/h2>\n
\n \n <\/pre>\n
3. Topological Sort Algorithm<\/h2>\n
3.1. In-Degree Based Topological Sort<\/h3>\n
\n
4. Java Code Implementation<\/h2>\n
\nimport java.util.*;\n\npublic class TopologicalSort {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n int N = scanner.nextInt(); \/\/ Number of classes\n int M = scanner.nextInt(); \/\/ Number of relations\n\n List5. Code Explanation<\/h2>\n
\n
6. Example Test<\/h2>\n
\n5 4\n1 2\n1 3\n2 4\n3 4\n <\/code><\/pre>\n7. Time Complexity<\/h2>\n
8. Conclusion<\/h2>\n