0

More than 1 year has passed since last update.

Swift で Topological Sort（トポロジカルソート）

Last updated at Posted at 2021-09-17

コード

// prerequisites = [[to1, from1]], [to2, from2], ... [toN, fromN]]
func findOrder(_ numCourses: Int, _ prerequisites: [[Int]]) -> [Int] {
var graph = [[Int]](repeating: [], count: numCourses)
var indegree = [Int](repeating: 0, count: numCourses)
var visited = [Bool](repeating: false, count: numCourses)
var queue = [Int]()
var result = [Int]()

// initialize
for edge in prerequisites {
let from = edge[1]
let to = edge[0]
graph[from].append(to)
indegree[to] += 1
}
for i in 0..<indegree.count where indegree[i] == 0 {
queue.append(i)
result.append(i)
}
if queue.isEmpty { return [] }

// algorithm
while !queue.isEmpty {
let from = queue.removeFirst()
visited[from] = true
for to in graph[from] {
indegree[to] -= 1
if indegree[to] == 0 {
queue.append(to)
result.append(to)
}
}
}

// guard
if !indegree.allSatisfy({ \$0 == 0 }) { return []}
if !visited.allSatisfy({ \$0 }) { return [] }

return result
}

Register as a new user and use Qiita more conveniently

1. You get articles that match your needs
2. You can efficiently read back useful information
3. You can use dark theme
What you can do with signing up
0