LeetCode 133 克隆图 在 C 语言中的实现主要难点在于图可能存在环需要用哈希表或数组记录已克隆的节点。C 语言没有自动垃圾回收和容器需要手动“malloc” 分配内存并正确管理指针。LeetCode 中节点值“val” 是 1 到 100 的唯一整数因此可以用数组直接作为映射表。C 语言中的图节点定义LeetCode 官方提供// Definition for a Node.struct Node {int val;int numNeighbors;struct Node** neighbors;};方法一DFS深度优先搜索递归思路使用数组“visited[101]” 存储“原节点val - 克隆节点指针” 的映射。递归时如果节点已克隆则直接返回否则创建新节点、记录到数组、再递归克隆邻居。#include stdlib.h// 递归辅助函数struct Node* dfs(struct Node* node, struct Node** visited) {if (node NULL) {return NULL;}// 如果已经克隆过直接返回克隆节点的指针 if (visited[node-val] ! NULL) { return visited[node-val]; } // 创建新节点并分配内存 struct Node* clone (struct Node*)malloc(sizeof(struct Node)); clone-val node-val; clone-numNeighbors node-numNeighbors; // 关键先存入 visited再递归防止环导致死循环 visited[node-val] clone; // 为邻居数组分配内存 if (clone-numNeighbors 0) { clone-neighbors (struct Node**)malloc( sizeof(struct Node*) * clone-numNeighbors ); for (int i 0; i clone-numNeighbors; i) { // 递归克隆每个邻居 clone-neighbors[i] dfs(node-neighbors[i], visited); } } else { clone-neighbors NULL; } return clone;}// LeetCode 入口函数struct Node* cloneGraph(struct Node* s) {if (s NULL) {return NULL;}// 假设节点 val 范围是 1~100初始化为 NULL struct Node* visited[101] {NULL}; return dfs(s, visited);}方法二BFS广度优先搜索迭代思路使用队列可以用数组模拟或链表实现进行广度遍历。同样利用“visited” 数组记录映射遇到未访问的邻居就创建新节点并入队。#include stdlib.h// 简单队列结构用数组实现#define MAX_NODES 101struct Node* cloneGraph(struct Node* s) {if (s NULL) return NULL;struct Node* visited[101] {NULL}; // 创建队列 struct Node* queue[MAX_NODES]; int front 0, rear 0; // 克隆起始节点 struct Node* clone_start (struct Node*)malloc(sizeof(struct Node)); clone_start-val s-val; clone_start-numNeighbors s-numNeighbors; visited[s-val] clone_start; queue[rear] s; while (front rear) { struct Node* cur queue[front]; // 为当前克隆节点分配邻居数组 if (cur-numNeighbors 0) { visited[cur-val]-neighbors (struct Node**)malloc( sizeof(struct Node*) * cur-numNeighbors ); } else { visited[cur-val]-neighbors NULL; } // 遍历所有邻居 for (int i 0; i cur-numNeighbors; i) { struct Node* neighbor cur-neighbors[i]; if (visited[neighbor-val] NULL) { // 如果邻居未克隆创建新节点并加入队列 struct Node* new_neighbor (struct Node*)malloc(sizeof(struct Node)); new_neighbor-val neighbor-val; new_neighbor-numNeighbors neighbor-numNeighbors; visited[neighbor-val] new_neighbor; queue[rear] neighbor; } // 将邻居的克隆体加入当前节点克隆体的 neighbors visited[cur-val]-neighbors[i] visited[neighbor-val]; } } return clone_start;}关键点解析难点 解决方案防止环导致无限递归 在递归/BFS 之前就把新节点指针存入“visited” 数组哈希映射 利用“val” 唯一且在“1~100” 的特性用数组代替哈希表内存分配 每个克隆节点和“neighbors” 数组都需要“malloc”注意“numNeighbors 0” 时置为“NULL”返回深拷贝 所有节点和边都是新分配的原图和克隆图完全独立复杂度分析时间复杂度“O(N)”每个节点和每条边只会被访问一次。空间复杂度“O(N)”“visited” 数组、“malloc” 的克隆图、以及递归栈/BFS 队列均占用“O(N)” 空间。⚠️ 注意LeetCode 的判题系统会自动检测内存泄漏但通常在算法题中只要正确“malloc” 且逻辑无误即可通过。如果是在生产环境需要配套实现图的销毁函数。如果需要我补充 图的销毁free函数 或 通用哈希表实现可以继续提问
)
