133. 克隆图

题意：

解题思路：

思路：DFS

PHP代码实现：

/*
// Definition for a Node.
class Node {
    public $val;
    public $neighbors;
    @param Integer $val 
    @param list<Node> $neighbors 
    function __construct($val, $neighbors) {
        $this->val = $val;
        $this->neighbors = $neighbors;
    }
}
*/
class Solution {
    /**
     * @param Node $node
     * @return Node
     */
    function cloneGraph($node) {
        $map = new SplObjectStorage();
        return $this->dfs($node, $map);
    }
    function dfs($node, &$map) {
        if($node == null) return null;
        if($map->contains($node)) return $map[$node];
        $clone = new Node($node->val, []);
        $map[$node] = $clone;
        foreach($node->neighbors as $neighbor){
            $clone->neighbors[] = $this->dfs($neighbor, $map);
        }
        return $clone;
    }
}

GO代码实现：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */
func cloneGraph(node *Node) *Node {
    visited := make(map[*Node]*Node)
    return cloneNode(node, visited)
}
func cloneNode(node *Node, visited map[*Node]*Node) *Node {
    if node == nil {
        return nil
    }
    if n, ok := visited[node]; ok {
        return n
    }
    c := &Node{Val: node.Val}
    visited[node] = c
    for _, ne := range node.Neighbors {
        c.Neighbors = append(c.Neighbors, cloneNode(ne, visited))
    }
    return c
}