Skip to content
wannacode

DFS: islands and cycles

In short: DFS (depth-first search) follows one path as far as it goes and then backtracks, with recursion or a stack; it finds connected components and cycles in a graph in O(V + E).

Problem

A city cut by the river

The city closes both bridges for repairs. The couriers can no longer cross the river, and the dispatcher has to know how many parts the city falls into and which stops are in each part: every part will be served by a separate van.

From the BFS lesson you know how to find what can be reached from the depot. But there may be many parts, and each one has to be found whole. You need a walk that starts from every stop that has no part yet and marks everything it reaches.

There is a second problem in the same city. The delivery plan has rules "A is delivered before B". Someone added a wrong rule, and now there is no order that keeps all of them. Which rule is to blame?

The idea

As far as the street goes

DFS (depth-first search) walks like a person in a maze: it takes the first street to an unknown stop, from there the first one to the next unknown stop, and so on, until it reaches a stop around which everything has been seen. Then it goes back one stop and tries that stop's next street.

With recursion the going back happens by itself: visit for a stop calls visit for its first unknown neighbour, and when that one finishes, the loop carries on with the next. The call stack remembers how far every stop has got.

  • Every stop gets the number of its island as soon as it is entered. This is also the set of seen stops: a stop with a number is not visited a second time.
  • An island (a connected component) is everything one visit reaches. The loop over all stops runs a new visit from every stop without a number.

See it

Down and back

function visit(graph, stop, island, islandOf) {
  islandOf.set(stop, island);
  for (const next of graph.get(stop)) {
    if (!islandOf.has(next)) {
      visit(graph, next, island, islandOf);
    }
  }
}


function islands(graph, stops) {
  const islandOf = new Map();
  let count = 0;
  for (const stop of stops) {
    if (islandOf.has(stop)) continue;
    count++;
    visit(graph, stop, count, islandOf);
  }
  return islandOf;
}

function visit(graph, stop, island, islandOf) {
  islandOf.set(stop, island);
  for (const next of graph.get(stop)) {
    if (!islandOf.has(next)) {
      visit(graph, next, island, islandOf);
    }
  }
}


function islands(graph, stops) {
  const islandOf = new Map();
  let count = 0;
  for (const stop of stops) {
    if (islandOf.has(stop)) continue;
    count++;
    visit(graph, stop, count, islandOf);
  }
  return islandOf;
}
Step by step, in words
  1. Both bridges are closed. islands goes through the stops in order: Depot has no island yet, so count = 1 and visit starts from it.
  2. visit(Depot) marks it with island 1 and goes straight into its first neighbour without an island: Station. Depot waits grey on the call stack.
  3. Deeper and deeper: Station → Square → Market. Four calls are open at once, and each waits for the one above it.
  4. Around Market everything already has an island. visit returns and Market turns black. Back up the stack: Square and Station have nothing new either.
  5. Depot is back on top. Its last neighbour Market is already seen, so the first walk ends: island 1 is Depot, Station, Market, Square. The closed bridges stopped it at the river.
  6. The loop in islands goes on: Station, Market and Square already have an island and are skipped. Park has none: count = 2.
  7. The same walk on the other bank: Park → Stadium → Hospital → Cinema, then back to Park.
  8. Two islands: 4 stops on each bank. Every stop got a number once and every street was looked at from both ends: O(V + E).

The program closes the bridges, runs islands and prints the islands:

const closed = [
  ["Market", "Park"], ["Square", "Cinema"],
];
for (const [a, b] of closed) {
  graph.set(a, graph.get(a).filter((s) => s !== b));
  graph.set(b, graph.get(b).filter((s) => s !== a));
}
const islandOf = islands(graph, stops);
const count = Math.max(...islandOf.values());
console.log(`Islands: ${count}`);
for (let i = 1; i <= count; i++) {
  const members = stops.filter((s) => islandOf.get(s) === i);
  console.log(`Island ${i}: ${members.join(", ")}`);
}
Output
Islands: 2
Island 1: Depot, Station, Market, Square
Island 2: Park, Cinema, Hospital, Stadium

The island number is kept in a Map, and their count is the largest number in it.

Try it

Predict the output

The bridge Market – Park is open, but there are roadworks around Cinema: Square – Cinema and Cinema – Hospital are closed. How many islands does the program print?

const closed = [
  ["Square", "Cinema"], ["Cinema", "Hospital"],
];
for (const [a, b] of closed) {
  graph.set(a, graph.get(a).filter((s) => s !== b));
  graph.set(b, graph.get(b).filter((s) => s !== a));
}
const islandOf = islands(graph, stops);
const count = Math.max(...islandOf.values());
console.log(`Islands: ${count}`);
Answer

