LeetCode-133-克隆圖

---

highlight: a11y-dark

「這是我參與11月更文挑戰的第29天，活動詳情檢視：2021最後一次更文挑戰」。

克隆圖

題目描述：給你無向 連通 圖中一個節點的引用，請你返回該圖的 深拷貝（克隆）。

圖中的每個節點都包含它的值 val（int） 和其鄰居的列表（list[Node]）。

示例說明請見LeetCode官網。

來源：力扣（LeetCode）
連結：http://leetcode-cn.com/problems/clone-graph/
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。

解法一：深度優先遍歷

首先，如果當前節點為空，不用處理，直接返回。

否則，使用一個Map即visited來儲存已經處理過的圖節點和相應的克隆節點，遞迴處理過程如下：

• 判斷當前節點是否在visited中，如果在，則說明已經處理過了，則直接從visited中取出當前節點的克隆並返回。
• 否則，根據當前節點克隆出一個新的克隆節點，新克隆的節點的鄰居節點初始化為空，然後將當前節點和新的克隆節點新增到visited中；
• 然後遞迴處理當前節點的鄰居節點。

最後，返回當前節點的克隆節點。

解法二：廣度優先遍歷

同樣的，首先，如果當前節點為空，不用處理，直接返回。

否則，也是需要初始化一個Map即visited來儲存已經處理過的圖節點和相應的克隆節點，首先將當前節點和由當前節點克隆的節點新增到visited中，然後將當前節點新增到一個佇列queue中，然後處理佇列中的節點，知道佇列不為空，處理過程如下：

• 取出佇列的頭結點為curNode；
• 遍歷處理curNode節點的鄰居節點；
• 如果當前鄰居節點不在visited，則將其和相應的克隆節點新增到visited中，並將其加到佇列中；
• 然後將當前鄰居節點的克隆節點新增到curNode的克隆節點的鄰居節點列表中。

最後，返回初始節點的克隆節點。

注：圖相關的演算法還是瞭解的不多，得多學學。

```java 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<GraphNode, GraphNode> visited = new HashMap<>();

    Queue<GraphNode> 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) {

}

} ```

【每日寄語】 自己動手，豐衣足食！