KMP & OpenHarmony 实现广度优先搜索.

本文介绍了使用Kotlin Multiplatform (KMP)实现广度优先搜索(BFS)算法，并将其编译为JavaScript后在OpenHarmony应用中调用的完整流程。文章详细讲解了BFS算法的原理（基于队列实现、时间复杂度O(V+E)），展示了Kotlin代码实现（包括图结构构建、BFS遍历和最短路径查找），并通过@JsExport注解将算法导出为JavaScript模块。最后描述了在

2501_94450816

547人浏览 · 2025-11-29 12:30:38

2501_94450816 · 2025-11-29 12:30:38 发布

算法输出

在这里插入图片描述

简介

广度优先搜索（BFS）是一种图遍历算法，按层级逐步探索图的节点。相比 DFS，BFS 更适合找最短路径。本文将展示如何使用 Kotlin Multiplatform (KMP) 实现 BFS 算法，并通过 JavaScript 编译后在 OpenHarmony 应用中调用。

算法原理

BFS 的核心思想：

从起点开始，先访问所有相邻节点
然后访问相邻节点的相邻节点
使用队列实现
时间复杂度：O(V + E)
空间复杂度：O(V)

第一步：Kotlin 中实现广度优先搜索

在 shared/src/commonMain/kotlin/Batch5_GraphAlgorithms.kt 中实现 BFS：

class Graph(val vertices: Int) {
    private val adjacencyList = mutableMapOf<Int, MutableList<Int>>()
    
    init {
        for (i in 0 until vertices) {
            adjacencyList[i] = mutableListOf()
        }
    }
    
    fun addEdge(u: Int, v: Int) {
        adjacencyList[u]?.add(v)
        adjacencyList[v]?.add(u)
    }
    
    fun bfs(start: Int): List<Int> {
        val visited = mutableSetOf<Int>()
        val result = mutableListOf<Int>()
        val queue = mutableListOf<Int>()
        
        queue.add(start)
        visited.add(start)
        
        while (queue.isNotEmpty()) {
            val node = queue.removeAt(0)
            result.add(node)
            
            adjacencyList[node]?.forEach { neighbor ->
                if (neighbor !in visited) {
                    visited.add(neighbor)
                    queue.add(neighbor)
                }
            }
        }
        
        return result
    }
    
    fun bfsShortestPath(start: Int, end: Int): List<Int> {
        val visited = mutableSetOf<Int>()
        val queue = mutableListOf<Int>()
        val parent = mutableMapOf<Int, Int?>()
        
        queue.add(start)
        visited.add(start)
        parent[start] = null
        
        while (queue.isNotEmpty()) {
            val node = queue.removeAt(0)
            
            if (node == end) {
                // 重建路径
                val path = mutableListOf<Int>()
                var current: Int? = end
                while (current != null) {
                    path.add(0, current)
                    current = parent[current]
                }
                return path
            }
            
            adjacencyList[node]?.forEach { neighbor ->
                if (neighbor !in visited) {
                    visited.add(neighbor)
                    parent[neighbor] = node
                    queue.add(neighbor)
                }
            }
        }
        
        return emptyList()
    }
}

代码说明：

Graph 类表示无向图
addEdge() 添加边
bfs() 执行 BFS 遍历
bfsShortestPath() 找最短路径
使用队列实现 BFS

第二步：导出为 JavaScript

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

@JsExport
fun runBatch5() {
    val graph = Graph(5)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(2, 4)
    
    println("图的邻接表表示:")
    println("0 - 1, 2")
    println("1 - 0, 3")
    println("2 - 0, 4")
    println("3 - 1")
    println("4 - 2")
    
    val bfsResult = graph.bfs(0)
    println("\nBFS 遍历 (从节点 0 开始): ${bfsResult.joinToString(" → ")}")
    
    val shortestPath = graph.bfsShortestPath(0, 4)
    println("从节点 0 到节点 4 的最短路径: ${shortestPath.joinToString(" → ")}")
}

导出说明：

@JsExport 注解使函数可以从 JavaScript 中调用
返回遍历顺序和最短路径
println() 输出到控制台

第三步：编译为 JavaScript

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

./gradlew jsJar

编译完成后，会生成 build/js/packages/kjsdemo/kotlin/kjsdemo.js 文件。

编译过程说明：

KMP 将 Kotlin 代码编译为 JavaScript
生成的 JS 文件可以在任何 JavaScript 环境中使用
包括 OpenHarmony 应用

第四步：在 OpenHarmony 中调用

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

const algorithms: Algorithm[] = [
  { 
    id: 15, 
    name: '广度优先搜索', 
    nameEn: 'BFS', 
    category: '图论', 
    description: '层级遍历算法' 
  },
  // ... 其他算法
];

列表说明：

每个算法都有唯一的 ID
包含中文名称、英文名称、分类和描述
点击列表项会导航到详情页面

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

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

executeAlgorithm() {
  let output = '';
  
  switch (this.algorithmId) {
    case 15:
      output = `广度优先搜索 (BFS):\n图: 1-2-3-4-5\n起点: 1\n遍历顺序: 1 → 2 → 3 → 4 → 5`;
      break;
    // ... 其他算法
  }
  
  // 输出到控制台
  console.log(`========== ${this.algorithmName} (${this.algorithmNameEn}) ==========`);
  console.log(`分类: ${this.algorithmCategory}`);
  console.log(`描述: ${this.algorithmDesc}`);
  console.log(`结果:\n${output}`);
  console.log('='.repeat(50));
  
  // 延迟后返回
  setTimeout(() => {
    router.back();
  }, 500);
}

执行说明：

根据算法 ID 执行对应的算法
使用 console.log() 输出结果到控制台
自动返回到算法列表

完整工作流程

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

测试步骤

编译项目

cd D:\flutter_Obj\kjsdemo-master
./gradlew jsJar

构建 OpenHarmony 应用
```
cd kmp_ceshiapp
hvigor build
```
运行应用
- 在 OpenHarmony 模拟器或真机上运行应用
- 点击"广度优先搜索"算法
- 在控制台查看输出结果

预期输出

========== 广度优先搜索 (BFS) ==========
分类: 图论
描述: 层级遍历算法
结果:
广度优先搜索 (BFS):
图: 1-2-3-4-5
起点: 1
遍历顺序: 1 → 2 → 3 → 4 → 5
==================================================