kimi-k2.6 在「实现图遍历算法」的评测结果

这是该 AI 模型在此测试用例上的详细评测结果。

基本信息

  • 模型名称：kimi-k2.6
  • 用例名称：实现图遍历算法
  • 测试类型：文本生成
  • 评测维度：代码生成

系统提示词（System Prompt）

这是给 AI 模型的背景设定和角色指令：

你是一名资深算法工程师，擅长数据结构与图论算法的实现与讲解。 回答要求： 1. 使用 Python 语言实现，代码需清晰易读，包含必要的注释。 2. 输出结构应包含：实现代码、简要说明、测试用例三部分。 3. 对核心方法注明时间复杂度与空间复杂度（Time & Space Complexity）。 4. 代码须为 Ready-to-run 状态，可直接运行并输出可验证的结果。 5. 面向入门学习者，优先保证逻辑清晰，避免过度工程化。

用户提示词（User Prompt）

这是用户给 AI 模型的具体任务要求：

请使用 Python 实现一个简单的**无向图**数据结构，具体要求如下： **数据结构要求：** - 使用**邻接表**（字典 + 列表）表示图结构。 - 支持 `add_vertex(v)` 方法：向图中添加一个顶点。 - 支持 `add_edge(u, v)` 方法：在顶点 u 和 v 之间添加一条无向边（若顶点不存在则自动创建）。 **算法要求：** - 实现 `dfs(start)` 方法：从指定起始顶点出发，执行深度优先搜索（DFS）遍历，返回遍历顺序的顶点列表。 - DFS 可使用递归或显式栈实现，需清晰标注所选方式。 **输出要求：** - 提供至少 3 个测试用例，覆盖：普通连通图、包含孤立顶点的图、单顶点图。 - 每个测试用例打印图的邻接表结构及 DFS 遍历结果。 **示例：**

任务要求

AI 模型需要满足以下要求：

  1. 邻接表结构正确，使用字典嵌套字典存储加权有向边，数据组织清晰合理。
  2. DFS 和 BFS 遍历逻辑正确，能处理非连通图（孤立顶点、多连通分量），访问顺序符合各自算法特性。
  3. 「`remove_vertex` 必须同步删除所有其他顶点中指向该顶点的入边，不能仅删除出边。」
  4. 「`has_path` 能正确判断有向路径的存在性，包括直接相邻、多跳路径及不可达的情况。」
  5. 「异常与边界处理完善：不存在的顶点执行遍历时抛出 `ValueError`，删除不存在的顶点/边时给出警告而非崩溃。」
  6. 提供复杂度分析，并附有覆盖主要功能和边界场景的可运行测试用例。

评测结果

综合得分

该模型在此用例的得分为：93.5 分（满分 100 分），已通过

基础难度评测结果

  • 得分：93.5 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

