Graph traversal with a visited set

When to use it

Use it when things are joined by links that may form a loop, and you must reach, check or copy everything connected to a start, in any order.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

A list gives, for each of six pupils numbered 0 to 5, the pupils whose phone numbers they have. Pupil 0 hears some news, and everyone who hears it calls all their numbers. Return the pupils who never hear it.

Input
knows = [[1, 2], [0, 3], [3], [1], [0, 5], [4]]

Output
[4, 5]

The method

1. Mark pupil 0 as visited and put that pupil on a waiting list
2. While pupils wait on the list, take one and read who they call
3. Skip someone already visited: nobody is handled twice
4. Someone new is marked as visited and joins the list
5. The list is empty: return the pupils who are not in the set

The run, one moment at a time

1. Step 1. Pupil 0 hears the news first. Mark 0 as visited and put 0 on the list. An arrow from one pupil to another means the first can call the second.

   list: 0
   visited: 0
   

2. Step 2. Take pupil 0 from the list. Pupil 0 has the numbers of 1 and 2.

   list: empty
   visited: 0
   

3. Step 4. Pupils 1 and 2 are not in the visited set, so the news is new to them. Mark them as visited and add them to the list.

   list: 1 2
   visited: 0 1 2
   

4. Step 2. Take pupil 2 from the list. It was added last. Any other order would reach the same pupils. Pupil 2 has the number of 3.

   list: 1
   visited: 0 1 2
   

5. Step 4. Pupil 3 is not in the visited set, so the news is new to 3. Mark 3 as visited and add 3 to the list.

   list: 1 3
   visited: 0 1 2 3
   

6. Step 2. Take pupil 3 from the list. Pupil 3 has the number of 1.

   list: 1
   visited: 0 1 2 3
   

7. Step 3. Pupil 1 is in the visited set already. A call to 1 would bring nothing new, so skip 1. Pupil 1 still waits on the list and will be handled once, from there.

   list: 1
   visited: 0 1 2 3
   

8. Step 2. Take pupil 1 from the list. Pupil 1 has the numbers of 0 and 3.

   list: empty
   visited: 0 1 2 3
   

9. Step 3. Pupils 0 and 3 are in the visited set already. A call to them would bring nothing new, so skip them. Without the set, 1 would call 0, 0 would call 1 again, and the walk would never end.

   list: empty
   visited: 0 1 2 3
   

10. Step 5. The list is empty, so the set holds everyone the news reaches: 0, 1, 2 and 3. Pupils 4 and 5 are not in it. Pupil 4 can call 0, but nobody who heard the news can call 4.

    list: empty
    visited: 0 1 2 3
    missed: 4 5
    

The code

The numbered comments are the steps of the method.

function solve(knows) {
  // 1. Mark pupil 0 as visited and put that pupil on a waiting list
  const visited = new Set([0]);
  const waiting = [0];
  // 2. While pupils wait on the list, take one and read who they call
  while (waiting.length) {
    // pop takes the newest. Any order reaches the same pupils.
    const pupil = waiting.pop();
    for (const other of knows[pupil]) {
      // 3. Skip someone already visited: nobody is handled twice
      if (visited.has(other)) continue;
      // 4. Someone new is marked as visited and joins the list
      visited.add(other);
      waiting.push(other);
    }
  }
  // 5. The list is empty: return the pupils who are not in the set
  const missed = [];
  for (let pupil = 0; pupil < knows.length; pupil++) {
    if (!visited.has(pupil)) missed.push(pupil);
  }
  return missed;
}

def solve(knows):
    # 1. Mark pupil 0 as visited and put that pupil on a waiting list
    visited = {0}
    waiting = [0]
    # 2. While pupils wait on the list, take one and read who they call
    while waiting:
        # pop takes the newest. Any order reaches the same pupils.
        pupil = waiting.pop()
        for other in knows[pupil]:
            # 3. Skip someone already visited: nobody is handled twice
            if other in visited:
                continue
            # 4. Someone new is marked as visited and joins the list
            visited.add(other)
            waiting.append(other)
    # 5. The list is empty: return the pupils who are not in the set
    missed = []
    for pupil in range(len(knows)):
        if pupil not in visited:
            missed.append(pupil)
    return missed

How to spot it

Given: Each item has a list of the items it is joined to

That is a graph. From any item you can step to its neighbors, then to theirs, and so reach everything connected to it.

Given: The links may lead round in a circle

A walk with no memory would go round for ever. The visited set ends it: a node already in the set is not entered again.

Asked: Can every node be reached from the first one?

Walk from the first node and mark what you meet. Then compare the number of marked nodes with the number of nodes.

Asked: Make a copy of every node, with the same links

Keep a map from each node to its copy. It is the visited record, and it also gives the copy that a link must point to.

Looks like it, but is not

• You need the fewest links between two nodes, not only whether a way exists. Use Breadth-first search by distance. A plain walk reaches nodes in no order of distance. For the fewest links, nearer nodes must be handled before farther ones.
• The nodes are the cells of a grid, and you count or measure groups of joined cells. Use Grid connected components. It is the same walk, but the neighbors are the four cells beside a cell, and the mark can be written into the grid itself.
• Links arrive one at a time, and after each you must say whether two nodes are joined. Use Union-find. A walk would have to start again after every new link. Union-find keeps the groups up to date and answers at once.

Cost and mistakes

Time grows with the nodes plus the links, written O(V + E) for V nodes and E links: each node leaves the list once, and each link is read once. Extra space is the visited set and the list, at most V entries each.

Watch out

• Mark a node as visited when you add it to the list, not when you take it off. Otherwise several neighbors can add the same node before it is marked, and it is handled more than once.
• A one-way link is followed only from its start. When links go both ways, list each one for both of its nodes, or half of the neighbors are never seen.

In the 150

4 problems of the 150 use it. Naming them gives their method away, so the list is folded.