#133. Clone Graph

題目描述

給你一個參照用的無向圖的節點。

回傳深度複製後的圖。每個圖中的節點包含了一個值(int)與相鄰的節點串列(List[ Node ])。

class Node {
　　public int val;
　　public List< Node > neighbors;
}

測試案例格式

簡單起見，每個節點值和它的節點編號一樣(從1開始)。舉例來說，第1個節點它的值也會是1，第2個節點的值則是2，以此類推。圖在測試案例中的表現方式以相鄰串列來呈現。相鄰串列是一個無序的節點串列集合用來表示一張有限圖，每個串列描述了該節點在圖中的相鄰節點。

測試案例的節點起點一定會是val=1的節點，你必須回傳複製後的圖的第一個節點作為起點。

限制條件

節點數量介於[0,100]。
1 <= 節點值 <= 100
節點值都是唯一的。
圖中不存在重複的邊與自迴圈節點。
從起點開始尋找可以找到所有圖中的節點。

解題思路

Solution

這題解決策略就是使用Hash Table來記錄新節點以及處理過的節點。首先會需要宣告兩個Hash Table，一個用來記錄新節點，一個用來紀錄處理過的節點。

每個節點要做三件事：

建立自己的複製節點。
複製節點連上相鄰的複製節點。
標示為已經處理完畢。

另外使用Queue來建立佇列，一個節點一個節點處理。

public class Solution {
    public Node CloneGraph(Node node) {
        if(node==null) return null;
        var clonedNodes = new Hashtable();
        var visited = new Hashtable();
        var q = new Queue<Node>();
        q.Enqueue(node);
        while(q.Count!=0){
            var n = q.Dequeue();
            if(visited.Contains(n.val)) continue;
            //Clone Current Node
            if(!clonedNodes.Contains(n.val)){
                clonedNodes.Add(n.val,new Node(n.val));
            }

            //Add Clone Neighbor to Cloned Node.
            var clone_n = (Node)clonedNodes[n.val];            
            foreach(var neighbor in n.neighbors){

                //If Clone Nrighbor Doesn't Exist, Clone it.
                if(!clonedNodes.Contains(neighbor.val)){
                    clonedNodes.Add(neighbor.val,new Node(neighbor.val));
                }            

                //Add Clone Neighbor.
                clone_n.neighbors.Add((Node)clonedNodes[neighbor.val]);

                //If Neighbor doesn't handle yet, Add into Queue.
                if(!visited.Contains(neighbor.val)){
                    q.Enqueue(neighbor);
                }
            }

            //Mark in handled.
            visited.Add(n.val,true);
        }
        return (Node)clonedNodes[1];
    }
}

複雜度分析：

時間複雜度：要檢查每個節點，時間複雜度為O(n)。
空間複雜度：要記錄處理過的每個節點，空間複雜度為O(n)。

學習重點

Hash Table