133.克隆图

大彬大约 1 分钟

133.克隆图

题目链接open in new window

题目描述

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

class Node {
    public int val;
    public List<Node> neighbors;
}

示例:

输入:adjList = [[2,4],[1,3],[2,4],[1,3]]
输出:[[2,4],[1,3],[2,4],[1,3]]
解释:
图中有 4 个节点。
节点 1 的值是 1,它有两个邻居:节点 24 。
节点 2 的值是 2,它有两个邻居:节点 13 。
节点 3 的值是 3,它有两个邻居:节点 24 。
节点 4 的值是 4,它有两个邻居:节点 13

解题思路

深度优先搜索。

class Solution {
    public Node cloneGraph(Node node) {
        Map<Node, Node> lookup = new HashMap<>();
        return dfs(node, lookup);
    }

    private Node dfs(Node node, Map<Node,Node> lookup) {
        if (node == null) return null;
        if (lookup.containsKey(node)) return lookup.get(node);
        Node clone = new Node(node.val, new ArrayList<>());
        lookup.put(node, clone);
        for (Node n : node.neighbors)clone.neighbors.add(dfs(n,lookup));
        return clone;
    }
}

广度优先搜索。遍历图的过程,未访问过的节点放入队列。

class Solution {
    public Node cloneGraph(Node node) {
        return bfs(node, new HashMap<Node, Node>());
    }

    private Node bfs(Node root, HashMap<Node, Node> visitedMap) {
        if (root == null) {
            return root;
        }

        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        Node cloneNode = new Node(root.val, new ArrayList<>());
        visitedMap.put(root, cloneNode);

        while (queue.size() != 0) {
            Node node = queue.poll();

            for (Node n : node.neighbors) {
                Node tmp = visitedMap.get(n);
                if (tmp == null) {
                    queue.offer(n); //未访问过的放入队列
                    tmp = new Node(n.val, new ArrayList<>());
                    visitedMap.put(n, tmp); //标记访问过
                }
                visitedMap.get(node).neighbors.add(tmp);
            }
        }

        return visitedMap.get(root);
    }
}
Loading...