The idea

Your own stack instead of recursion

Here the islands have 4 stops each, and the recursion is 4 calls deep. In a grid city of 100,000 crossroads a depth-first walk can go tens of thousands of levels down, and every level is a frame on the call stack. The stack is small and overflows. How recursion becomes a loop is in the lesson "From recursion to a loop". Here it is the same: the stack becomes an ordinary collection.

function walk(graph, start) {
  const order = [];
  const seen = new Set();
  const stack = [start];
  while (stack.length > 0) {
    const stop = stack.pop();
    if (seen.has(stop)) continue;
    seen.add(stop);
    order.push(stop);
    const next = graph.get(stop);
    for (let i = next.length - 1; i >= 0; i--) {
      if (!seen.has(next[i])) stack.push(next[i]);
    }
  }
  return order;
}

Two things differ from the recursion:

  • A stop can enter the stack twice: from two neighbours, before it is visited. That is why the check "has it been seen" is also done when it is taken: the second time it is skipped.
  • The neighbours go in in reverse. The last one put in comes out first, so the first neighbour has to be on top. That way the order is the same as with recursion:
const islandOf = new Map();
visit(graph, "Depot", 1, islandOf);
console.log(`Recursion: ${[...islandOf.keys()].join(", ")}`);
console.log(`Own stack: ${walk(graph, "Depot").join(", ")}`);
Output
Recursion: Depot, Station, Square, Market, Park, Stadium, Hospital, Cinema
Own stack: Depot, Station, Square, Market, Park, Stadium, Hospital, Cinema
More precisely, if you are curious

If you push the neighbours in the order of the list, the walk is still depth-first and still finds the same islands, only the order of visits is different. For the islands the order does not matter. For cycles in a directed graph below it does: there you need to know when every stop finishes, and with a stack of stops that is harder. That is why findCycle is recursive, and for deep graphs the stack holds a pair (stop, how far it has got in its list).

The idea

A cycle in the delivery plan

The rules of the plan are a directed graph: the arrow Market → Park means "Market before Park". If the arrows form a cycle, there is no order that keeps them: every stop in the cycle has to come before itself.

"Seen" alone is not enough to catch a cycle. Market → Square leads to a seen stop, but there is no cycle: you cannot get from Square back to Market. That is why stops have three colours:

  • white: not seen yet;
  • grey: on the current path, its call is still open;
  • black: everything after it is checked, and there is no cycle.

An arrow to a grey stop leads back into your own path: that is the cycle.

function findCycle(plan, stop, color, path) {
  color.set(stop, "grey");
  path.push(stop);
  for (const next of plan.get(stop)) {
    const c = color.get(next) ?? "white";
    if (c === "grey") {
      return [...path.slice(path.indexOf(next)), next];
    }
    if (c === "white") {
      const found = findCycle(plan, next, color, path);
      if (found !== null) return found;
    }
  }
  color.set(stop, "black");
  path.pop();
  return null;
}

function findCycle(plan, stop, color, path) {
  color.set(stop, "grey");
  path.push(stop);
  for (const next of plan.get(stop)) {
    const c = color.get(next) ?? "white";
    if (c === "grey") {
      return [...path.slice(path.indexOf(next)), next];
    }
    if (c === "white") {
      const found = findCycle(plan, next, color, path);
      if (found !== null) return found;
    }
  }
  color.set(stop, "black");
  path.pop();
  return null;
}
Step by step, in words
  1. Every arrow is a rule: the stop it starts from is delivered first. All stops are white, nobody has been seen yet. The walk starts at Depot.
  2. Grey means on the current path: Depot → Station → Square. These calls are still open.
  3. No rules leave Square: it turns black, everything after it is checked, and it leaves the path. Station is done too.
  4. Market also points to Square, but Square is black: there is no way from it back to Market. Two rules into the same stop are not a cycle.
  5. Across the river the path grows: Park → Cinema → Hospital → Stadium, all grey.
  6. Stadium → Park: Park is grey, it is still on the path. The arrow leads back into the path itself, and that is a cycle.
  7. The cycle is the path from Park to the end: Park → Cinema → Hospital → Stadium → Park. No order of these four stops keeps every rule, so the rule Stadium → Park must go.

The loop runs findCycle from every white stop, as islands runs visit:

