Euler path / circuit — Seven Bridges, Chinese Postman

Hard

Problem

(1) Decide whether an undirected graph has an Euler circuit (every edge used once, ending at the start: all degrees even) or an Euler path (exactly 0 or 2 odd-degree vertices). (2) Chinese Postman: the shortest closed walk that uses every edge at least once — pair up the odd-degree vertices and add the cheapest duplicate paths.

Example 1

Input:  edges 0–1, 0–2, 1–2, 2–3
Output: Euler path (vertices 2 and 3 have odd degree), no circuit

Also asked as: Paths to travel each nodes using each edge(Seven Bridges) · Chinese Postman or Route Inspection

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. Degree conditions + Hierholzer

Time O(E) for HierholzerSpace O(E)

An undirected connected graph has an Euler circuit iff every vertex has even degree; an Euler path iff exactly 0 or 2 vertices have odd degree (the Seven Bridges graph has 4 odd, so no path). Hierholzer’s algorithm builds the trail in O(E). Chinese Postman: pair up odd-degree vertices with minimum-weight matching and duplicate those shortest paths, then take an Euler circuit.

function hierholzer(n, adj) { // adj[u] = multiset of neighbours; assumes an Euler circuit exists
const stack = [0], circuit = [];
const local = adj.map((l) => [...l]);
while (stack.length) {
const u = stack[stack.length - 1];
if (local[u].length) {
const v = local[u].pop();
local[v].splice(local[v].indexOf(u), 1);
stack.push(v);
} else {
circuit.push(stack.pop());
}
}
return circuit.reverse();
}