# 133.Clone-Graph

## 133. Clone Graph

## 题目地址

<https://leetcode.com/problems/clone-graph/>

<https://www.jiuzhang.com/solutions/clone-graph/>

## 题目描述

```
Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

// 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;
    }
};

Test case format:

For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
```

## 代码

### Approach #1 DFS

```java
class Solution {
    private HashMap <Node, Node> visited = new HashMap <> ();
    public Node cloneGraph(Node node) {
        if (node == null)     return node;

        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        Node cloneNode = new Node(node.val, new ArrayList());
        visited.put(node, cloneNode);

        for (Node neighbor: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}
```

### Approach #2 BFS

```java
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null)   return node;

        HashMap<Node, Node> visited = new HashMap();
        visited.put(node, new Node(node.val, new ArrayList()));

        LinkedList<Node> queue = new LinkedList<Node> ();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node n = queue.remove();

            for (Node neighbor: n.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    // Clone the neighbor and put in the visited, if not present already
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
                    // Add the newly encountered node to the queue.
                    queue.add(neighbor);
                }
                // Add the clone of the neighbor to the neighbors of the clone node "n".
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }

        // Return the clone of the node from visited.
        return visited.get(node);
    }
}
```

// 九章

### Approach #1

```java
class UndirectedGraphNode {
  int label;
  ArrayList<UndirectedGraphNode> neighbors;
  UndirectedGraphNode(int x) { 
    label = x; 
    neighbors = new ArrayList<UndirectedGraphNode>(); 
  }
};

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return node;

    ArrayList<UndirectedGraphNode> nodes = getNodes(node);

    HashMap<UndirectedGraphNode, UndirectedGraphNode> mapping = new HashMap<>();
    for (UndirectedGraphNode n : nodes) {
      mapping.put(n, new UndirectedGraphNode(n.label));
    }

    for (UndirectedGraphNode n : nodes) {
      UndirectedGraphNode newNode = mapping.get(n);
      for (UndirectedGraphNode neighbor : n.neighbors) {
        UndirectedGrapNode newNeighbor = mapping.get(neighbor);
        newNode.neighbors.add(newNeighbor);
      }
    }

    return mapping.get(node);
  }

  private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
    Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    HashSet<UndirectedGraphNode> set = new HashSet<>();

    queue.offer(node);
    set.add(node);
    while (!queue.isEmpty()) {
      UndirectedGraphNode head = queue.poll();
      for (UndirectedGraphNode neighbor : head.neighbors) {
        if (!set.contains(neighbor)) {
          set.add(neighbor);
          queue.offer(neighbor);
        }
      }
    } 

    return new ArrayList<UndirectedGraphNode>(set);
  }
}
```

### Approach #2

```java
public class Solution {
  public UndirectedGraphNode cloneGraph(UndirectedGraphNode noe) {
    if (node == null) return null;

    ArrayList<UndirectedGraphNode> nodes = new ArrayList<UndirectedGraphNode>();
    HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

    nodes.add(node);
    map.put(node, new UndirectedGraphNode(node.label));

    int start = 0;
    while (start < nodes.size()) {
      UndirectedGraphNode head = nodes.get(start++);
      for (int i = 0; i < head.neighbors.size(); i++) {
        UndirectedGraphNode neighbor = head.neighbors.get(i);
        if (!map.containsKey(neighbor)) {
          map.put(neighbor, new UndirectedGraphNode(neighbor.label));
          nodes.add(neighbor);
        }
      }
    }

    for (int i = 0; i < nodes.size(); i++) {
      UndirectedGraphNode newNode = map.get(nodes.get(i));
      for (int j = 0; j < nodes.get(i).neighbors.size(); j++) {
        newNode.neighbors.add(map.get(nodes.get(i).neighbors.get(j)));
      }
    }

    return map.get(node);
  }
}
```

### Using Stack

```java
class StackElement {
  public UndirectedGraphNode node;
  public int neighborIndex;
  public StackElement(UndirectedGraphNode node, int neighborIndex) {
    this.node = node;
    this.neighborIndex = neighborIndex;
  }
}

private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
  Stack<StackElement> stack = new Stack<StackElement>();
  HashSet<UndirectedGraphNode> set = new HashSet<>();
  stack.push(new StackElement(node, -1));
  set.add(node);

  while (!stack.isEmpty()) {
    StackElement current = stack.peek();
    current.neighborIndex++;

    if (current.neighborIndex == current.node.neighbors.size()) {
      stack.pop();
      continue;
    }

    UndirectedGraphNode neighbor = current.node.neighbors.get(current.neighborIndex);

    if (set.contains(neighbor))    continue;

    stack.push(new StackElement(neighbor, -1));
    set.add(neighbor);
  }

  return new ArrayList<UndirectedGraphNode>(set);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/graph-search/133.clone-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.