Given an undirected graph, check whether it has an Eulerian path or not. In other words, check if it is possible to construct a path that visits each edge exactly once.
An Eulerian trail is a path that visits every edge in a graph exactly once. An undirected graph has an Eulerian trail if and only if
The following graph is not Eulerian since there are four vertices with an odd in-degree (0
, 2
, 3
, 5
).
An Eulerian circuit is an Eulerian trail that starts and ends on the same vertex, i.e., the path is a cycle. An undirected graph has an Eulerian cycle if and only if
For example, the following graph has an Eulerian cycle since every vertex has an even degree.
A graph that has an Eulerian trail but not an Eulerian circuit is called Semi-Eulerian. An undirected graph is Semi-Eulerian if and only if
The following graph is Semi-Eulerian since there are exactly two vertices with an odd in-degree (0
, 1
).
The following implementation in C++, Java, and Python checks whether a given graph is Eulerian and contains an Eulerian cycle.
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Data structure to store graph edges
struct Edge {
int src, dest;
};
// Class to represent a graph object
class Graph
{
public:
// construct a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(const vector<Edge> &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Utility function to perform DFS Traversal in a graph
void DFS(const Graph &graph, int v, vector<bool> &visited)
{
// mark the current node as visited
visited[v] = true;
// do for every edge `(v -> u)`
for (int u: graph.adjList[v])
{
// if `u` is not visited
if (!visited[u]) {
DFS(graph, u, visited);
}
}
}
// Function to check if all vertices with a nonzero degree in a graph
// belong to a single connected component
bool isConnected(const Graph &graph, int N)
{
// stores vertex is visited or not
vector<bool> visited(N);
// start DFS from the first vertex with nonzero degree
for (int i = 0; i < N; i++)
{
if (graph.adjList[i].size())
{
DFS(graph, i, visited);
break;
}
}
// if a single DFS call couldn’t visit all vertices with nonzero degree,
// the graph contains more than one connected component
for (int i = 0; i < N; i++) {
if (!visited[i] && graph.adjList[i].size() > 0) {
return false;
}
}
return true;
}
// Utility function to return the number of vertices with an odd degree in a graph
int countOddVertices(const Graph &graph)
{
int count = 0;
for (vector<int> list: graph.adjList) {
if (list.size() & 1) {
count++;
}
}
return count;
}
int main()
{
// vector of graph edges as per above diagram
vector<Edge> edges = {
{0, 1}, {0, 3}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}
};
// number of nodes in the graph
int N = 5;
// create an undirected graph from given edges
Graph graph(edges, N);
// check if all vertices with nonzero degree belong to a single connected component
bool is_connected = isConnected(graph, N);
// find the number of vertices with an odd degree
int odd = countOddVertices(graph);
// Eulerian path exists if all nonzero degree vertices are connected and
// zero or two vertices have an odd degree
if (is_connected && (odd == 0 || odd == 2))
{
cout << “The Graph has an Eulerian path” << endl;
// A connected graph has an Eulerian cycle if every vertex has even degree
if (odd == 0) {
cout << “The Graph has an Eulerian cycle” << endl;
}
// The graph has an Eulerian path, but not an Eulerian cycle
else {
cout << “The Graph is Semi-Eulerian” << endl;
}
}
else {
cout << “The Graph is not Eulerian” << endl;
}
return 0;
}
|
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// data structure to store graph edges
class Edge {
int source, dest;
public Edge(int source, int dest) {
this.source = source;
this.dest = dest;
}
}
// class to represent a graph object
class Graph {
// A List of Lists to represent an adjacency list
List<List<Integer>> adjList;
// Constructor
Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
// add edges to the undirected graph
for (Edge edge: edges) {
adjList.get(edge.source).add(edge.dest);
adjList.get(edge.dest).add(edge.source);
}
}
}
class Main
{
// Utility function to perform DFS Traversal on the graph
public static void DFS(Graph graph, int v, boolean[] discovered) {
// mark current node as discovered
discovered[v] = true;
// do for every edge (v -> u)
for (int u : graph.adjList.get(v)) {
// u is not discovered
if (!discovered[u]) {
DFS(graph, u, discovered);
}
}
}
// Function to check if all vertices with nonzero degree in a graph
// belong to a single connected component
public static boolean isConnected(Graph graph, int N) {
// stores vertex is visited or not
boolean[] visited = new boolean[N];
// start DFS from the first vertex with nonzero degree
for (int i = 0; i < N; i++) {
if (graph.adjList.get(i).size() > 0) {
DFS(graph, i, visited);
break;
}
}
// if a single DFS call couldn’t visit all vertices with nonzero degree,
// the graph contains more than one connected component
for (int i = 0; i < N; i++) {
if (!visited[i] && graph.adjList.get(i).size() > 0) {
return false;
}
}
return true;
}
// Utility function to return the number of vertices in a graph
// with an odd degree
public static int countOddVertices(Graph graph) {
int count = 0;
for (List<Integer> list: graph.adjList) {
if ((list.size() & 1) == 1) {
count++;
}
}
return count;
}
public static void main(String[] args) {
// List of graph edges as per above diagram
List<Edge> edges = Arrays.asList(new Edge(0, 1), new Edge(0, 3),
new Edge(1, 2), new Edge(1, 3), new Edge(1, 4),
new Edge(2, 3), new Edge(3, 4));
// number of nodes in the graph
int N = 5;
// create an undirected graph from given edges
Graph graph = new Graph(edges, N);
// check if all vertices with nonzero degree belong to a
// single connected component
boolean is_connected = isConnected(graph, N);
// find the number of vertices with an odd degree
int odd = countOddVertices(graph);
// Eulerian path exists if all nonzero degree vertices are connected
// and zero or two vertices have an odd degree
if (is_connected && (odd == 0 || odd == 2)) {
System.out.println(“The Graph has an Eulerian path”);
// A connected graph has an Eulerian cycle if every vertex has even degree
if (odd == 0) {
System.out.println(“The Graph has an Eulerian cycle”);
}
// The graph has an Eulerian path, but not an Eulerian cycle
else {
System.out.println(“The Graph is Semi-Eulerian”);
}
}
else {
System.out.println(“The Graph is not Eulerian”);
}
}
}
|
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
# class to represent a graph object
class Graph:
def __init__(self, N, edges=[]):
# resize the lists to hold `N` elements
self.adjList = [[] for _ in range(N)]
# add an edge from source to destination
for edge in edges:
self.addEdge(edge[0], edge[1])
# Function to add an edge `u -> v` in the graph
# and update in-degree for each edge
def addEdge(self, u, v):
self.adjList[u].append(v)
self.adjList[v].append(u)
# Function to perform DFS Traversal
def DFS(graph, v, discovered):
discovered[v] = True # mark current node as discovered
# do for every edge (v -> u)
for u in graph.adjList[v]:
if not discovered[u]: # u is not discovered
DFS(graph, u, discovered)
# Function to check if all vertices with nonzero degree in a graph
# belong to a single connected component
def isConnected(graph, N):
# stores vertex is discovered or not
discovered = [False] * N
# start DFS from the first vertex with nonzero degree
for i in range(N):
if len(graph.adjList[i]):
DFS(graph, i, discovered)
break
# if a single DFS call couldn’t visit all vertices with nonzero degree,
# the graph contains more than one connected component
for i in range(N):
if not discovered[i] and len(graph.adjList[i]):
return False
return True
# Utility function to return the number of vertices with an odd degree in a graph
def countOddVertices(graph):
count = 0
for list in graph.adjList:
if len(list) & 1:
count += 1
return count
if __name__ == ‘__main__’:
# list of graph edges as per above diagram
edges = [(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
# number of nodes in the graph
N = 5
# create an undirected graph from given edges
graph = Graph(N, edges)
# check if all vertices with nonzero degree belong to a single connected component
is_connected = isConnected(graph, N)
# find the number of vertices with an odd degree
odd = countOddVertices(graph)
# Eulerian path exists if all nonzero degree vertices are connected and
# zero or two vertices have an odd degree
if is_connected and (odd == 0 or odd == 2):
print(“The Graph has an Eulerian path”)
# A connected graph has an Eulerian cycle if every vertex has even degree
if odd == 0:
print(“The Graph has an Eulerian cycle”)
# The graph has an Eulerian path, but not an Eulerian cycle
else:
print(“The Graph is Semi-Eulerian”)
else:
print(“The Graph is not Eulerian”)
|
The Graph has an Eulerian path
The Graph has an Eulerian cycle
The time complexity of the above solution is O(n+m) where n
is a number of vertices and m
is a number of edges in the graph. Depending upon how dense the graph is, the number of edges m
may vary between O(1) and O(n2).