## Similar Problems

Similar Problems not available

# Clone Graph - Leetcode Solution

LeetCode: Clone Graph Leetcode Solution

Difficulty: Medium

Topics: breadth-first-search hash-table depth-first-search graph

Problem Statement:

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.

```
class Node {
public int val;
public List<Node> neighbors;
}
```

Test Input Reasoning:

We test with the minimum input first.

```
Input:
{}
Output:
{}
```

Test Output Reasoning:

Since there are no nodes in the graph, the output will also result in an empty graph.

```
GraphNode: {}
```

Test Input Reasoning:

We test the solution approach when given a graph with one node and no neighbours.

```
Input:
{0,[]}
Output:
{0,[]}
```

Test Output Reasoning:

In this test case, there is only one node in the graph and it has no neighbouring nodes. The output will result in a similar graph.

```
GraphNode: {
0
}
```

Test Input Reasoning:

We test the solution output when given a graph with one node and one neighbour.

```
Input:
{0,[[1]]}
Output
{0,[[1]]}
```

Test Output Reasoning:

In this test case, there is only one node in the graph and it has one neighbouring node. The output will result in a similar graph with the nodes interconnected properly.

```
GraphNode:{
0 --- 1
}
```

Test Input Reasoning:

We test the solution approach when given a graph with multiple nodes.

```
Input:
{0, [[1, 2], [2]], [3, 4], [4,[]], [5, [6]], [6,[]]]
Output:
{0,[[1,2],[2]],[3,4],[4,[]],[5,[6]],[6,[]]}
```

Test Output Reasoning:

In this test case, the graph has 6 nodes and each node is inter-connected with other nodes. The output will be a deep copy of the input graph preserving the node values and the edges.

```
GraphNode:{
0----1
| |
| 2
3----4
5----6
}
```

Test Input Reasoning:

We test the solution approach when given a graph with multiple nodes and varying degrees of connectivity.

```
Input:
{0, [[1,2]], [1,[2]], [2,[]]]
Output:
{0,[[1,2]],[1,[2]],[2,[]]]
```

Test Output Reasoning:

In this test case, the graph has 3 nodes and not all nodes are interconnected. The output will preserve the node values and the edges as well as the degree of connectivity from the input graph.

```
{
0--|
V
[1]--->[2]
}
```

## Clone Graph Solution Code

`1`