LeetCode-133-克隆图

克隆图

题目描述：给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

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

示例说明请见LeetCode官网。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/clone-graph/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：深度优先遍历

首先，如果当前节点为空，不用处理，直接返回。

否则，使用一个Map即visited来存储已经处理过的图节点和相应的克隆节点，递归处理过程如下：

• 判断当前节点是否在visited中，如果在，则说明已经处理过了，则直接从visited中取出当前节点的克隆并返回。
• 否则，根据当前节点克隆出一个新的克隆节点，新克隆的节点的邻居节点初始化为空，然后将当前节点和新的克隆节点添加到visited中；
• 然后递归处理当前节点的邻居节点。

最后，返回当前节点的克隆节点。

解法二：广度优先遍历

同样的，首先，如果当前节点为空，不用处理，直接返回。

否则，也是需要初始化一个Map即visited来存储已经处理过的图节点和相应的克隆节点，首先将当前节点和由当前节点克隆的节点添加到visited中，然后将当前节点添加到一个队列queue中，然后处理队列中的节点，知道队列不为空，处理过程如下：

• 取出队列的头结点为curNode；
• 遍历处理curNode节点的邻居节点；
• 如果当前邻居节点不在visited，则将其和相应的克隆节点添加到visited中，并将其加到队列中；
• 然后将当前邻居节点的克隆节点添加到curNode的克隆节点的邻居节点列表中。

最后，返回初始节点的克隆节点。

注：图相关的算法还是了解的不多，得多学学。

import com.kaesar.leetcode.GraphNode;

import java.util.*;

public class LeetCode_133 {
    private static Map visited = new HashMap<>();

    /**
     * 深度优先遍历
     *
     * @param node 当前节点
     * @return
     */
    public static GraphNode cloneGraph(GraphNode node) {
        if (node == null) {
            return node;
        }
        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 克隆当前节点
        GraphNode cloneNode = new GraphNode(node.val, new ArrayList<>());
        // 哈希表存储
        visited.put(node, cloneNode);

        // 递归处理当前节点的邻居节点
        for (GraphNode neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }

    /**
     * 广度优先遍历
     *
     * @param node 当前节点
     * @return
     */
    public static GraphNode cloneGraph2(GraphNode node) {
        if (node == null) {
            return node;
        }

        HashMap visited = new HashMap<>();

        Queue queue = new LinkedList<>();
        // 将当前节点添加到队列中
        queue.add(node);
        // 克隆第一个节点并存储到哈希表中
        visited.put(node, new GraphNode(node.val, new ArrayList<>()));

        // 广度优先遍历
        while (!queue.isEmpty()) {
            // 取出队列的头节点
            GraphNode curNode = queue.remove();
            // 遍历当前节点的邻居节点
            for (GraphNode neighbor : curNode.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor, new GraphNode(neighbor.val, new ArrayList<>()));
                    // 将邻居节点添加到队列中
                    queue.add(neighbor);
                }

                // 更新当前节点的邻居节点列表
                visited.get(curNode).neighbors.add(visited.get(neighbor));
            }
        }

        return visited.get(node);
    }

    public static void main(String[] args) {

    }
}

【每日寄语】 自己动手，丰衣足食！