演算法-圖-克隆圖

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）。你必須將 給定節點的拷貝 作爲對克隆圖的參照返回。

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 時間複雜度

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 時間複雜度

O(N)

• 每個元素都遍歷一次

3.4 空間複雜度

O(C)