function anyCycle(plan, stops) {
  const color = new Map();
  for (const stop of stops) {
    if (color.has(stop)) continue;
    const found = findCycle(plan, stop, color, []);
    if (found !== null) return found;
  }
  return null;
}
const rules = [
  ["Depot", "Station"], ["Station", "Square"],
  ["Depot", "Market"], ["Market", "Square"],
  ["Market", "Park"], ["Park", "Cinema"],
  ["Cinema", "Hospital"], ["Hospital", "Stadium"],
  ["Stadium", "Park"],
];
const cycle = anyCycle(plan, stops);
console.log(cycle === null ? "No cycle" : `Cycle: ${cycle.join(" → ")}`);
Output
Cycle: Park → Cinema → Hospital → Stadium → Park

Remove the last rule, and the program prints No cycle. Then the order in which the stops turn black is the delivery order reversed. Topological sorting, the next lesson, is built on that.

function findCycle(plan, stop, color, path) {
  color.set(stop, "grey");
  path.push(stop);
  for (const next of plan.get(stop)) {
    const c = color.get(next) ?? "white";
    if (c === "grey") {
      return [...path.slice(path.indexOf(next)), next];
    }
    if (c === "white") {
      const found = findCycle(plan, next, color, path);
      if (found !== null) return found;
    }
  }
  color.set(stop, );
  path.pop();
  return null;
}
More precisely, if you are curious

In an undirected graph every street is an arrow in both directions, and the neighbour you came from is always "seen". There a cycle exists if you reach a seen stop that is not the one you have just come from. The three colours are needed for a directed graph.

The idea

What it costs

Every stop gets a number once and is visited once. When visited, it looks at its streets, and a two-way street is seen from both ends. In total: V visits and 2E looks, O(V + E), the same as BFS.

It is linear only if the island number is shared by the whole walk. If for every stop you ask "which island am I on?" with a new walk and an empty set of seen stops, you make n walks. Run both on a grid city of n crossroads that the river cuts in two:

  • One shared islandOf for the whole city O(n)
  • A fresh walk for every crossroad O(n²)
Algorithmn = 10n = 1,000n = 2,000n = 100,000
One shared islandOf for the whole city284,8089,730498,100
A fresh walk for every crossroad1482,405,4409,730,980≈ 24,327,450,000
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.
function islands(graph, stops) {
  const islandOf = new Map();
  let count = 0;
  for (const stop of stops) {
    if (islandOf.has(stop)) continue;
    count++;
    visit(graph, stop, count, islandOf);
  }
  return islandOf;
}

Every stop taken from the stack and every look at a neighbour is counted. Both use their own stack: at 100,000 crossroads recursion in the browser crashes with a stack overflow. At 1000 crossroads the shared number makes 4,808 operations, and a new walk for every crossroad 2,405,440. At 2000 the new walk is already at 9,730,980, while the shared one at 100,000 makes 498,100.

Try it

Find the bug

A colleague decided that in visit the island should grow with every step. The program prints:

function visit(graph, stop, island, islandOf) {
  islandOf.set(stop, island);
  for (const next of graph.get(stop)) {
    if (!islandOf.has(next)) {
      visit(graph, next, island + 1, islandOf);
    }
  }
}
Output
Islands: 5
Island 1: Depot
Island 2: Station, Park
Island 3: Square, Stadium
Island 4: Market, Hospital
Island 5: Cinema

There are five islands, and Station and Park are "on one island", although the bridges are closed. Which line has the bug?

Pick the line with the bug.

More precisely

How deep recursion can go

JavaScript engines stop recursion at about 10,000 levels (depending on the browser and the size of the frame) with RangeError: Maximum call stack size exceeded. An array with push and pop is a stack with O(1) at the end and has no such limit.

Exercise

The critical streets

Solve the task in your editor.

Critical streets. The bridge Market – Park is closed for a month, and Square – Cinema still works. A street is critical if closing it splits the city into more islands. Close the bridge, print how many islands there are, then for every open street remove it, count the islands with islands and put it back. Print the critical streets in the order of streets.

const closed = [
  ["Market", "Park"],
];
Output
Islands: 1
Critical: Square - Cinema, Cinema - Hospital, Park - Stadium, Hospital - Stadium

More tasks

  • The biggest island. Print the island with the most stops and how many van hours a week it needs if every stop takes 3 hours.
  • The cycle in the plan. Write findCycle with your own stack: put a pair (stop, index of the next neighbour) on the stack, and the stop turns black when the index reaches the end of its list.
  • Islands on the map. The warehouse map is a grid of # (shelf) and . (free). Count the free zones, where the neighbours of a cell are up, down, left and right.

Test

Check yourself

1. What does DFS do when everything around the current stop has already been seen?
2. Why does islands go through all stops instead of running visit only from the depot?
3. In the directed plan findCycle sees an arrow to a black stop. Is it a cycle?
4. The city has 100,000 crossroads in one long chain. What happens to the recursive visit?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·