Clone Graph

Problem

Deep-copy a graph given as an adjacency dictionary keyed by node name.

adj maps each node to the list of its neighbors; neighbor lists must be preserved in order. Return a new dictionary with the same keys and copied neighbor lists, built by traversing the graph rather than reusing any list objects.

Hint

Traverse with a queue and create a shallow entry in the copy before expanding each node.

Test cases

case 1

in: [{"0":["1","2"],"1":["0"],"2":["0"]}]

expected: {"0":["1","2"],"1":["0"],"2":["0"]}

case 2

in: [{"0":[]}]

expected: {"0":[]}

case 3

in: [{}]

expected: {}

case 4

in: [{"0":["1"],"1":["0","2"],"2":["1"]}]

expected: {"0":["1"],"1":["0","2"],"2":["1"]}

Starter codePython

def clone_graph(adj):
    # Your code here
    pass

4 test cases · run your code against them in the editor