CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

  • 图

    • 图理论基础
    • 图的搜索:DFS

      • 岛屿的最大面积:BFS 和 DFS 模板
      • 岛屿数量
      • 节点间通路
      • 二分图
      • 所有路径:需要存储路径的 DFS 模板
      • 单词搜索:DFS + 回溯模板
      • 计算除法
      • 最长递增路径:记忆化 DFS 模板
      • 二叉树中所有距离为 K 的结点
      • 克隆图
        • 📃 题目描述
        • 🔔 解题思路
          • DFS
          • BFS
        • 💥 复杂度分析
      • 剑指 Offer 17 - 打印从 1 到最大的 n 位数
      • 剑指 Offer 35 - 复杂链表的复制
      • 展平多级双向链表
    • 图的搜索:BFS

    • 拓扑排序

    • 并查集

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 图
  • 图的搜索:DFS
小牛肉
2022-08-31
目录

克隆图

# 📃 题目描述

题目链接:133. 克隆图 (opens new window)

# 🔔 解题思路

# DFS

对于本题而言,我们需要明确图的深拷贝是在做什么,对于一张图而言,它的深拷贝即构建一张与原图结构,值均一样的图,但是其中的节点不再是原来图节点的引用。因此,为了深拷贝出整张图,我们需要知道整张图的结构以及对应节点的值。

由于题目只给了我们一个节点的引用,因此为了知道整张图的结构以及对应节点的值,我们需要从给定的节点出发,进行「图的遍历」,并在遍历的过程中完成图的深拷贝。

为了避免在深拷贝时陷入死循环,我们需要理解图的结构。对于一张无向图,任何给定的无向边都可以表示为两个有向边,即如果节点 A 和节点 B 之间存在无向边,则表示该图具有从节点 A 到节点 B 的有向边和从节点 B 到节点 A 的有向边。

为了防止多次遍历同一个节点,陷入死循环,我们需要用一种数据结构记录已经被克隆过的节点

算法

  1. 使用一个哈希表存储所有已被访问和克隆的节点。哈希表中的 key 是原始图中的节点,value 是克隆图中的对应节点。
  2. 从给定节点开始遍历图。如果某个节点已经被访问过,则返回其克隆图中的对应节点。
  3. 如果当前访问的节点不在哈希表中,则创建它的克隆节点并存储在哈希表中。注意:在进入递归之前,必须先创建克隆节点并保存在哈希表中。如果不保证这种顺序,可能会在递归中再次遇到同一个节点,再次遍历该节点时,陷入死循环。
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    // key:原始图中的节点 value:克隆图中的节点
    private Map<Node, Node> visited = new HashMap<>();

    // 返回拷贝后的图中的 node 节点
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 克隆当前节点
        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        List<Node> neighbors = node.neighbors;
        for (Node neighbor : neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }
}

# BFS

class Solution {
    // key:原始图中的节点 value:克隆图中的节点
    private Map<Node, Node> visited = new HashMap<>();

    // 返回拷贝后的图中的 node 节点
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);

        // 克隆第一个节点
        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();

            // 遍历当前节点的邻居并更新克隆节点的邻居列表
            List<Node> neighbors = cur.neighbors;
            for (Node neighbor : neighbors) {
                if (!visited.containsKey(neighbor)) {
                    queue.offer(neighbor);

                    // 更新 visited
                    Node neighborCloneNode = new Node(neighbor.val, new ArrayList<>());
                    visited.put(neighbor, neighborCloneNode);
                }
                // 更新当前克隆节点的克隆邻居列表
                visited.get(cur).neighbors.add(visited.get(neighbor));
            }
        }

        return cloneNode;
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
二叉树中所有距离为 K 的结点
剑指 Offer 17 - 打印从 1 到最大的 n 位数

← 二叉树中所有距离为 K 的结点 剑指 Offer 17 - 打印从 1 到最大的 n 位数→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式