Eulerian Path

An Eulerian path in a graph is a path that traverses every edge exactly once. It starts and ends at different vertices.

An Eulerian path exists in an undirected graph if at most two vertices have odd degree, and all other vertices have even degree. For directed graphs, all vertices must have equal in degree and out degree.

Finding Eulerian paths has applications in graph theory and recreation like the Seven Bridges of Königsberg problem.

Example in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Undirected graph  
int[][] graph = {
  {0, 1},
  {1, 2},
  {2, 0},
  {0, 3},
  {3, 4} 
};

List<Integer> eulerPath = getEulerPath(graph); // e.g. [0, 1, 2, 0, 3, 4]

// Check degrees
int[] degrees = countDegrees(graph); 
int oddCount = countOdds(degrees); // 2

Example in C++:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// Directed graph 
vector<pair<int, int>> graph {
  {0, 1},
  {1, 2}, 
  {2, 0},
  {2, 3},
  {3, 1}
};

vector<int> path = getEulerPath(graph); // e.g. [2, 3, 1, 0, 1, 2]

// Check in/out degrees
map<int, int> inOut = getInOutDegrees(graph);  
bool balanced = inOutBalanced(inOut); // true

Example in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# Undirected graph
graph = {
  0: [1, 4],
  1: [0, 2],
  2: [1, 3],
  3: [2, 4],
  4: [0, 3]
}  

path = find_euler_path(graph) # e.g. [0, 4, 3, 2, 1, 0]

degrees = count_degrees(graph)  
num_odd = sum(d % 2 for d in degrees) # 2

In summary, an Eulerian path traverses all edges in a graph exactly once. It exists for graphs with balanced vertex degrees.

An Eulerian path is a trail in a finite graph that visits every edge exactly once. If the path starts and ends on the same vertex, it’s called an Eulerian cycle. Eulerian paths and cycles are named after the Swiss mathematician Leonhard Euler.

In mathematical terms, a finite graph has an Eulerian cycle if and only if all vertices have an even degree, and the graph is connected. For an Eulerian path, exactly zero or two vertices should have an odd degree.

Example Code in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.LinkedList;
import java.util.Stack;

public class EulerianPath {
    private int vertices;
    private LinkedList<Integer>[] adj;

    EulerianPath(int vertices) {
        this.vertices = vertices;
        adj = new LinkedList[vertices];
        for (int i = 0; i < vertices; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    void printEulerianPath() {
        Stack<Integer> stack = new Stack<>();
        LinkedList<Integer> path = new LinkedList<>();

        stack.push(0);

        while (!stack.isEmpty()) {
            int current = stack.peek();
            if (adj[current].size() > 0) {
                int next = adj[current].removeFirst();
                adj[next].remove((Integer) current);
                stack.push(next);
            } else {
                path.addFirst(stack.pop());
            }
        }

        for (int i : path) {
            System.out.print(i + " ");
        }
    }

    public static void main(String[] args) {
        EulerianPath graph = new EulerianPath(4);

        graph.addEdge(0, 1);
        graph.addEdge(0, 3);
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 3);

        graph.printEulerianPath();
    }
}

Example Code in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class EulerianPath {
public:
    vector<vector<int>> adj;
    int vertices;

    EulerianPath(int n) : vertices(n), adj(n, vector<int>()) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void printEulerianPath() {
        stack<int> s;
        vector<int> path;
        s.push(0);

        while (!s.empty()) {
            int current = s.top();
            if (!adj[current].empty()) {
                int next = adj[current].back();
                adj[current].pop_back();
                s.push(next);
            } else {
                path.push_back(current);
                s.pop();
            }
        }

        for (int node : path) {
            cout << node << " ";
        }
    }
};

int main() {
    EulerianPath graph(4);

    graph.addEdge(0, 1);
    graph.addEdge(0, 3);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 3);

    graph.printEulerianPath();
    return 0;
}

Example Code in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from collections import deque

class EulerianPath:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def print_eulerian_path(self):
        stack = []
        path = deque()

        stack.append(0)

        while stack:
            current = stack[-1]
            if self.adj[current]:
                next_vertex = self.adj[current].pop()
                self.adj[next_vertex].remove(current)
                stack.append(next_vertex)
            else:
                path.appendleft(stack.pop())

        print(" ".join(map(str, path)))

if __name__ == "__main__":
    graph = EulerianPath(4)
    graph.add_edge(0, 1)
    graph.add_edge(0, 3)
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_edge(2, 3)

    graph.print_eulerian_path()

The implementation uses Depth-First Search (DFS) to find the Eulerian Path. We use a stack to keep track of the vertices as we go along the path. When we find that a vertex has no more edges to explore, we start backtracking.