咸糖记录编程的地方

念念不忘,必有回响。

目录
数据结构 4.图
/  

数据结构 4.图

133. Clone Graph

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.


Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

一看到这道题 我就想用dfs去做,传入一个引用给他进行实例化,实例化的成员变量在设置进去

但是出现了问题,会栈溢出,经过debug 突然发现这个是一个无向图,所以需要添加一个map进行去重 防止重复遍历,但是又存在一个问题,如果他是重复的但是也是一个neighbor应该如何拿到那个引用呢,这里我用一个hashMap 存入之前的引用,需要的时候获取就行了。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    Map<Integer,Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }
       
        return dfs(node);
    }
    
    public Node dfs(Node node){
        if(node == null){
            return null;
        }
         if (map.containsKey(node.val)){
             return map.get(node.val);
        }
        
        Node res =  new Node(node.val, new ArrayList<Node>());
    
        map.put(res.val,res);
        for (Node neighbor : node.neighbors) 
            res.neighbors.add(dfs(neighbor));
        return res;
        
        
    }
}

标题:数据结构 4.图
作者:xiantang
地址:http://xiantang.info/articles/2019/06/03/1559551228088.html

评论