下面给出一个面向入门学习者的、可直接运行的 Python 实现。整体采用**邻接表**存储无向图，`DFS` 选用**递归**实现（代码更简洁，思路与教科书一致）。 --- ## 1. 实现代码 ```python class UndirectedGraph: """ 无向图数据结构，基于字典+列表的邻接表实现。 """ def __init__(self): # 邻接表：键为顶点，值为该顶点的邻居列表 self.adj = {} def add_vertex(self, v): """ 向图中添加顶点 v。若顶点已存在，则不做任何操作。 时间复杂度：O(1)（均摊） 空间复杂度：O(1) """ if v not in self.adj: self.adj[v] = [] def add_edge(self, u, v): """ 在顶点 u 和 v 之间添加一条无向边。 若顶点不存在，会自动创建。 时间复杂度：O(1) 空间复杂度：O(1) """ if u not in self.adj: self.add_vertex(u) if v not in self.adj: self.add_vertex(v) self.adj[u].append(v) self.adj[v].append(u) def dfs(self, start): """ 从起始顶点 start 出发，执行深度优先搜索（DFS）。 【实现方式：递归】 返回： list: 遍历顺序的顶点列表（仅包含从 start 可达的顶点）。 时间复杂度：O(V + E) V 为顶点数，E 为边数。每个顶点访问一次，每条边在其两个端点处各被查看一次。 空间复杂度：O(V) 主要用于 visited 集合和递归调用栈。 """ if start not in self.adj: return [] visited = set() result = [] def _dfs_recursive(v): visited.add(v) result.append(v) # 遍历当前顶点的所有邻居 for neighbor in self.adj[v]: if neighbor not in visited: _dfs_recursive(neighbor) _dfs_recursive(start) return result def __str__(self): """以字符串形式打印邻接表，方便观察图结构。""" lines = ["Graph adjacency list:"] for v, neighbors in self.adj.items(): lines.append(f" {v}: {neighbors}") return "\n".join(lines) # ------------------- 测试用例 ------------------- def run_tests(): # 测试用例 1：普通连通图 print("=" * 50) print("测试用例 1：普通连通图") print("=" * 50) g1 = UndirectedGraph() edges1 = [(0, 1), (0, 2), (1, 3), (2, 4)] for u, v in edges1: g1.add_edge(u, v) print(g1) print("DFS 从顶点 0 出发:", g1.dfs(0)) print() # 测试用例 2：包含孤立顶点的图 print("=" * 50) print("测试用例 2：包含孤立顶点的图") print("=" * 50) g2 = UndirectedGraph() g2.add_edge("A", "B") g2.add_edge("B", "C") g2.add_vertex("D") # 孤立顶点 print(g2) print("DFS 从顶点 A 出发:", g2.dfs("A")) print("（说明：孤立顶点 D 无法从 A 到达，故不在 DFS 结果中。）") print() # 测试用例 3：单顶点图 print("=" * 50) print("测试用例 3：单顶点图") print("=" * 50) g3 = UndirectedGraph() g3.add_vertex("X") print(g3) print("DFS 从顶点 X 出发:", g3.dfs("X")) print() if __name__ == "__main__": run_tests() ``` --- ## 2. 简要说明 | 方法 | 核心思路 | 时间复杂度 | 空间复杂度 | | :---...

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【CLAUDE】这是一个高质量的图数据结构实现，完全满足任务要求。代码清晰易读，注释详尽，复杂度分析准确。DFS 递归实现符合教科书标准，逻辑正确。邻接表结构使用恰当，核心方法实现无误。测试用例覆盖了主要场景，输出格式规范。整体面向入门学习者，在保证正确性的同时兼顾了可读性。若要进一步提升，可增加对重复边、自环的处理，以及更全面的边界测试用例。 【GEMINI】该回答是一份高质量的 AI 生成结果。它不仅完美完成了所有功能性要求（图结构、DFS 算法、测试用例），还在文档结构、注释清晰度以及复杂度分析上表现专业。代码逻辑简洁，非常适合入门学习者参考，没有任何明显的瑕疵。 【KIMI】整体而言，这段代码实现了无向图的基本功能，包括图的表示、遍历算法实现和路径查找等。代码结构清晰，注释详细，易于理解。测试用例覆盖了常见的图结构，能够验证代码的正确性。但是测试用例还可以进一步完善，增加对图操作和DFS遍历结果的更全面的验证。

进阶难度评测结果

  • 得分：95.8 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

