:orphan:

Clone Graph
===========

.. highlight:: none

Problem
-------
https://leetcode.com/problems/clone-graph/

Given a reference of a node in a
`connected <https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph>`__
undirected graph.

Return a `deep
copy <https://en.wikipedia.org/wiki/Object_copying#Deep_copy>`__ (clone)
of the graph.

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

::


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

 

**Test case format:**

For simplicity, 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.

**An 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.

 

**Example 1:**

|image1|

::


   Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
   Output: [[2,4],[1,3],[2,4],[1,3]]
   Explanation: There are 4 nodes in the graph.
   1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
   2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
   3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
   4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

**Example 2:**

|image2|

::


   Input: adjList = [[]]
   Output: [[]]
   Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

**Example 3:**

::


   Input: adjList = []
   Output: []
   Explanation: This an empty graph, it does not have any nodes.

 

**Constraints:**

- The number of nodes in the graph is in the range ``[0, 100]``.
- ``1 <= Node.val <= 100``
- ``Node.val`` is unique for each node.
- There are no repeated edges and no self-loops in the graph.
- The Graph is connected and all nodes can be visited starting from the
  given node.

.. |image1| image:: https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png
.. |image2| image:: https://assets.leetcode.com/uploads/2020/01/07/graph.png

.. highlight:: python

Pattern
-------
Hash Table, Depth-First Search, Breadth-First Search, Graph Theory

Approaches
----------

.. tab-set::

    .. tab-item:: BFS

        **Code**

        .. literalinclude:: ../problems/medium/clone-graph/clone_graph__bfs.py
            :language: python
            :lines: 13-

        **Test**

        >>> from clone_graph__bfs import cloneGraph, Node
        >>> node1 = Node(1); node2 = Node(2); node3 = Node(3); node4 = Node(4)
        >>> node1.neighbors = [node2, node4]; node2.neighbors = [node1, node3]
        >>> node3.neighbors = [node2, node4]; node4.neighbors = [node1, node3]
        >>> clone = cloneGraph(node1)
        >>> clone is not node1 and clone.val == 1
        True
        >>> cloneGraph(None) is None
        True

        .. autoclass:: clone_graph__bfs.Node
           :members:
           :show-inheritance:
           :undoc-members:

        .. autofunction:: clone_graph__bfs.cloneGraph