LeetCode 133. Clone Graph

133. Clone Graph

Difficulty: Medium

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

Example:

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.

Note:

1. The number of nodes will be between 1 and 100.
2. The undirected graph is a , which means no repeated edges and no self-loops in the graph.
3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
4. You must return the copy of the given node as a reference to the cloned graph.

Solution

Language: Java

一边遍历点和边，一边克隆，BFS

/*
// 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;
    }
};
*/
public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> q = new LinkedList<>();
        q.offer(node);
        while (!q.isEmpty()) {
            Node tmp = q.poll();
            if (!map.containsKey(tmp)) {
                Node newNode = new Node(tmp.val, new ArrayList<>());
                map.put(tmp, newNode);
            }
            Node newNode = map.get(tmp);
            for (Node nei : tmp.neighbors) {
                if (!map.containsKey(nei)) {
                    q.offer(nei);
                    Node n = new Node(nei.val, new ArrayList<>());
                    map.put(nei, n);
                }
                newNode.neighbors.add(map.get(nei));
            }
        }
        return map.get(node);
    }
}

先复制点再遍历添加边，BFS

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> q = new LinkedList<>();
        q.offer(node);
        while (!q.isEmpty()) {
            Node tmp = q.poll();
            if (!map.containsKey(tmp)) {
                Node newNode = new Node(tmp.val, new ArrayList<>());
                map.put(tmp, newNode);
            }
            for (Node nei : tmp.neighbors) {
                if (!map.containsKey(nei)) {
                    q.offer(nei);
                }
            }
        }
        for (Node origin : map.keySet()) {
            Node nn = map.get(origin);
            for (Node neighbor : origin.neighbors) {
                nn.neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }
}

DFS

public class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        dfsHelper(node, map);
        return map.get(node);
    }
    
    private void dfsHelper(Node node, Map<Node, Node> map) {
        if (!map.containsKey(node)) {
            Node newNode = new Node(node.val, new ArrayList<>());
            map.put(node, newNode);
        }
        Node newNode = map.get(node);
        for (Node neighbor : node.neighbors) {
            if (!map.containsKey(neighbor)) {
                dfsHelper(neighbor, map);
            }
            newNode.neighbors.add(map.get(neighbor));
        } 
    }
}