```python """ Weighted Directed Graph (邻接表实现) 使用字典嵌套字典表示图结构： {顶点: {邻居顶点: 权重}} 支持任意可哈希类型作为顶点标识，提供完整的顶点/边增删、 DFS、BFS 以及有向路径判定功能。 """ from collections import deque from typing import Any, Dict, List class WeightedDirectedGraph: def __init__(self): """ 初始化空图。 adj: 邻接表，格式为 {vertex: {neighbor: weight}} """ self.adj: Dict[Any, Dict[Any, float]] = {} # ------------------------------------------------------------------ # # 顶点操作 # ------------------------------------------------------------------ # def add_vertex(self, v: Any) -> None: """ 添加顶点 v。若顶点已存在则静默忽略。 时间复杂度: O(1) """ if v not in self.adj: self.adj[v] = {} def remove_vertex(self, v: Any) -> None: """ 删除顶点 v 及其所有出边，并同步清理其他顶点指向 v 的入边。 若顶点不存在，打印警告信息。 时间复杂度: O(V + E) （需要遍历全图邻接表清理入边） 空间复杂度: O(1) """ if v not in self.adj: print(f"Warning: Vertex '{v}' does not exist. No action taken.") return # 1. 删除顶点自身及其所有出边 del self.adj[v] # 2. 遍历剩余所有顶点，删除指向 v 的入边 # 此处仅修改内层字典，外层字典在遍历时大小不变，安全。 for u in self.adj: if v in self.adj[u]: del self.adj[u][v] # ------------------------------------------------------------------ # # 边操作 # ------------------------------------------------------------------ # def add_edge(self, u: Any, v: Any, weight: float = 1) -> None: """ 添加从 u 到 v 的有向边，权重默认为 1。 若顶点 u 或 v 不存在，会自动创建。 时间复杂度: O(1) 空间复杂度: O(1) """ self.add_vertex(u) self.add_vertex(v) self.adj[u][v] = weight def remove_edge(self, u: Any, v: Any) -> None: """ 删除从 u 到 v 的有向边。 若起点 u 不存在或边不存在，打印警告信息。 时间复杂度: O(1) 平均（字典查找） 空间复杂度: O(1) """ if u not in self.adj: print(f"Warning: Edge ({u} -> {v}) does not exist. Source vertex '{u}' is missing.") return if v not in self.adj[u]: print(f"Warning: Edge ({u} -> {v}) does not exist.") return del self.adj[u][v] # ------------------------------------------------------------------ # # 辅助校验 # ------------------------------------------------------------------ # def _ensure_vertex_exists(self, v: Any, method_name: str) -> None: """内部方法：若顶点不存在，抛出带说明的 ValueError。""" if v not in self.adj: raise ValueError(...

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【CLAUDE】这是一份高质量的实现。代码结构清晰，命名规范，关键逻辑处有详细注释。邻接表数据结构设计合理，完美支持加权有向图的所有操作。算法实现正确且高效，特别是 remove_vertex 正确处理了入边清理这一关键难点。异常处理机制设计合理，区分了需要抛出异常和仅需警告的场景。测试用例覆盖全面且可直接运行，复杂度分析准确详尽。代码达到了生产级别的质量标准，完全满足所有功能要求和边界处理需求。 【GEMINI】这是一份极高质量的实现。代码结构优雅，采用了类型提示（Typing）和详尽的文档字符串，符合资深工程师的工程实践标准。所有功能点均完美达成，特别是 remove_vertex 的入边清理和异常处理机制的设计，体现了良好的健壮性考虑。 【KIMI】整体而言，代码实现了题目要求的加权有向图数据结构及其遍历算法，功能完整，结构清晰，异常处理得当。测试用例覆盖了主要场景，但还有进一步完善的空间。代码风格良好，注释详尽，易于理解。

困难难度评测结果

  • 得分：91.7 分
  • 通过状态：已通过

模型生成产物

以下是该模型针对此任务的实际生成内容：

```python import heapq from collections import deque from typing import Any, Dict, List, Set class Graph: """ 通用图类（邻接表实现），支持有向/无向模式、加权边及常用图算法。 """ def __init__(self, directed: bool = False): self.directed: bool = directed # 邻接表：{顶点: {邻居: 权重}} self._adj: Dict[Any, Dict[Any, int]] = {} # ---------------------------------------------------------------------- # 基本操作 # ---------------------------------------------------------------------- def add_vertex(self, v: Any) -> None: """添加顶点，若已存在则静默忽略。""" if v not in self._adj: self._adj[v] = {} def remove_vertex(self, v: Any) -> None: """ 删除顶点及其所有关联边。 若顶点不存在则抛出 KeyError。 """ if v not in self._adj: raise KeyError(f"Vertex {v} does not exist") # 删除所有其他顶点指向 v 的边（O(V)） for u in list(self._adj.keys()): if v in self._adj[u]: del self._adj[u][v] del self._adj[v] def add_edge(self, u: Any, v: Any, weight: int = 1) -> None: """ 添加/更新边。 - 若顶点不存在则自动创建。 - 不允许负权重，否则抛出 ValueError。 - 重复添加同一条边将以新权重覆盖旧权重。 """ if weight None: """ 删除边。 若边不存在则抛出 KeyError。 无向图需同时删除反向边；自环只删除一次。 """ if u not in self._adj or v not in self._adj[u]: raise KeyError(f"Edge ({u}, {v}) does not exist") del self._adj[u][v] if not self.directed and u != v: if v not in self._adj or u not in self._adj[v]: raise KeyError(f"Reverse edge ({v}, {u}) does not exist") del self._adj[v][u] # ---------------------------------------------------------------------- # 遍历算法 # ---------------------------------------------------------------------- def dfs(self, start: Any) -> List[Any]: """ 深度优先搜索（迭代实现）。 空图返回 []；起点不存在抛出 KeyError。 时间复杂度: O(V + E) 空间复杂度: O(V) （栈 + visited 集合） """ if not self._adj: return [] if start not in self._adj: raise KeyError(f"Start vertex {start} does not exist") visited: Set[Any] = set() order: List[Any] = [] stack: List[Any] = [start] while stack: u = stack.pop() if u in visited: continue visited.add(u) order.append(u) # 逆序压栈，保证邻接表原始插入顺序与遍历顺序一致 for w in reversed(list(self._adj[u].keys())): if w not in visited: stack.append(w) return order def bfs(self, start: Any)...

AI 评审点评

以下是 AI 评审对该模型输出的点评：

【CLAUDE】该实现整体质量较高，功能完整，算法实现正确，代码结构清晰，注释与复杂度标注规范。测试用例覆盖了题目要求的所有场景及多个边界情况。主要不足是空图时遍历方法对不存在起点的处理与规范略有出入（返回 [] 而非抛异常），以及无向图环检测在理论上对多重边场景存在父节点追踪的局限性（实际场景不影响）。总体而言是一份工程化质量较好的实现。 【GEMINI】这是一份卓越的工程化代码实现。作者不仅在算法层面展示了深厚的基础（如三色标记法检测环路），在工程细节上也处理得非常到位（如无向图删除边时对自环的特殊处理、弱连通分量的构建等）。代码注释清晰，完全遵循了所有的约束条件，是一份标准的资深工程师级别交付物。 【KIMI】整体上，代码实现了题目要求的所有功能，包括图的基本操作、遍历算法、最短路径、环路检测和连通分量等。算法逻辑正确，代码结构清晰，异常处理和边界场景考虑比较全面。但在部分注释和测试用例的严谨性上还有提升空间。

相关链接

您可以通过以下链接查看更多相关内容：

加载中...
100%