目录

一、练习题

二、小结

一、练习题

1. 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

package Algorithm.topologicalsort
import std.collection.*

public func topologicalSort(numVertices: Int64, adjList: ArrayList<ArrayList<Int64>>): ArrayList<Int64> {
    // 初始化入度表
    let inDegree = Array<Int64>(numVertices, item: 0)
    for (i in 0..adjList.size) {
        let neighbors = adjList[i]
        for (j in 0..neighbors.size) {
            let neighbor = neighbors[j]
            inDegree[neighbor]++
        }
    }
 
    // 初始化队列，将所有入度为0的节点加入队列
    let queue = ArrayList<Int64>()
    for (i in 0..numVertices) {
        if (inDegree[i] == 0) {
            queue.append(i)
        }
    }
 
    let result = ArrayList<Int64>()
    while (!queue.isEmpty()) {
        let u = queue.remove(0)
        result.append(u)

        let neighbors = adjList[u]
        for (j in 0..neighbors.size) {
            let v = neighbors[j]
            inDegree[v]--
            if (inDegree[v] == 0) {
                queue.append(v)
            }
        }
    }
 
    // 检查是否有环
    if (result.size != numVertices) {
        // 返回空列表表示有环
        return ArrayList<Int64>() 
    }
 
    return result
}

测试代码

package Algorithm
import Algorithm.topologicalsort.*
import std.collection.*

main(): Int64 {
    let numVertices = 6
    let adjList = ArrayList<ArrayList<Int64>>()
    for (_ in 0..numVertices) {
        adjList.append(ArrayList<Int64>())
    }
 
    // 添加边
    adjList[1].append(2)
    adjList[1].append(3)
    adjList[2].append(4)
    adjList[3].append(4)
    adjList[5].append(1)
 
    let result = topologicalSort(numVertices, adjList)
    println(result)
    return 0
}

二、小结

本章为大家详细的介绍了仓颉数据结构与算法中拓扑排序练习题的内容，下一章，为大家带来关键路径的内容。最后，创作不易，如果大家觉得我的文章对学习仓颉数据结构与算法有帮助的话，就动动小手，点个免费的赞吧！收到的赞越多，我的创作动力也会越大哦，谢谢大家🌹🌹🌹！！！