Paths to travel each nodes using each edge (Seven Bridges)

The problem, simply

You get islands (dots) and bridges (lines between them). Find a walk that crosses every bridge exactly once. You may visit an island many times. If no such walk exists, say so.

If the walk ends where it started, it is a closed loop. If it starts and ends on different islands, it is an open path. This is the famous Seven Bridges of Konigsberg puzzle, which Euler solved in 1736.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order of bridges by walking and backing up.

1. Pick a start island.
2. From where you stand, try each unused bridge that touches you. Cross it and keep going.
3. If every bridge is crossed, you are done. If you get stuck, un-cross the last bridge and try a different one.
4. If no start island works, there is no walk.

class EulerBacktrack {
    static int[][] roads;
    static boolean[] used;
    static List<Integer> trail;

    public static List<Integer> find(int n, int[][] edges) {
        roads = edges;
        used = new boolean[edges.length];
        for (int start = 0; start < n; start++) {
            trail = new ArrayList<>();
            trail.add(start);
            if (walk(start, 0)) return trail;
        }
        return new ArrayList<>();                      // no start works
    }

    static boolean walk(int at, int crossed) {
        if (crossed == roads.length) return true;      // every bridge used once
        for (int i = 0; i < roads.length; i++) {
            if (used[i]) continue;
            int other;
            if (roads[i][0] == at) other = roads[i][1];
            else if (roads[i][1] == at) other = roads[i][0];
            else continue;                             // this bridge does not touch us
            used[i] = true;
            trail.add(other);
            if (walk(other, crossed + 1)) return true;
            used[i] = false;                           // undo and try another bridge
            trail.remove(trail.size() - 1);
        }
        return false;
    }
}

How long it takes: in the worst case it tries every order of the bridges, about O(E!). Extra room: the used marks, the trail and the recursion, O(E). It also cannot quickly say "impossible": on Konigsberg it tries everything before giving up.

Way 2: the clever way

First use the counting rule to decide. Then build the walk with Hierholzer's trick: walk until stuck, and while backing up, write islands down. Whenever a backed-up island still has unused bridges, walk again from there. The loops slot in by themselves.

1. Count bridges at each island (its degree). If more than two are odd, there is no walk. If two are odd, start at one of them. If none is odd, start at any island with a bridge.
2. Put the start on a pile. Look at the top island. If it has an unused bridge, cross it and put the far island on the pile.
3. If it has no unused bridge, take it off the pile and add it to the trail.
4. When the pile is empty, the trail holds the walk backwards. If the trail has fewer than E + 1 islands, some bridges were in another piece, so there is no walk.

class EulerHierholzer {
    public static List<Integer> find(int n, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();     // {other end, bridge number}
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[] deg = new int[n];
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0], v = edges[i][1];
            adj.get(u).add(new int[]{v, i});
            adj.get(v).add(new int[]{u, i});
            deg[u]++;
            deg[v]++;
        }

        int odd = 0, start = -1;
        for (int i = 0; i < n; i++) {
            if (deg[i] % 2 == 1) { odd++; if (start == -1) start = i; }
        }
        if (odd != 0 && odd != 2) return new ArrayList<>();   // too many odd islands
        if (start == -1) {                                    // all even: any island with a bridge
            start = 0;
            for (int i = 0; i < n; i++) if (deg[i] > 0) { start = i; break; }
        }

        boolean[] used = new boolean[edges.length];
        int[] next = new int[n];                       // next bridge to try from each island
        Deque<Integer> pile = new ArrayDeque<>();
        List<Integer> trail = new ArrayList<>();
        pile.push(start);
        while (!pile.isEmpty()) {
            int u = pile.peek();
            while (next[u] < adj.get(u).size() && used[adj.get(u).get(next[u])[1]]) next[u]++;
            if (next[u] == adj.get(u).size()) {
                trail.add(pile.pop());                 // stuck: write this island down
            } else {
                int[] e = adj.get(u).get(next[u]);
                used[e[1]] = true;                     // cross the bridge
                pile.push(e[0]);
            }
        }
        if (trail.size() != edges.length + 1) return new ArrayList<>();  // bridges in another piece
        Collections.reverse(trail);
        return trail;
    }
}

How long it takes: the degree count is O(V + E), and each bridge is crossed once while next[u] only moves forward, so the walk is O(V + E). Extra room: the lists, the pile and the trail, O(V + E).

Watch out for

• Islands with no bridges at all do not matter. Do not fail just because a lonely island is unreachable.
• Start at an odd island when there are two. Starting at an even one gets stuck at the wrong place.
• Mark bridges as used, not islands. Islands may be visited many times.
• Repeated bridges between the same two islands (like Konigsberg) are allowed. Give each bridge its own number so both copies can be used.
• A recursive version of Hierholzer can overflow the call stack on a big graph; the pile version above cannot.

What interviewers ask next

• One-way bridges (a directed graph)? A closed loop needs in-degree equal to out-degree everywhere. An open path needs one island with one extra out and one with one extra in. LeetCode "Reconstruct Itinerary" is this with a smallest-first rule.
• Visit every island exactly once instead of every bridge? That is a Hamiltonian path, which is NP-hard. The bridges version is easy; the islands version is not.
• How many extra bridges make a closed loop possible? Pair up the odd islands; each added bridge fixes two of them, so you need odd / 2.
• A postman must walk every street and come home with the least distance. Duplicate the cheapest set of streets that pairs up the odd corners (the Chinese postman problem).
• Find the shortest string that contains every k-letter code (a de Bruijn sequence). Build a graph of k - 1 letter codes and take an Euler loop.

Remember this

Grown-up words: the islands are vertices, the bridges are edges, the number of bridges at an island is its degree, the walk is an Euler path (or Euler circuit when it is closed), the walk-and-back-up trick is Hierholzer's algorithm, and the walk pile is a stack.