Graphs that are not grids

An adjacency map, and traversing a structure where the nodes are objects rather than coordinates.

Key idea

Edge list to adjacency map

Problems usually hand you a list of edges, which is the wrong shape for traversal because finding a node's neighbors means scanning the whole list. Convert once, up front, into a map from node to its neighbors.

For an undirected graph add both directions. Forgetting one is a bug that makes half the graph unreachable and is invisible on symmetric test cases.

1from collections import defaultdict2 3def to_adjacency(edges, directed=False):4    graph = defaultdict(list)5    for a, b in edges:6        graph[a].append(b)7        if not directed:8            graph[b].append(a)9    return graph10 11print(dict(to_adjacency([(1, 2), (2, 3)])))12print(dict(to_adjacency([(1, 2), (2, 3)], directed=True)))

Key idea

Traversing while building a copy

Copying a graph is the Unit 7 old-to-new mapping again, with one difference: a graph has no natural order to walk in, so the copying happens during a traversal rather than in two clean passes.

The map does double duty. It records which originals have been copied, so it is the visited set, and it supplies the copy to link to when an already-seen node is reached again. One dict, two jobs.

Below is the state after one node has been copied and before anything has been linked, which is the moment that makes both jobs work.

1class Node:2    def __init__(self, val):3        self.val, self.neighbors = val, []4 5a, b = Node(1), Node(2)6a.neighbors, b.neighbors = [b], [a]       # a two-node cycle7 8made = {a: Node(a.val)}                   # a is copied, nothing linked yet9 10print("a is recorded:", a in made, " b is not:", b in made)11print("the copy is a different object:", made[a] is not a)12print("and it has no neighbors yet:", made[a].neighbors)

Keyed by the node itself, so two nodes holding the same value stay separate entries.

Predict the output· 5 min

Predict the output: the map is also the visited set

A graph whose two nodes point at each other is copied. The map from original to copy is written before any recursion happens. Type the two lines it prints.

Python

1graph = {1: [2], 2: [1]}2 3copies = {}4order = []5 6def clone(label):7    if label in copies:8        return copies[label]      # already made, and this is what stops the cycle9    copies[label] = []            # recorded before descending, not after10    order.append(label)11    for neighbor in graph[label]:12        copies[label].append(clone(neighbor))13    return copies[label]14 15clone(1)16print(order)17print(sorted(copies))

Printed output

Problem· 25 min

Clone Graph

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1class Node:2 def __init__(self, val):3 self.val, self.neighbors = val, []4 5a, b = Node(1), Node(2)6a.neighbors, b.neighbors = [b], [a] # a two-node cycle7 8made = {a: Node(a.val)} # a is copied, nothing linked yet9 10print("a is recorded:", a in made, " b is not:", b in made)11print("the copy is a different object:", made[a] is not a)12print("and it has no neighbors yet:", made[a].neighbors)

1graph = {1: [2], 2: [1]}2 3copies = {}4order = []5 6def clone(label):7 if label in copies:8 return copies[label] # already made, and this is what stops the cycle9 copies[label] = [] # recorded before descending, not after10 order.append(label)11 for neighbor in graph[label]:12 copies[label].append(clone(neighbor))13 return copies[label]14 15clone(1)16print(order)17print(sorted(copies))