算法输出

简介

拓扑排序（Topological Sorting）是对有向无环图（DAG - Directed Acyclic Graph）的顶点进行线性排序，使得对于每条有向边 (u,v)，u 在排序中都在 v 之前。这个算法在实际应用中非常重要，特别是在任务调度、编译器优化、课程先修关系等领域。

拓扑排序的关键特性：

• 只能应用于有向无环图（DAG）
• 一个 DAG 可能有多个拓扑排序
• 如果图中存在环，则无法进行拓扑排序

算法原理详解

核心思想

拓扑排序的核心思想基于以下观察：

• 在 DAG 中，必然存在入度为 0 的顶点（没有前驱）
• 移除这个顶点及其所有出边后，剩余图仍然是 DAG
• 重复此过程直到所有顶点都被处理

两种实现方法

方法一：Kahn 算法（基于入度）

• 计算所有顶点的入度
• 将入度为 0 的顶点加入队列
• 依次处理队列中的顶点
• 更新相邻顶点的入度
• 时间复杂度：O(V + E)
• 空间复杂度：O(V)

方法二：DFS 算法

• 对每个未访问的顶点进行 DFS
• 在 DFS 回溯时将顶点加入结果
• 最后反转结果列表
• 时间复杂度：O(V + E)
• 空间复杂度：O(V)

第一步：Kotlin 中实现拓扑排序

使用 Kahn 算法的实现

fun topologicalSortKahn(n: Int, edges: List<Pair<Int, Int>>): List<Int> {
    // 构建邻接表和入度数组
    val adj = mutableMapOf<Int, MutableList<Int>>()
    val inDegree = IntArray(n)
    
    // 初始化邻接表
    for (i in 0 until n) {
        adj[i] = mutableListOf()
    }
    
    // 构建图和计算入度
    for ((u, v) in edges) {
        adj[u]?.add(v)
        inDegree[v]++
    }
    
    // 将所有入度为 0 的顶点加入队列
    val queue = mutableListOf<Int>()
    for (i in 0 until n) {
        if (inDegree[i] == 0) {
            queue.add(i)
        }
    }
    
    val result = mutableListOf<Int>()
    
    // 处理队列中的顶点
    while (queue.isNotEmpty()) {
        val u = queue.removeAt(0)
        result.add(u)
        
        // 更新相邻顶点的入度
        adj[u]?.forEach { v ->
            inDegree[v]--
            if (inDegree[v] == 0) {
                queue.add(v)
            }
        }
    }
    
    // 检查是否存在环
    return if (result.size == n) result else emptyList()
}

代码说明：

• 使用邻接表表示图结构
• 入度数组记录每个顶点的前驱数量
• 队列存储入度为 0 的顶点
• 每次处理一个入度为 0 的顶点，并更新其后继的入度
• 如果最终结果大小不等于顶点数，说明存在环

使用 DFS 算法的实现

fun topologicalSortDFS(n: Int, edges: List<Pair<Int, Int>>): List<Int> {
    // 构建邻接表
    val adj = mutableMapOf<Int, MutableList<Int>>()
    for (i in 0 until n) {
        adj[i] = mutableListOf()
    }
    
    for ((u, v) in edges) {
        adj[u]?.add(v)
    }
    
    val visited = BooleanArray(n)
    val recStack = BooleanArray(n)  // 用于检测环
    val result = mutableListOf<Int>()
    var hasCycle = false
    
    fun dfs(v: Int) {
        visited[v] = true
        recStack[v] = true
        
        adj[v]?.forEach { u ->
            if (!visited[u]) {
                dfs(u)
            } else if (recStack[u]) {
                hasCycle = true  // 检测到环
            }
        }
        
        recStack[v] = false
        result.add(v)
    }
    
    // 对所有未访问的顶点进行 DFS
    for (i in 0 until n) {
        if (!visited[i]) {
            dfs(i)
        }
    }
    
    // 反转结果并检查是否存在环
    return if (!hasCycle) result.reversed() else emptyList()
}

