LeetCode -- Clone Graph

LeetCode -- Clone Graph

題目描述：


Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.


就是對一個圖進行復制。


思路：
圖遍歷可以DFS或BFS，兩種方式都可以，下面的解法是DFS的遞歸方式。當然，也可以用隊列+哈希表使用BFS完成。


1. 在哈希表hash添加圖的首節點source，和復制節點cloned（拷貝label）。
2. 復制過程：
2.1 如果source有neighbors，遍歷neighbors，對於每個neighbors[i],判斷是否在哈希存在，如果不存在，添加一份neighbor[i]的復制到哈希表中，進入遞歸；
2.2 如果已經存在，或者完成了2.1的復制步驟，將這個neighbor復制到當前map[source]對應的鄰居列表中。即map[source].neighbors.Add(map[neighbor[i]])


實現代碼：

/**
 * Definition for undirected graph.
 * public class UndirectedGraphNode {
 *     public int label;
 *     public IList neighbors;
 *     public UndirectedGraphNode(int x) { label = x; neighbors = new List(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode CloneGraph(UndirectedGraphNode node) 
    {
        if(node == null){
            return null;
        }
		
		// use a map saving source - cloned node
        var map = new Dictionary();
		
		// put root of source - cloned node into map
		var cloned = new UndirectedGraphNode(node.label);
		map.Add(node, cloned);
		
		Clone(node, ref map);
		
        return cloned;
    }
	
    private void Clone(UndirectedGraphNode source, ref Dictionary map)
    {
        for(var i = 0;i < source.neighbors.Count; i++){
            var n = source.neighbors[i];
            if(!map.ContainsKey(n))
			{
                map.Add(n, new UndirectedGraphNode(n.label));
                Clone(n, ref map);
            }
			map[source].neighbors.Add(map[n]); 
        }
    }
	
}