拓扑排序Swift

问题描述 投票:0回答:1

我正在尝试使用以下理论在Swift中实现拓扑排序。

https://courses.cs.washington.edu/courses/cse326/03wi/lectures/RaoLect20.pdf

我的代码是:

func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
    guard (prerequisites.count > 0) else {return true}
    var graph : [[Int]] = Array(repeating: [], count: numCourses + 1)
    var inDegree : [Int] = Array(repeating: 0, count: numCourses + 1 )
    for x in prerequisites {
        graph[x[0]] = [x[1]]
        inDegree[x[0]] += 1
    }
    for course in graph.enumerated() {
        print ("To finish course \(course.offset) you must have finished \(course.element)")
    }

    for course in (inDegree.enumerated()) {
        print ("Course \(course.offset) needs \(course.element) courses to be complete")
    }

    var outputArr = [Int]()

    while let currentVertexIndx = (inDegree.enumerated().first { $0.element == 0 }?.offset) {
        outputArr.append( currentVertexIndx )
        for course in graph.enumerated() {

            if (course.element.contains(currentVertexIndx)) {
                inDegree[ course.offset ] -= 1
            }
        }

        inDegree[currentVertexIndx] = -1
    }
    return outputArr.count >= numCourses
}

测试答案正确:

//canFinish(1, [[1,0]]) // true - to take course 1 you should have finished course 0
//canFinish(2, [[1,0],[0,1]]) // false - to take course 1 you have to have finished course 0, to take 0 you have to have finished course 1
//canFinish(1, []) // true
//canFinish(3, [[1,0],[2,0]]) // true
//canFinish(3, [[2,0],[2,1]]) // true

测试答案不正确

canFinish(10, [[5,6],[0,2],[1,7],[5,9],[1,8],[3,4],[0,6],[0,7],[0,3],[8,9]]) // true, but returns false

问题:使用Washington.edu链接的理论,我的代码不适用于上面的输入。出了什么问题?

swift
1个回答
1
投票

你应该正确填写graph

graph[x[0]] += [x[1]]

哪个会在给定的示例中产生正确的结果:

canFinish(10, [[5,6],[0,2],[1,7],[5,9],[1,8],[3,4],[0,6],[0,7],[0,3],[8,9]]) //true
© www.soinside.com 2019 - 2024. All rights reserved.