代码说明：

• 使用递归 DFS 遍历图
• 递归栈用于检测环的存在
• 在回溯时将顶点加入结果
• 最后反转结果得到拓扑排序

第二步：导出为 JavaScript

使用 @JsExport 注解将 Kotlin 函数导出为 JavaScript：

@JsExport
fun runBatch5() {
    // 示例：课程先修关系
    val n = 6
    val edges = listOf(
        Pair(0, 1),  // 课程0是课程1的先修课
        Pair(0, 2),
        Pair(1, 3),
        Pair(2, 3),
        Pair(3, 4),
        Pair(4, 5)
    )
    
    val result = topologicalSortKahn(n, edges)
    
    if (result.isNotEmpty()) {
        println("拓扑排序结果: ${result.joinToString(" → ")}")
        println("课程学习顺序: ${result.map { "课程$it" }.joinToString(" → ")}")
    } else {
        println("图中存在环，无法进行拓扑排序")
    }
}

导出说明：

• @JsExport 注解使函数可以从 JavaScript 中调用
• 返回拓扑排序的结果列表
• println() 输出到控制台

第三步：编译为 JavaScript

在项目根目录执行编译命令：

./gradlew jsJar

编译过程会：

1. 编译 Kotlin 代码为 JavaScript
2. 生成 TypeScript 定义文件
3. 创建 Source Map 用于调试
4. 输出到 build/js/packages/ 目录

第四步：在 OpenHarmony 中调用

在 kmp_ceshiapp/entry/src/main/ets/pages/Index.ets 中定义算法列表：

const algorithms: Algorithm[] = [
  { 
    id: 20, 
    name: '拓扑排序', 
    nameEn: 'Topological Sort', 
    category: '图论', 
    description: '有向无环图排序' 
  },
  // ... 其他算法
];

第五步：执行算法并输出到控制台

在 kmp_ceshiapp/entry/src/main/ets/pages/AlgorithmDetail.ets 中处理算法执行：

case 20:
  output = `【拓扑排序】\nDAG: 6个顶点,7条边\n入度计算: [0,1,1,2,1,1]\n处理顺序: 0→1→2→3→4→5\n排序结果: [0,1,2,3,4,5]\n有效性: 通过`;
  break;

完整工作流程

Kotlin 代码 (topologicalSort)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

实际应用场景

1. 课程先修关系

课程依赖关系：
- 数据结构 → 算法设计
- 数据结构 → 数据库
- 算法设计 → 高级算法
- 数据库 → 系统设计

拓扑排序结果：
数据结构 → 算法设计 → 高级算法 → 系统设计
数据结构 → 数据库 → 系统设计

2. 编译器优化

编译步骤依赖：
- 词法分析 → 语法分析
- 语法分析 → 语义分析
- 语义分析 → 代码生成
- 代码生成 → 优化
- 优化 → 汇编

拓扑排序确保正确的编译顺序

3. 任务调度

任务依赖关系：
- 需求分析 → 系统设计
- 系统设计 → 模块开发
- 模块开发 → 集成测试
- 集成测试 → 系统测试

拓扑排序确定最优的任务执行顺序

性能分析

指标	Kahn 算法	DFS 算法
时间复杂度	O(V + E)	O(V + E)
空间复杂度	O(V)	O(V)
环检测	隐式	显式
实现难度	简单	中等
实际应用	更常用	学术研究

优化建议

1. 使用优先队列：如果需要特定的排序顺序，可以使用优先队列代替普通队列
2. 环检测优化：提前检测环，避免不必要的计算
3. 并行化：对于大规模图，可以考虑并行处理
4. 缓存优化：对于频繁查询的图，可以缓存拓扑排序结果

总结

通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中编写高效的拓扑排序算法
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

拓扑排序是图论中的重要算法，广泛应用于任务调度、编译器优化、依赖关系处理等领域。理解和掌握拓扑排序对于解决实际问题非常重要。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net

---