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”)
|
Output:
The Graph has an Eulerian path
The Graph has an Eulerian cycle
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).