详细见：leetcode.com/problems/clone-graph

Java Solution: github

package leetcode;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

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


	OJ's undirected graph serialization:
	Nodes are labeled uniquely.
	
	We use # as a separator for each node, and , as a separator for node label
	 and each neighbor of the node.
	As an example, consider the serialized graph {0,1,2#1,2#2,2}.
	
	The graph has a total of three nodes, and therefore contains three parts 
	as separated by #.
	
	First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
	Second node is labeled as 1. Connect node 1 to node 2.
	Third node is labeled as 2. Connect node 2 to node 2 (itself),
	 thus forming a self-cycle.
	Visually, the graph looks like the following:
	
	       1
	      / \
	     /   \
	    0 --- 2
	         / \
	         \_/
 */

import tools.UndirectedGraphNode辅助.UndirectedGraphNode;

/**
 * @author      zxwtry
 * @email       zxwtry@qq.com
 * @project     OJ
 * @package     leetcode
 * @file        P133_CloneGraph.java
 * @type        P133_CloneGraph
 * @date        2017年5月12日 下午12:10:45
 * @details     Solution1: AC 4ms 97.59%
 * @details     Solution2: AC 9ms 39.60%
 */
public class P133_CloneGraph {
	static class Solution1 {
	    HashMap<Integer, UndirectedGraphNode> m = new HashMap<>();
	    public UndirectedGraphNode cloneGraph(UndirectedGraphNode n) {
	        if (n == null) return null;
	        UndirectedGraphNode v = m.get(n.label);
	        if (v != null) return v;
	        v = new UndirectedGraphNode(n.label);
	        m.put(n.label, v);
	        for (UndirectedGraphNode l : n.neighbors)
	            v.neighbors.add(cloneGraph(l));
	        return v;
	    }
	}
	static class Solution2 {
	    public UndirectedGraphNode cloneGraph(UndirectedGraphNode n) {
	        if (n == null) return null;
	        HashMap<Integer, UndirectedGraphNode> m = new HashMap<>();
	        Queue<UndirectedGraphNode> q = new LinkedList<>();
	        UndirectedGraphNode ans = new UndirectedGraphNode(n.label);
	        m.put(n.label, ans);
	        q.add(n);
	        while (! q.isEmpty()) {
	            UndirectedGraphNode c = q.poll();
	            for (UndirectedGraphNode l : c.neighbors) {
	                UndirectedGraphNode v = m.get(l.label);
	                if (v == null) {
	                    q.add(l);
	                    v = new UndirectedGraphNode(l.label);
	                    m.put(l.label, v);
	                }
	                m.get(c.label).neighbors.add(v);
	            }
	        }
	        return ans;
	    }
	}
}

C Solution: github

#pragma warning(disable:4786)
/*
    url: leetcode.com/problems/clone-graph
    AC 36ms 23.81%
*/

#include <iostream>
#include <set>
#include <vector>
#include <map>

using namespace std;

struct UndirectedGraphNode {
    int label;
    vector<UndirectedGraphNode *> neighbors;
    UndirectedGraphNode(int x) : label(x) {};
};

map<UndirectedGraphNode* , UndirectedGraphNode* > m;

class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == 0) return node;
        if (m.count(node)) return m[node];
        UndirectedGraphNode *new_node = new UndirectedGraphNode(node->label);
        m[node] = new_node;
        for (int i = 0; i < node->neighbors.size(); i ++) {
           (new_node->neighbors).push_back(cloneGraph(node->neighbors[i]));
        }
        return new_node;
    }
};

Python Solution: github

#coding=utf-8

'''
    url: leetcode.com/problems/clone-graph
    @author:     zxwtry
    @email:      zxwtry@qq.com
    @date:       2017年5月15日
    @details:    Solution:  99ms 59.52%
'''

class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def search(self, n, m):
        if n == None: return n
        if n in m: return m[n]
        ng = UndirectedGraphNode(n.label)
        m[n] = ng
        for nn in n.neighbors:
            ng.neighbors.append(self.search(nn, m))
        return ng
        
    def cloneGraph(self, n):
        m = {}
        return self.search(n, m)