kotlin coding test course, topological sorting

Overview

Topological Sort is an algorithm for linearly ordering vertices in a directed graph. This algorithm is mainly used for problems that express dependencies of tasks. For example, it is useful for solving various problems such as course prerequisites, task scheduling, etc.

Problem Description

The following is a problem utilizing Topological Sort.

Problem: Course Prerequisite Problem

In university, to complete course A, courses B and C must be completed first. Given several courses and completion conditions, write a program in Kotlin to determine the order of classes required to complete all courses. There can be multiple valid class orders. The goal is to return all possible class orders.

Input Format

• The first line contains an integer N (1 ≤ N ≤ 20): the number of courses.
• The second line contains an integer M (0 ≤ M ≤ 100): the number of prerequisite pairs.
• The next M lines contain two integers in the form of ‘A B’, meaning that to finish course ‘A’, course ‘B’ must be completed first.

Output Format

Output the order of course completion in a single line separated by spaces. If there are multiple valid orders of completion, only output the lexicographically smallest course order.

Solution Process

1. Understanding the Problem

To solve the problem, we must first understand the concept of Topological Sort. In the graph, vertices represent courses, and edges represent prerequisites. We can construct a directed graph that indicates which courses must be completed in order to take others.

2. Constructing the Graph

Based on the given courses and prerequisites, construct the graph. Each course becomes a node, and prerequisites are represented as directed edges.

val graph = mutableMapOf>()
val inDegree = IntArray(N + 1) // Stores the in-degree of each course

3. Calculating In-Degree

Calculate the in-degree of each course. The in-degree represents the number of courses that must be completed before reaching that course.

for (i in 0 until M) {
    val a = readLine()!!.split(' ').map { it.toInt() }
    graph.getOrPut(a[1]) { mutableListOf() }.add(a[0])
    inDegree[a[0]]++
}

4. Implementing Topological Sort Algorithm

Topological Sort can be implemented using BFS. Starting from nodes with an in-degree of 0, visit these nodes in order while decrementing their in-degrees. If any node’s in-degree becomes 0 during this process, add it to the queue.

fun topologicalSort(N: Int): List {
    val result = mutableListOf()
    val queue: Queue = LinkedList()

    // Add nodes with in-degree of 0 to the queue
    for (i in 1..N) {
        if (inDegree[i] == 0) {
            queue.add(i)
        }
    }

    while (queue.isNotEmpty()) {
        // Remove vertex from queue for lexicographical sorting
        val current = queue.poll()
        result.add(current)

        // Process the outgoing edges from the current vertex
        for (next in graph[current] ?: listOf()) {
            inDegree[next]--
            if (inDegree[next] == 0) {
                queue.add(next)
            }
        }
    }

    return result
}

5. Final Code

The final code including the Topological Sort functionality is as follows.

fun main() {
    val (N, M) = readLine()!!.split(' ').map { it.toInt() }

    val graph = mutableMapOf>()
    val inDegree = IntArray(N + 1)

    // Initialize graph and in-degrees
    for (i in 0 until M) {
        val (a, b) = readLine()!!.split(' ').map { it.toInt() }
        graph.getOrPut(b) { mutableListOf() }.add(a)
        inDegree[a]++
    }

    // Perform Topological Sort
    val result = topologicalSort(N)
    
    // Output the result
    println(result.joinToString(" "))
}

Conclusion

Topological Sort is a very useful algorithm for solving various graph problems. It shines especially in situations where dependencies must be taken into account, such as in course prerequisite problems. In this lesson, we examined the basic concepts of Topological Sort and followed a step-by-step problem-solving process. I hope you continue to enhance your Kotlin skills through various algorithm problems.