Graph Traversal with a Visited Map

Foundations

In the first lesson, a visited mark only had to answer yes or no: has this node been reached? Now, what if each node also needs something built for it, and every later edge to that node must find the same thing again?

Use a hash map from each node to what you built for it. A depth-first walk records a node's entry before visiting its neighbors, so when a cycle leads back, the walk finds the entry and stops instead of looping. Every edge that reaches a node later gets that same entry, so even a node shared by many neighbors is handled once.

Take adj = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3]]: nodes 0, 1, and 2 form a triangle, 2 also joins 3, and 3 joins 4. Walk from 0 and give each node the next letter in a map, name[node], before visiting its neighbors: 0 gets A, 1 gets B, 2 gets C, 3 gets D, and 4 gets E. Every later edge finds a name already there, so the triangle never loops.

• Hash Set Lookup

  This lesson's map is that lesson's hash map, keyed by node instead of by value.

  Open lesson

Case Scenario

Clone Graph gives one node of a connected, undirected graph and asks for a deep copy: new nodes with the same values and the same edges, sharing nothing with the original. What the walk builds for each node is its copy, and the map from original to copy keeps each node to a single copy. For adjList = [[2, 4], [1, 3], [2, 4], [1, 3]], a square of four nodes, the copy is the same square.

The naive copy recurses without memory: copy a node, then copy each neighbor. On the square, copying 1 copies 2, which copies 1 again, which copies 2 again, forever, because every undirected edge leads straight back. Even without cycles, a node shared by two neighbors would be copied twice, breaking the shape of the graph.