Euler path / circuit — Seven Bridges, Chinese Postman
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.
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();}