Comment on page

# 133.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

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) {
}
return cloneNode;
}
}

### Approach #2 BFS

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()));
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.
}
// Add the clone of the neighbor to the neighbors of the clone node "n".
}
}
// Return the clone of the node from visited.
return visited.get(node);
}
}
// 九章

### Approach #1

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);
}
}
return mapping.get(node);
}
private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
HashSet<UndirectedGraphNode> set = new HashSet<>();
queue.offer(node);
while (!queue.isEmpty()) {
for (UndirectedGraphNode neighbor : head.neighbors) {
if (!set.contains(neighbor)) {
queue.offer(neighbor);
}
}
}
return new ArrayList<UndirectedGraphNode>(set);
}
}

### Approach #2

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>();
map.put(node, new UndirectedGraphNode(node.label));
int start = 0;
while (start < nodes.size()) {
for (int i = 0; i < head.neighbors.size(); i++) {
if (!map.containsKey(neighbor)) {
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
}
}
}
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++) {
}
}
return map.get(node);
}
}

### Using Stack

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));
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));