133. 克隆图（Clone Graph）——C语言实现深拷贝

题目描述

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。
图中的每个节点都包含它的值val和其邻居的列表neighbors。

• 节点类定义：

struct Node { int val; int numNeighbors; struct Node** neighbors; };

• 测试用例格式：

  • 节点的值和索引相同，方便测试。

  • 邻接列表表示图。

示例：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]] 输出：[[2,4],[1,3],[2,4],[1,3]]

提示：

• 节点数量在 [0,100]。

• 1 <= Node.val <= 100，唯一。

• 无重复边和自环。

• 图是连通的。

解题思路

本题可以抽象为“图的深拷贝”问题。
由于是无向图，克隆过程中需要注意避免重复创建节点，否则会进入无限递归。

核心思路：

1. 图遍历：可以使用 DFS 或 BFS。

2. 哈希表记录已克隆节点：避免重复创建。这里题目给出val范围 [1,100]，所以可以用数组模拟哈希表。

3. 深拷贝节点及其邻居：递归/队列遍历。

DFS 实现（C语言）

核心函数

#include <stdlib.h> // DFS 克隆 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* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->val = node->val; newNode->numNeighbors = node->numNeighbors; newNode->neighbors = (struct Node**)malloc(sizeof(struct Node*) * node->numNeighbors); // 记录映射 visited[node->val] = newNode; // 递归克隆所有邻居 for (int i = 0; i < node->numNeighbors; i++) { newNode->neighbors[i] = dfs(node->neighbors[i], visited); } return newNode; }

主函数

struct Node *cloneGraph(struct Node *s) { if (s == NULL) return NULL; // 使用数组作为哈希表（val 范围 1~100） struct Node* visited[101] = {0}; return dfs(s, visited); }

示例解析

以输入[[2,4],[1,3],[2,4],[1,3]]为例：

原图结构：

1 -- 2 | | 4 -- 3

DFS 克隆过程：

1. 克隆节点 1

2. 遍历邻居 2 → 克隆 2

3. 2 的邻居 1 已经克隆 → 直接引用

4. 遍历邻居 3 → 克隆 3

5. 遍历邻居 4 → 克隆 4

6. 4 的邻居 1、3 已经克隆 → 直接引用

7. 完成克隆

最终得到一个深拷贝图。

时间复杂度与空间复杂度

• 时间复杂度：O(N + E)

  • 每个节点和每条边只访问一次

• 空间复杂度：O(N)

  • 递归栈 + 哈希表（visited）存储

注意点

1. 必须使用 visited 数组，防止重复创建节点导致无限递归。

2. 先记录 visited 再递归克隆邻居，保证引用正确。

3. neighbors 指针数组必须分配内存：

newNode->neighbors = malloc(sizeof(struct Node*) * node->numNeighbors);

1. 空图或单节点图需要特殊处理：

if (s == NULL) return NULL;

总结

• 这题是图的深拷贝，本质是DFS/BFS + 哈希表映射。

• DFS 简洁，BFS 更适合面试考察队列实现。

• C语言实现要注意内存分配和避免重复创建节点。