Log inSign up
hardGeeksforGeeksNot Started

Fleury's Algorithm

Construct and print the Eulerian Path or Eulerian Circuit of a given graph using Fleury's Algorithm. Never cross a bridge unless there is no other choice.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a connected undirected graph with V vertices and a list of undirected edges that is guaranteed to contain either an Eulerian Circuit or an Eulerian Path.

Construct and return the sequence of vertices in the order they are visited along the Eulerian Trail using Fleury's Algorithm.

Fleury's principle states: 1. Start at a vertex of odd degree if one exists; otherwise start at any vertex. 2. From the current vertex u, pick an adjacent edge (u, v) such that (u, v) is not a bridge in the remaining graph, unless (u, v) is the only available edge. 3. Traverse edge (u, v), remove it from the graph, and repeat from vertex v until all edges have been traversed.

---

### Examples

Example 1: ``text Input: V = 4, edges = [[0, 1], [0, 2], [1, 2], [2, 3]] Output: [3, 2, 0, 1, 2] (or [3, 2, 1, 0, 2]) Explanation: Degrees: deg(0)=2, deg(1)=2, deg(2)=3 (odd), deg(3)=1 (odd). The path must start at either 3 or 2. Starting at 3, the only edge is (3, 2). Traverse it. From 2, edges to 0 and 1 are non-bridges in the cycle 0-1-2. Pick 0. Traverse 0 -> 1 -> 2. All 4 edges are used!

Example 2: ``text Input: V = 3, edges = [[0, 1], [1, 2], [2, 0]] Output: [0, 1, 2, 0] Explanation: All degrees are 2 (even). Any starting vertex works. Traversing 0 -> 1 -> 2 -> 0 forms a valid Eulerian Circuit.

---

### Constraints - 1 <= V <= 1000 - 1 <= edges.length <= 5000 - Graph is connected and guaranteed Eulerian.

Constraints:

  • 1 <= V <= 1000
  • 1 <= E <= 5000
  • Graph has either 0 or 2 odd-degree vertices

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the mechanics of Fleury's bridge-avoidance principle.
  • Understand why prematurely crossing a bridge disconnects the remaining trail.
  • Implement bridge detection inside an edge-deletion loop.
  • Compare Fleury's O(E2) with Hierholzer's O(V + E) algorithm.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Requirement to output the actual sequence of vertices in an Euler trail.
  • Tracing continuous paths without repeating edges.
  • Delivery routes visiting all street segments without retracing.

Algorithmic Decision Tree:

  • If only existence is needed -> Degree parity in O(V + E).
  • If constructive path requested with Fleury's -> Bridge check per edge in O(E2).
  • If maximum performance path construction requested -> Hierholzer's algorithm in O(V + E).

Connected Patterns:

Eulerian Path and CircuitReconstruct ItineraryHierholzer's AlgorithmTarjan's Bridge Algorithm

1. Backtracking Path Search with Edge Set

Intuition

Explore all permutations of edge traversals using backtracking, rolling back on dead ends until a complete length-E trail is found.

Algorithm

  1. Identify start vertex.
  2. Recursively explore unused incident edges.
  3. Track path in an array.
  4. If path length reaches E + 1, return success.
  5. Backtrack if dead end reached before consuming all E edges.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <map>
