Java Coding Test Course, Topological Sorting

Hello! Today we will learn about Topological Sorting, 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.

1. What is Topological Sorting?

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:

  • When determining the order of tasks in a project (e.g., Task B can only start after Task A is completed)
  • When determining the order of classes in a learning process (e.g., a prerequisite course must be taken before enrolling in the next course)

2. Problem Description

Let’s solve the following problem:

3. Topological Sort Algorithm

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.

3.1. In-Degree Based Topological Sort

The in-degree based topological sorting consists of the following steps:

  1. Calculate the in-degree of all vertices in the graph.
  2. Add vertices with an in-degree of 0 to the queue.
  3. Remove vertices one by one from the queue and decrease the in-degree of all vertices connected to it by 1.
  4. Add vertices whose in-degree becomes 0 to the queue.
  5. Repeat the above steps until the queue is empty.

4. Java Code Implementation

Let’s implement the topological sorting algorithm in Java. Below is the Java code to solve the problem.


import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // Number of classes
        int M = scanner.nextInt(); // Number of relations

        List> graph = new ArrayList<>();
        int[] inDegree = new int[N + 1];
        
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        // Process graph input
        for (int i = 0; i < M; i++) {
            int A = scanner.nextInt();
            int B = scanner.nextInt();
            graph.get(A).add(B);
            inDegree[B]++;
        }
        
        // Add nodes with in-degree 0 to the queue
        Queue queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        List result = new ArrayList<>();
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            result.add(current);
            for (int next : graph.get(current)) {
                inDegree[next]--; // Decrease in-degree
                if (inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        
        // Check if the order is determined
        if (result.size() == N) {
            for (int i : result) {
                System.out.print(i + " ");
            }
        } else {
            System.out.println(0);
        }
        
        scanner.close();
    }
}

5. Code Explanation

The above Java code works as follows:

  1. It uses a Scanner to read input and retrieves the number of classes N and the number of relations M.
  2. It initializes an array to store the graph and in-degrees. The graph information for each class is stored as a list.
  3. It receives M relations, adds the relations to the graph, and updates the in-degrees.
  4. It starts by adding nodes with an in-degree of 0 to the queue.
  5. It removes vertices from the queue, decreasing the in-degrees of all vertices connected to it by 1.
  6. If any vertex’s in-degree becomes 0 during this process, it adds it to the queue.
  7. It handles exceptional situations and ultimately prints the classes in the possible order.

6. Example Test

Let’s test with the following input:


5 4
1 2
1 3
2 4
3 4

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.

7. Time Complexity

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.

8. Conclusion

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!

© 2023 Java Coding Test Course