Hierholzer's algorithm
Hierholzer's algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Description
Hierholzer's Algorithm is an efficient way to find Eulerian circuits in a graph.
Algorithm: Hierholzer's Algorithm
Input: Graph G = (V, E) represented as adjacency list
Output: Eulerian circuit as ordered list of vertices
Function FindEulerianCircuit(Graph G):
// Initialize empty circuit and stack
Circuit = empty list
Stack = empty stack
// Start from any vertex with non-zero degree
current = any vertex v in V where degree(v) > 0
Push current to Stack
While Stack is not empty:
if OutDegree(current) == 0:
// Add to circuit when no more unused edges
Add current to front of Circuit
current = Pop from Stack
else:
// Follow an unused edge
Push current to Stack
next = any adjacent vertex with unused edge from current
Remove edge (current, next) from G
current = next
Return Circuit
Function VerifyEulerianCircuit(Graph G):
For each vertex v in G:
If InDegree(v) ≠ OutDegree(v):
Return false
If Graph is not strongly connected:
Return false
Return true
Main Algorithm:
1. If not VerifyEulerianCircuit(G):
Return "No Eulerian circuit exists"
2. Circuit = FindEulerianCircuit(G)
3. If Circuit contains all edges:
Return Circuit
Else:
Return "No Eulerian circuit exists"
Preconditions:
- Graph must be connected
- All vertices must have equal in-degree and out-degree
Time Complexity: O(|E|) where E is the number of edges
Space Complexity: O(|V|) where V is the number of vertices- Task
Implement the Hierholze's Algorithm in your language and test it using the same examples as in the OCaml entry.
C++
Based on code from https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
void printCircuit(vector< vector<int> > adj) {
// adj represents the adjacency list of
// the directed graph
// edge_count represents the number of edges
// emerging from a vertex
unordered_map<int,int> edge_count;
for (size_t i = 0; i < adj.size(); i++) {
//find the count of edges to keep track
//of unused edges
edge_count[i] = adj[i].size();
}
if (!adj.size())
return; //empty graph
// Maintain a stack to keep vertices
stack<int> curr_path;
// vector to store final circuit
vector<int> circuit;
// start from any vertex
curr_path.push(0);
int curr_v = 0; // Current vertex
while (!curr_path.empty()) {
// If there's remaining edge
if (edge_count[curr_v]) {
// Push the vertex
curr_path.push(curr_v);
// Find the next vertex using an edge
int next_v = adj[curr_v].back();
// and remove that edge
edge_count[curr_v]--;
adj[curr_v].pop_back();
// Move to next vertex
curr_v = next_v;
}
// back-track to find remaining circuit
else
{
circuit.push_back(curr_v);
// Back-tracking
curr_v = curr_path.top();
curr_path.pop();
}
}
// we've got the circuit, now print it in reverse
for (int i=circuit.size()-1; i>=0; i--) {
cout << circuit[i];
if (i) cout<<" -> ";
}
}
// Driver program to check the above function
int main() {
vector< vector<int> > adj1, adj2;
// First adjacency list
adj1.resize(3);
// Build the edges
adj1[0].push_back(1);
adj1[1].push_back(2);
adj1[2].push_back(0);
printCircuit(adj1);
cout << endl;
// Second adjacency list
adj2.resize(7);
adj2[0].push_back(1);
adj2[0].push_back(6);
adj2[1].push_back(2);
adj2[2].push_back(0);
adj2[2].push_back(3);
adj2[3].push_back(4);
adj2[4].push_back(2);
adj2[4].push_back(5);
adj2[5].push_back(0);
adj2[6].push_back(4);
printCircuit(adj2);
return 0;
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
Dart
import 'dart:collection';
void printCircuit(List<List<int>> adj) {
// Edge count map to track unused edges
Map<int, int> edgeCount = {};
for (var i = 0; i < adj.length; i++) {
edgeCount[i] = adj[i].length;
}
if (adj.isEmpty) return;
// Stack for current path
Queue<int> currPath = Queue<int>();
// List to store final circuit
List<int> circuit = [];
currPath.addFirst(0);
var currV = 0;
while (currPath.isNotEmpty) {
if (edgeCount[currV]! > 0) {
currPath.addFirst(currV);
var nextV = adj[currV].last;
edgeCount[currV] = edgeCount[currV]! - 1;
adj[currV].removeLast();
currV = nextV;
} else {
circuit.add(currV);
currV = currPath.first;
currPath.removeFirst();
}
}
// Print circuit in reverse
String result = circuit.reversed.join(" -> ");
print(result);
}
void main() {
// First adjacency list
var adj1 = List.generate(3, (_) => <int>[]);
adj1[0].add(1);
adj1[1].add(2);
adj1[2].add(0);
printCircuit(adj1);
// Second adjacency list
var adj2 = List.generate(7, (_) => <int>[]);
adj2[0].addAll([1, 6]);
adj2[1].add(2);
adj2[2].addAll([0, 3]);
adj2[3].add(4);
adj2[4].addAll([2, 5]);
adj2[5].add(0);
adj2[6].add(4);
printCircuit(adj2);
}
- Output:
Same as C++ entry.
FreeBASIC
' Stack implementation
Type Stack
dato(99) As Integer
top As Integer
End Type
' Stack operations
Sub initStack(st As Stack Ptr)
st->top = 0
End Sub
Function isEmpty(st As Stack Ptr) As Boolean
Return (st->top = 0)
End Function
Sub push(st As Stack Ptr, value As Integer)
st->top += 1
st->dato(st->top) = value
End Sub
Function pop(st As Stack Ptr) As Integer
Dim As Integer value = st->dato(st->top)
st->top -= 1
Return value
End Function
Function peek_(st As Stack Ptr) As Integer
Return st->dato(st->top)
End Function
' Adjacency list implementation
Type AdjList
edges(99) As Integer
count As Integer
End Type
' Subroutine to print the Eulerian circuit
Sub printCircuit(adj() As AdjList, size As Integer)
If size = 0 Then Exit Sub ' If the adjacency list is empty, we exit
Dim As Stack currPath, circuit
initStack(@currPath)
initStack(@circuit)
' Start with vertex 0
push(@currPath, 0)
While Not isEmpty(@currPath)
Dim As Integer currV = peek_(@currPath)
If adj(currV).count > 0 Then
' Get next vertex from adjacency list
Dim As Integer nextV = adj(currV).edges(1)
' Remove edge (shift remaining edges left)
For i As Integer = 1 To adj(currV).count - 1
adj(currV).edges(i) = adj(currV).edges(i + 1)
Next
adj(currV).count -= 1
push(@currPath, nextV)
Else
' Backtrack and add to circuit
push(@circuit, pop(@currPath))
End If
Wend
' Print the circuit in reverse order
While Not isEmpty(@circuit)
Print pop(@circuit);
If Not isEmpty(@circuit) Then Print " -> ";
Wend
Print
End Sub
' Main program
Sub main()
' First adjacency list
Dim adj1(0 To 2) As AdjList
With adj1(0)
.edges(1) = 1
.count = 1
End With
With adj1(1)
.edges(1) = 2
.count = 1
End With
With adj1(2)
.edges(1) = 0
.count = 1
End With
printCircuit(adj1(), 3)
' Second adjacency list
Dim adj2(0 To 6) As AdjList
With adj2(0)
.edges(1) = 1
.edges(2) = 6
.count = 2
End With
With adj2(1)
.edges(1) = 2
.count = 1
End With
With adj2(2)
.edges(1) = 0
.edges(2) = 3
.count = 2
End With
With adj2(3)
.edges(1) = 4
.count = 1
End With
With adj2(4)
.edges(1) = 2
.edges(2) = 5
.count = 2
End With
With adj2(5)
.edges(1) = 0
.count = 1
End With
With adj2(6)
.edges(1) = 4
.count = 1
End With
printCircuit(adj2(), 7)
End Sub
main()
Sleep
- Output:
0 -> 1 -> 2 -> 0 0 -> 1 -> 2 -> 0 -> 6 -> 4 -> 2 -> 3 -> 4 -> 5 -> 0
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public final class HierholzesAlgorithm {
public static void main(String[] args) {
List<List<Integer>> adjacencyList1 = new ArrayList<List<Integer>>();
adjacencyList1.addLast( Stream.of( 1 ).collect(Collectors.toList()) );
adjacencyList1.addLast( Stream.of( 2 ).collect(Collectors.toList()) );
adjacencyList1.addLast( Stream.of( 0 ).collect(Collectors.toList()) );
printCircuit(adjacencyList1);
List<List<Integer>> adjacencyList2 = new ArrayList<List<Integer>>();
adjacencyList2.addLast( Stream.of( 1, 6 ).collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 2 ) .collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 0, 3 ).collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 4 ) .collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 2, 5 ).collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 0 ) .collect(Collectors.toList()) );
adjacencyList2.addLast( Stream.of( 4 ) .collect(Collectors.toList()) );
printCircuit(adjacencyList2);
}
public static void printCircuit(List<List<Integer>> adjacencyList) {
if ( adjacencyList.isEmpty() ) {
return;
}
Stack<Integer> path = new Stack<Integer>();
List<Integer> circuit = new ArrayList<Integer>();
int currentVertex = 0; // Start at vertex 0
path.push(currentVertex);
while ( ! path.isEmpty() ) {
if ( ! adjacencyList.get(currentVertex).isEmpty() ) {
path.push(currentVertex);
final int nextVertex = adjacencyList.get(currentVertex).getLast();
adjacencyList.get(currentVertex).removeLast();
currentVertex = nextVertex;
} else { // Back-tracking
circuit.add(currentVertex);
currentVertex = path.pop();
}
}
for ( int i = circuit.size() - 1; i >= 0; i-- ) { // Print the circuit
System.out.print(circuit.get(i));
if ( i != 0 ) {
System.out.print(" => ");
}
}
System.out.println();
}
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
Julia
""" Function to print the Eulerian circuit """
function print_circuit(adj)
isempty(adj) && return # If the adjacency list is empty, do nothing
curr_path = [0] # Start with vertex 0
circuit = Int[]
while !isempty(curr_path)
curr_v = curr_path[end]
if !isempty(adj[begin + curr_v])
next_v = popfirst!(adj[begin + curr_v]) # Get next vertex from list
push!(curr_path, next_v) # Push the new vertex to curr_path stack
else
# Backtrack and add to the circuit
push!(circuit, pop!(curr_path))
end
end
# Print the circuit in reverse order
for i in length(circuit):-1:1
print(circuit[i])
i > 1 && print(" -> ")
end
println()
end
# testing code
const adj1, adj2 = Vector{Vector{Int}}(), Vector{Vector{Int}}()
# First adjacency list
push!(adj1, [1], [2], [0])
print_circuit(adj1)
# Second adjacency list
push!(adj2, [1, 6], [2], [0, 3], [4], [2, 5], [0], [4])
print_circuit(adj2)
- Output:
0 -> 1 -> 2 -> 0 0 -> 1 -> 2 -> 0 -> 6 -> 4 -> 2 -> 3 -> 4 -> 5 -> 0
OCaml
(* Function to print the Eulerian circuit *)
let print_circuit adj =
if Array.length adj = 0 then
() (* If the adjacency list is empty, do nothing *)
else
let curr_path = Stack.create () in
let circuit = Stack.create () in
(* Start with vertex 0 *)
Stack.push 0 curr_path;
while not (Stack.is_empty curr_path) do
let curr_v = Stack.top curr_path in
if adj.(curr_v) <> [] then
(* Get the next vertex from the adjacency list *)
let next_v = List.hd adj.(curr_v) in
adj.(curr_v) <- List.tl adj.(curr_v); (* Remove the edge *)
Stack.push next_v curr_path
else
(* Backtrack and add to the circuit *)
Stack.push (Stack.pop curr_path) circuit
done;
(* Print the circuit in reverse order *)
let rec print_stack s =
if not (Stack.is_empty s) then (
Printf.printf "%d" (Stack.pop s);
if not (Stack.is_empty s) then Printf.printf " -> ";
print_stack s
)
in
print_stack circuit;
Printf.printf "\n"
(* Main function *)
let () =
(* First adjacency list *)
let adj1 = Array.make 3 [] in
adj1.(0) <- [1];
adj1.(1) <- [2];
adj1.(2) <- [0];
print_circuit adj1;
(* Second adjacency list *)
let adj2 = Array.make 7 [] in
adj2.(0) <- [1; 6];
adj2.(1) <- [2];
adj2.(2) <- [0; 3];
adj2.(3) <- [4];
adj2.(4) <- [2; 5];
adj2.(5) <- [0];
adj2.(6) <- [4];
print_circuit adj2;
You may Attempt This Online!
Phix
Using 1-based indices. As with all other entries on this page, no attempt to implement VerifyEulerianCircuit().
with javascript_semantics
function hierholser(sequence adj)
integer t = 1
sequence cycle = {t}
adj = deep_copy(adj)
while length(adj[t]) do
cycle &= adj[t][$]
adj[t] = adj[t][1..$-1]
t = cycle[$]
end while
assert(sum(apply(adj,length))=0,"not all edges taken")
return cycle
end function
for adj in {{{2},{3},{1}}, {{2,7},{3},{1,4},{5},{3,6},{1},{5}}} do
printf(1,"%s\n",{join(hierholser(adj)," -> ",fmt:="%d")})
end for
- Output:
1 -> 2 -> 3 -> 1 1 -> 7 -> 5 -> 6 -> 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 1
alternative
with javascript_semantics
function hierholser(sequence adj)
sequence curr_path = {1}, // start with vertex 1
circuit = {}
adj = deep_copy(adj)
while length(curr_path) do
integer v = curr_path[$]
if length(adj[v])!=0 then
// get the next vertex from the adjacency list
integer n = adj[v][1]
adj[v] = adj[v][2..$]
curr_path &= n
else
// backtrack and add to the circuit
circuit &= v
curr_path = curr_path[1..$-1]
end if
end while
assert(sum(apply(adj,length))=0,"not all edges taken")
circuit = reverse(circuit)
return circuit
end function
for adj in {{{2},{3},{1}}, {{2,7},{3},{1,4},{5},{3,6},{1},{5}}} do
printf(1,"%s\n",{join(hierholser(adj)," -> ",fmt:="%d")})
end for
- Output:
More closely matches output of FreeBASIC, Julia, OCaml, and Wren (but still with the 1-based indices)
1 -> 2 -> 3 -> 1 1 -> 2 -> 3 -> 1 -> 7 -> 5 -> 3 -> 4 -> 5 -> 6 -> 1
PureBasic
Structure Stack
Array Data.i(100)
top.i
EndStructure
Procedure InitStack(*s.Stack)
*s\top = -1
EndProcedure
Procedure PushStack(*s.Stack, value.i)
*s\top + 1
*s\data(*s\top) = value
EndProcedure
Procedure.i PopStack(*s.Stack)
Protected value.i = *s\data(*s\top)
*s\top - 1
ProcedureReturn value
EndProcedure
Procedure.i TopStack(*s.Stack)
ProcedureReturn *s\data(*s\top)
EndProcedure
Procedure.i IsEmptyStack(*s.Stack)
ProcedureReturn Bool(*s\top = -1)
EndProcedure
Structure Graph
Array adj.i(100,100)
Array sizes.i(100)
vertices.i
EndStructure
Procedure PrintCircuit(*g.Graph)
Protected curr_path.Stack, circuit.Stack
Dim edge_count.i(100)
InitStack(@curr_path)
InitStack(@circuit)
For i = 0 To *g\vertices - 1
edge_count(i) = *g\sizes(i)
Next
PushStack(@curr_path, 0)
Protected curr_v.i = 0
While Not IsEmptyStack(@curr_path)
If edge_count(curr_v) > 0
PushStack(@curr_path, curr_v)
Protected next_v.i = *g\adj(curr_v, edge_count(curr_v) - 1)
edge_count(curr_v) - 1
curr_v = next_v
Else
PushStack(@circuit, curr_v)
curr_v = TopStack(@curr_path)
PopStack(@curr_path)
EndIf
Wend
While Not IsEmptyStack(@circuit)
Print(Str(PopStack(@circuit)));
If Not IsEmptyStack(@circuit)
Print(" -> ")
EndIf
Wend
PrintN("")
EndProcedure
OpenConsole()
Define g1.Graph
g1\vertices = 3
g1\adj(0,0) = 1 : g1\sizes(0) = 1
g1\adj(1,0) = 2 : g1\sizes(1) = 1
g1\adj(2,0) = 0 : g1\sizes(2) = 1
PrintCircuit(@g1)
Define g2.Graph
g2\vertices = 7
g2\adj(0,0) = 1 : g2\adj(0,1) = 6 : g2\sizes(0) = 2
g2\adj(1,0) = 2 : g2\sizes(1) = 1
g2\adj(2,0) = 0 : g2\adj(2,1) = 3 : g2\sizes(2) = 2
g2\adj(3,0) = 4 : g2\sizes(3) = 1
g2\adj(4,0) = 2 : g2\adj(4,1) = 5 : g2\sizes(4) = 2
g2\adj(5,0) = 0 : g2\sizes(5) = 1
g2\adj(6,0) = 4 : g2\sizes(6) = 1
PrintCircuit(@g2)
PrintN(#CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
Python
Based on code from https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
#!/usr/bin/python
# coding=UTF-8
from __future__ import print_function
def printCircuit(adj):
# adj represents the adjacency list of
# the directed graph
# edge_count represents the number of edges
# emerging from a vertex
edge_count = dict()
for i in range(len(adj)):
# find the count of edges to keep track
# of unused edges
edge_count[i] = len(adj[i])
if len(adj) == 0:
return # empty graph
# Maintain a stack to keep vertices
curr_path = []
# vector to store final circuit
circuit = []
# start from any vertex
curr_path.append(0)
curr_v = 0 # Current vertex
while len(curr_path):
# If there's remaining edge
if edge_count[curr_v]:
# Push the vertex
curr_path.append(curr_v)
# Find the next vertex using an edge
next_v = adj[curr_v][-1]
# and remove that edge
edge_count[curr_v] -= 1
adj[curr_v].pop()
# Move to next vertex
curr_v = next_v
# back-track to find remaining circuit
else:
circuit.append(curr_v)
# Back-tracking
curr_v = curr_path[-1]
curr_path.pop()
# we've got the circuit, now print it in reverse
for i in range(len(circuit) - 1, -1, -1):
print(circuit[i], end = "")
if i:
print(" -> ", end = "")
# Driver Code
if __name__ == "__main__":
# Input Graph 1
adj1 = [0] * 3
for i in range(3):
adj1[i] = []
# Build the edges
adj1[0].append(1)
adj1[1].append(2)
adj1[2].append(0)
printCircuit(adj1)
print()
# Input Graph 2
adj2 = [0] * 7
for i in range(7):
adj2[i] = []
adj2[0].append(1)
adj2[0].append(6)
adj2[1].append(2)
adj2[2].append(0)
adj2[2].append(3)
adj2[3].append(4)
adj2[4].append(2)
adj2[4].append(5)
adj2[5].append(0)
adj2[6].append(4)
printCircuit(adj2)
print()
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
Raku
say join ' -> ', .&hierholser for ([1],[2],[0]), ([1,6],[2],[0,3],[4],[2,5],[0],[4]);
sub hierholser (@graph) {
my @cycle = 0;
@cycle.push: @graph[@cycle.tail].pop while @graph[@cycle.tail].elems;
@cycle;
}
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0
You may Attempt This Online!
Wren
import "./seq" for Stack
/* Function to print the Eulerian circuit */
var printCircuit = Fn.new { |adj|
// if the adjacency list is empty, do nothing
if (adj.isEmpty) return
var currPath = Stack.new()
var circuit = Stack.new()
currPath.push(0) // start with vertex 0
while (!currPath.isEmpty) {
var currV = currPath.peek()
if (!adj[currV].isEmpty) {
// get the next vertex from the adjacency list
var nextV = adj[currV][0]
adj[currV].removeAt(0) // remove the edge
currPath.push(nextV)
} else {
// backtrack and add to the circuit
circuit.push(currPath.pop())
}
}
// print the circuit in reverse order
var printStack // recursive
printStack = Fn.new { |s|
if (!s.isEmpty) {
System.write(s.pop())
if (!s.isEmpty) System.write(" -> ")
printStack.call(s)
}
}
printStack.call(circuit)
System.print()
}
// first adjacency list
var adj1 = [ [1], [2], [0] ]
printCircuit.call(adj1)
// second adjacency list
var adj2 = [ [1, 6], [2], [0, 3], [4], [2, 5], [0], [4] ]
printCircuit.call(adj2)
- Output:
0 -> 1 -> 2 -> 0 0 -> 1 -> 2 -> 0 -> 6 -> 4 -> 2 -> 3 -> 4 -> 5 -> 0
Yabasic
// Rosetta Code problem: https://rosettacode.org/wiki/Hierholze's_Algorithm
// by Jjuanhdez, 11/2024
rem Initialize arrays and stacks
dim adj(10, 10) rem adjacency list
dim adjCnt(10) rem count of edges for each vertex
dim currPath(100) rem current path stack
dim circuit(100) rem final circuit stack
// currPathTop rem top of current path stack
// circuitTop rem top of circuit stack
rem First adjacency list
initArrays()
adj(0,0) = 1: adjCnt(0) = 1
adj(1,0) = 2: adjCnt(1) = 1
adj(2,0) = 0: adjCnt(2) = 1
printCircuit()
rem Second adjacency list
initArrays()
adj(0,0) = 1: adj(0,1) = 6: adjCnt(0) = 2
adj(1,0) = 2: adjCnt(1) = 1
adj(2,0) = 0: adj(2,1) = 3: adjCnt(2) = 2
adj(3,0) = 4: adjCnt(3) = 1
adj(4,0) = 2: adj(4,1) = 5: adjCnt(4) = 2
adj(5,0) = 0: adjCnt(5) = 1
adj(6,0) = 4: adjCnt(6) = 1
printCircuit()
end
sub initArrays()
currPathTop = 0
circuitTop = 0
for i = 0 to 9
adjCnt(i) = 0
for j = 0 to 9
adj(i,j) = -1
next j
next i
end sub
sub pushCurrPath(value)
currPath(currPathTop) = value
currPathTop = currPathTop + 1
end sub
sub popCurrPath()
currPathTop = currPathTop - 1
return currPath(currPathTop)
end sub
sub pushCircuit(value)
circuit(circuitTop) = value
circuitTop = circuitTop + 1
end sub
rem Subroutine to print the Eulerian circuit
sub printCircuit()
pushCurrPath(0)
while currPathTop > 0
currV = currPath(currPathTop - 1)
if adjCnt(currV) > 0 then
nextV = adj(currV, adjCnt(currV) - 1)
adjCnt(currV) = adjCnt(currV) - 1
pushCurrPath(nextV)
else
v = popCurrPath()
pushCircuit(v)
endif
wend
for i = circuitTop - 1 to 0 step -1
print circuit(i);
if i > 0 print " -> ";
next i
print
end sub
- Output:
0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0