4
5using namespace std;
6
7bool backtrack(int u, int count, int totalE, const vector<vector<int>>& adj, map<pair<int, int>, int>& edgeCount, vector<int>& path) {
8 if (count == totalE) return true;
9
10 for (int v : adj[u]) {
11 pair<int, int> e = {min(u, v), max(u, v)};
12 if (edgeCount[e] > 0) {
13 edgeCount[e]--;
14 path.push_back(v);
15 if (backtrack(v, count + 1, totalE, adj, edgeCount, path)) return true;
16 path.pop_back();
17 edgeCount[e]++;
18 }
19 }
20 return false;
21}
22
23vector<int> findEulerianTrailBacktracking(int V, const vector<vector<int>>& edges) {
24 vector<vector<int>> adj(V);
25 map<pair<int, int>, int> edgeCount;
26 vector<int> degree(V, 0);
27
28 for (const auto& e : edges) {
29 adj[e[0]].push_back(e[1]);
30 adj[e[1]].push_back(e[0]);
31 edgeCount[{min(e[0], e[1]), max(e[0], e[1])}]++;
32 degree[e[0]]++;
33 degree[e[1]]++;
34 }
35
36 int start = 0;
37 for (int i = 0; i < V; ++i) {
38 if (degree[i] % 2 != 0) {
39 start = i;
40 break;
41 }
42 }
43
44 vector<int> path = {start};
45 backtrack(start, 0, edges.size(), adj, edgeCount, path);
46 return path;
47}
48
49int main() {
50 int V = 4;
51 vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
52 auto trail = findEulerianTrailBacktracking(V, edges);
53 cout << "Trail: ";
54 for (int v : trail) cout << v << " ";
55 cout << endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(V!)
  • Space complexity: O(V + E)

2. Fleury's Algorithm (Bridge Check per Edge Step)

Intuition

Step-by-step edge consumption. At vertex u, choose an edge (u, v) that is not a bridge in the current remaining graph unless it is the only remaining edge.

Algorithm

  1. Pick start vertex (an odd-degree vertex if available, else any non-zero vertex).
  2. While current vertex u has remaining edges:
  3. Find all neighbors v of u.
  4. If only one neighbor exists, pick it.
  5. Else, pick a neighbor v such that edge (u, v) is NOT a bridge (verified by DFS reachable count before and after removing (u, v)).
  6. Traverse to v, append v to path, and delete edge (u, v) bidirectionally.
  7. Set u = v.
  8. Return path.

Fleury's Bridge Check Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Start at odd vertex 3
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Path: [3, 2], remove edge (3, 2)
Why this step matters

Start at odd vertex 3. Neighbors of 3: [2]. Only 1 neighbor exists => must pick 2.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Fleury {
8 int V;
9 vector<vector<int>> adj;
10
11 void dfsCount(int u, vector<bool>& visited, int& count) {
12 visited[u] = true;
13 count++;
14 for (int v : adj[u]) {
15 if (!visited[v]) dfsCount(v, visited, count);
16 }
17 }
18
19 void removeEdge(int u, int v) {
20 auto it1 = find(adj[u].begin(), adj[u].end(), v);
21 if (it1 != adj[u].end()) adj[u].erase(it1);
22
23 auto it2 = find(adj[v].begin(), adj[v].end(), u);
24 if (it2 != adj[v].end()) adj[v].erase(it2);
25 }
26
27 void addEdge(int u, int v) {
28 adj[u].push_back(v);
29 adj[v].push_back(u);
30 }
31
32 bool isValidNextEdge(int u, int v) {
33 if (adj[u].size() == 1) return true;
34
35 vector<bool> visited(V, false);
36 int count1 = 0;
37 dfsCount(u, visited, count1);
38
39 removeEdge(u, v);
40 fill(visited.begin(), visited.end(), false);
41 int count2 = 0;
42 dfsCount(u, visited, count2);
43
44 addEdge(u, v);
45 return count1 <= count2;
46 }
47
48public:
49 Fleury(int v) : V(v), adj(v) {}
50
51 void insertEdge(int u, int v) {
52 addEdge(u, v);
53 }
54
55 vector<int> getEulerianTrail() {
56 int start = 0;
57 for (int i = 0; i < V; ++i) {
58 if (adj[i].size() % 2 != 0) {
59 start = i;
60 break;
61 }
62 }
63
64 vector<int> path = {start};
65 int curr = start;
66
67 while (!adj[curr].empty()) {
68 int nextNode = -1;
69 for (int v : adj[curr]) {
70 if (isValidNextEdge(curr, v)) {
71 nextNode = v;
72 break;
73 }
74 }
75
76 if (nextNode == -1) nextNode = adj[curr][0];
77 removeEdge(curr, nextNode);
78 path.push_back(nextNode);
79 curr = nextNode;
80 }
81
82 return path;
83 }
84};
85
86int main() {
87 int V = 4;
88 Fleury solver(V);
89 vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
90 for (const auto& e : edges) solver.insertEdge(e[0], e[1]);
91
92 auto trail = solver.getEulerianTrail();
93 cout << "Fleury Trail: ";
94 for (int v : trail) cout << v << " ";
95 cout << endl;
96 return 0;
97}

Time & Space Complexity

  • Time complexity: O(E^2)
  • Space complexity: O(V + E)

3. Hierholzer's Algorithm (Linear Postorder Stack Splicing)

Intuition

Constructs the Eulerian trail in optimal O(V + E) linear time by greedily following unused edges until a cycle closes, then backtracking onto a stack.

Algorithm

  1. Determine start vertex (odd-degree vertex if 2 exist, else any non-zero vertex).
  2. Initialize an explicit recursion call stack with start.
  3. While stack is not empty:
  4. Let u = stack.top().
  5. If u has unused incident edges:
  6. Pick neighbor v, delete edge (u, v) bidirectionally.
  7. Push v onto stack.
  8. Else (no remaining edges from u):
  9. Pop u from stack and append to trail.
  10. Reverse the trail array to obtain the forward Eulerian path.

Hierholzer's Algorithm Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Start at odd vertex 3
Visual state
Values and pointers at this exact step
table
This state table trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Decision / next transition
Traverse 3-2
Why this step matters

Start at odd vertex 3. Stack: [3].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <stack>
4#include <algorithm>
5
6using namespace std;
7
8vector<int> hierholzer(int V, const vector<vector<int>>& edges) {
9 vector<vector<int>> adj(V);
10 vector<int> deg(V, 0);
11
12 for (const auto& e : edges) {
13 adj[e[0]].push_back(e[1]);
14 adj[e[1]].push_back(e[0]);
15 deg[e[0]]++;
16 deg[e[1]]++;
17 }
18
19 int start = 0;
20 for (int i = 0; i < V; ++i) {
21 if (deg[i] % 2 != 0) {
22 start = i;
23 break;
24 }
25 }
26
27 stack<int> st;
28 vector<int> trail;
29 st.push(start);
30
31 while (!st.empty()) {
32 int u = st.top();
33 if (!adj[u].empty()) {
34 int v = adj[u].back();
35 adj[u].pop_back();
36
37 // Remove reverse edge
38 auto it = find(adj[v].begin(), adj[v].end(), u);
39 if (it != adj[v].end()) adj[v].erase(it);
40
41 st.push(v);
42 } else {
43 trail.push_back(u);
44 st.pop();
45 }
46 }
47
48 reverse(trail.begin(), trail.end());
49 return trail;
50}
51
52int main() {
53 int V = 4;
54 vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
55 auto trail = hierholzer(V, edges);
56 cout << "Optimal Hierholzer Trail: ";
57 for (int v : trail) cout << v << " ";
58 cout << endl;
59 return 0;
60}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V + E)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Exhaustive BacktrackingO(V!)O(E)Explore all permutations of edge traversals with backtrack on failure.Exploring dead-end trails.
2.Fleury's Algorithm (Bridge Check per Step)O(E^2)O(V + E)Step-by-step edge burn. At each vertex u, choose an edge that is not a bridge unless it is the only edge.DFS reachability test for candidate edges.
3.Hierholzer's Algorithm (Splice Cycles / Postorder)OptimalO(V + E)O(V + E)Follow unused edges into cycles, splice sub-tours together using recursion or an explicit stack.None. Linear time.

Common Pitfalls & Crucial Edge Cases

Starting at an even-degree node when odd-degree nodes exist

Prevents finding an Eulerian Path (guarantees getting stuck early).

Crossing a bridge when other edges exist

Strands the remaining component.

Not removing edges bidirectionally in undirected graphs

Causes double-traversal of edges.

Crucial Edge Cases to Validate:

  • Two odd vertices — Must start at one of the odd vertices.
  • Zero odd vertices — Can start at any vertex with degree > 0.
  • Single edge graph (V = 2, E = 1) — Directly outputs [0, 1] or [1, 0].
  • Disconnected degree-0 nodes — Safely skipped.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the rule clearly: Dont burn a bridge unless you have no other choice.'
  2. Highlight the start vertex rule: If odd vertices exist, you MUST start at an odd vertex.
  3. Mention that Hierholzer's algorithm solves the exact same problem in O(V + E) time.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must Fleury's algorithm avoid crossing a bridge edge if non-bridge edges are available?

2.When is an edge allowed to be crossed in Fleury's algorithm even if it is a bridge?

Back to DSA Sheet