企业官网建设流程全解析

LeetCode 133 克隆图 在 C 语言中的实现，主要难点在于：

1. 图可能存在环，需要用哈希表（或数组）记录已克隆的节点。
2. C 语言没有自动垃圾回收和容器，需要手动
   “malloc” 分配内存，并正确管理指针。
3. 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 101

struct 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）函数 或 通用哈希表实现，可以继续提问！