算法-图-克隆图

小鱼儿 2022-11-26 12:57 156阅读 0赞

# 算法-图-克隆图 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/clone-graph/

## 1.2 题目描述 ##

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list\[Node\]）。

class Node \{  
public int val;  
public List neighbors;  
\}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]

# 2 BFS #

## 2.1 思路 ##

1.  将给定的入口Node克隆，并放入Queue开始BFS
2.  使用一个长度101的数组`cloneNodes`记录已经访问、克隆过的Node，下标就是Node的val
3.  每次从Queue内取出一个Node，并遍历其neighbors，如果已访问过的直接从cloneNodes\[val\]取来加入到当前遍历Node的克隆的neighbors list中；如果没访问过，就克隆该Node，并加入cloneNodes，当然也要放入Queue等待BFS遍历。
4.  直到Queue变为空，遍历结束，返回初始cloneNode即可

## 2.2 代码 ##

/* // 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 { 
        public Node cloneGraph(Node node) { 
            if(node == null){ 
                return null;
            }
            Node[] cloneNodes = new Node[101];
    
            Queue<Node> queue = new LinkedList<>(); 
            Node cNode = new Node(node.val, (ArrayList<Node>)node.neighbors);
            cloneNodes[cNode.val] = cNode;
            queue.add(cNode);
            
            while(queue.size() > 0){ 
                Node cloneNode = queue.poll();
                List<Node> cloneList = new ArrayList<>();
                for(Node ne : cloneNode.neighbors){ 
                    if(cloneNodes[ne.val] == null){ 
                        ne = new Node(ne.val, (ArrayList<Node>)ne.neighbors);
                        queue.add(ne);
                        cloneNodes[ne.val] = ne;
                    } else{ 
                        ne = cloneNodes[ne.val];
                    }
                    cloneList.add(ne);
                }
                cloneNode.neighbors = cloneList;
            }
            return cNode;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200812114343492.png_pic_center]  
O(N)

*  每个元素都遍历一次

## 2.4 空间复杂度 ##

`O(C)`

# 3 DFS #

## 3.1 思路 ##

1.  跟BFS一样，使用一个长度101的数组`cloneNodes`记录已经访问、克隆过的Node，下标就是Node的val
2.  从给定元素开始DFS，如果该元素在cloneNodes中存在就直接返回，否则就克隆并遍历其neighbors进行dfs，并将结果加入到新的list
3.  最后返回该克隆的node即为结果

## 3.2 代码 ##

/* // 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 { 
        Node[] cloneNodes = new Node[101];
        public Node cloneGraph(Node node) { 
            if(node == null){ 
                return null;
            }
           
            return dfs(node);
        }
    
        private Node dfs(Node node){ 
            // 优先从缓存取
            if(cloneNodes[node.val] != null){ 
                return cloneNodes[node.val];
            }
            // 缓存没有就克隆一个
            ArrayList<Node> cloneList = new ArrayList<>();
            Node cNode = new Node(node.val, cloneList);
            cloneNodes[node.val] = cNode;
    
            for(Node ne : node.neighbors){ 
                cloneList.add(dfs(ne));
            }
            return cNode;
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][2020081212253623.png_pic_center]

O(N)

*  每个元素都遍历一次

## 3.4 空间复杂度 ##

`O(C)`

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/a13e1e7ca73d4b22a27c0b783391195b.png
[20200812114343492.png_pic_center]: /images/20221124/946811f553bc4a12ab87d38ac213800c.png
[2020081212253623.png_pic_center]: /images/20221124/b940cf3559d2496097f6f6df1b770205.png