leetcode：133. 克隆图

题目

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

  1. class Node {
  2.     public int val;
  3.     public List<Node> neighbors;
  4. }

测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：
[中等] 133. 克隆图 - 图1

  1. 输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
  2. 输出：[[2,4],[1,3],[2,4],[1,3]]
  3. 解释：
  4. 图中有 4 个节点。
  5. 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
  6. 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
  7. 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
  8. 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：
[中等] 133. 克隆图 - 图2

  1. 输入：adjList = [[]]
  2. 输出：[[]]
  3. 解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：

  1. 输入：adjList = []
  2. 输出：[]
  3. 解释：这个图是空的，它不含任何节点。

示例 4：
[中等] 133. 克隆图 - 图3

  1. 输入：adjList = [[2],[1]]
  2. 输出：[[2],[1]]

解答 & 代码

解法一：BFS + 哈希表

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> neighbors;
  7.     Node() {
  8.         val = 0;
  9.         neighbors = vector<Node*>();
  10.     }
  11.     Node(int _val) {
  12.         val = _val;
  13.         neighbors = vector<Node*>();
  14.     }
  15.     Node(int _val, vector<Node*> _neighbors) {
  16.         val = _val;
  17.         neighbors = _neighbors;
  18.     }
  19. };
  20. */
  22. class Solution {
  23. public:
  24.     Node* cloneGraph(Node* node) {
  25.         // 特殊情况：如果 node 为空，则直接返回空
  26.         if(node == nullptr)
  27.             return nullptr;
  29.         // 哈希表，key = 原图节点的指针，val = 拷贝图节点的指针
  30.         unordered_map<Node*, Node*> map;
  31.         // 队列，存储原图遍历到的节点的指针，用于 BFS 遍历
  32.         queue<Node*> nodeQ;
  33.         Node* first = new Node(node->val);    // 第一个克隆节点
  34.         map[node] = first;
  35.         nodeQ.push(node);
  36.         // BFS
  37.         while(!nodeQ.empty())
  38.         {
  39.             // 取出队列的第一个节点
  40.             Node* curNode = nodeQ.front();
  41.             nodeQ.pop();
  42.             Node* curNodeCopy = map[curNode];
  43.             // 遍历该节点的邻居
  44.             for(int i = 0; i < curNode->neighbors.size(); ++i)
  45.             {
  46.                 Node* nextNode = curNode->neighbors[i];
  47.                 // 若该节点未被访问过，则克隆，并存储到哈希表，并加入队列
  48.                 if(map.find(nextNode) == map.end())
  49.                 {
  50.                     Node* nextNodeCopy = new Node(nextNode->val);
  51.                     map[nextNode] = nextNodeCopy;
  52.                     curNodeCopy->neighbors.push_back(nextNodeCopy);
  53.                     nodeQ.push(nextNode);
  54.                 }
  55.                 // 否则，当前节点已被访问过，直接连接即可
  56.                 else
  57.                 {
  58.                     Node* nextNodeCopy = map[nextNode];
  59.                     curNodeCopy->neighbors.push_back(nextNodeCopy);
  60.                 }     
  61.             }
  62.         }
  63.         return first;
  64.     }
  65. };

复杂度分析：设原图节点数为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(N)：

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 87.07% 的用户
内存消耗：8.5 MB, 在所有 C++ 提交中击败了 84.57% 的用户

解法二：DFS