LeetCode-133-克隆圖

語言: CN / TW / HK

highlight: a11y-dark

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

克隆圖

題目描述:給你無向 連通 圖中一個節點的引用,請你返回該圖的 深拷貝(克隆)。

圖中的每個節點都包含它的值 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的克隆節點的鄰居節點列表中。

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

:圖相關的演算法還是瞭解的不多,得多學學。

```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) {

}

} ```

【每日寄語】 自己動手,豐衣足食!