Clone Graph - Leetcode Solution

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]
}

1