How do you clone a graph when it may contain cycles?
You make a new node for every node in the original, and you use a map to remember which new node goes with which old one. That map is what lets you handle cycles.
So what goes wrong without the map? If you follow the neighbours and make a new node for each one as you reach it, then a cycle makes you go round for ever. You would make a new copy of a node that you had already copied, and then copy that one again, and on and on.
the graph A -> B -> C -> A
without a map you make A, then B, then C, then A again,
then B again, and you never stop
with a map when you reach A the second time you use the
copy you already made
And so the rule is simple. Before you make a copy of a node, you check whether you have already made one. If you have then you use it. And if you have not then you make it, you put it in the map, and then you go on to its neighbours.
And there is another detail that matters for an undirected graph. The edges go both ways, so when you copy the neighbours of A you also have to make sure that the copies of A are added to the neighbour lists of the copied neighbours. The usual way to handle this is to make the copy of a node and add it to the map first, and then to fill in its neighbours afterwards.
mapping = {}
copy = Node(node.value)
mapping[node] = copy # put it in the map before you go deeper
for neighbour in node.neighbours:
copy.neighbours.append(clone(neighbour, mapping))
And the complexity is O of n plus m for the time, where n is the number of nodes and m is the number of edges, because every node is copied once and every edge is copied once. And the space is O of n for the map and the copies.
So the rule to remember is this. Put the copy in the map before you go on to the neighbours, and the cycles take care of themselves.
The next two questions in this topic show the code for the map version and for the neighbour list version.