Swift Coding Test Course, Topological Sorting

Coding tests are important exams for many software developers. In particular, the ability to solve algorithmic problems is a crucial factor for interviewers to evaluate applicants’ problem-solving skills. This course covers the essence and application of an algorithm called ‘Topological Sorting.’ Topological sorting is a concept mostly used in graph theory, which is a way to linearly order the vertices of a directed graph.

1. Concept of Topological Sorting

Topological sorting is the process of listing each vertex in a Directed Acyclic Graph (DAG) in order. The condition that one vertex can come before another is determined by the direction of the edges. That is, if there is an edge from vertex A to vertex B, then in topological sorting, vertex A must come before vertex B.

2. Problem Description

Problem: Write a program to print the order of prerequisite subjects required to complete all courses based on the given relationship between classes and their prerequisites.

Input Format

– The first line contains two integers N (1 ≤ N ≤ 10^6) and M (1 ≤ M ≤ 10^6), where N is the number of courses and M is the number of prerequisite relationships between the courses.

– The next M lines each contain two integers A and B, indicating that A is a prerequisite for B.

Output Format

– Print the sorted order of courses that satisfy the prerequisites in one line. If this process cannot be completed, output 0.

Example Input

4 4
2 1
3 1
1 4
4 3

Example Output

0

3. Approach to Problem Solving

This problem can be solved using the topological sorting algorithm. Generally, the topological sorting algorithm can be executed in two ways:

  • Method using DFS (Depth-First Search)
  • Method using BFS (Breadth-First Search) and in-degrees

4. BFS-based Topological Sorting

Let’s examine how to solve the problem using the BFS method for topological sorting. This approach calculates the ‘in-degrees’ and inserts the vertices with an in-degree of 0 into the queue. Then, it proceeds by taking one vertex from the queue at a time and decreasing the in-degrees of the other connected vertices.

4.1. Steps of the Algorithm

  1. Create an array to store in-degrees.
  2. Analyze each edge and calculate the in-degrees.
  3. Insert vertices with in-degrees of 0 into the queue.
  4. Remove vertices from the queue and decrease the in-degrees of the connected vertices.
  5. If all vertices have been processed, return the result; if there are unprocessed vertices, return 0.

5. Swift Implementation

Below is the code implementing the given problem in Swift.


import Foundation

func topologicalSort(N: Int, edges: [(Int, Int)]) {
    var graph = [[Int]](repeating: [Int](), count: N + 1)
    var inDegree = [Int](repeating: 0, count: N + 1)

    for edge in edges {
        let (a, b) = edge
        graph[a].append(b)
        inDegree[b] += 1
    }

    var result = [Int]()
    var queue = [Int]()

    // Insert vertices with in-degrees of 0 into the queue
    for i in 1...N {
        if inDegree[i] == 0 {
            queue.append(i)
        }
    }

    while !queue.isEmpty {
        let current = queue.removeFirst()
        result.append(current)

        for neighbor in graph[current] {
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0 {
                queue.append(neighbor)
            }
        }
    }

    if result.count == N {
        print(result.map { String($0) }.joined(separator: " "))
    } else {
        print(0)
    }
}

let N = 4
let M = 4
let edges = [(2, 1), (3, 1), (1, 4), (4, 3)]

topologicalSort(N: N, edges: edges)

6. Conclusion

Topological sorting is a useful algorithm that is applied in many fields. In particular, it serves as a powerful tool through the concept of prerequisites when tasks need to be performed sequentially. Through this problem, I hope you learn the topological sorting algorithm and develop the ability to apply it to various problems. Similar problems frequently appear in coding tests, so ample practice is necessary.