Check whether an undirected graph is Eulerian
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.
1. Eulerian trail (or Eulerian path, or Euler walk)
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
- Exactly zero or two vertices have odd degree, and
- All of its vertices with a non-zero degree belong to a single connected component.
The following graph is not Eulerian since four vertices have an odd in-degree (0, 2, 3, 5):
2. Eulerian circuit (or Eulerian cycle, or Euler tour)
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
- Every vertex has an even degree, and
- All of its vertices with a non-zero degree belong to a single connected component.
For example, the following graph has an Eulerian cycle since every vertex has an even degree:
3. Semi–Eulerian
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
- Exactly two vertices have odd degree, and
- All of its vertices with a non-zero degree belong to a single connected component.
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 130 131 132 133 134 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; // Data structure to store a graph edge struct Edge { int src, dest; }; // A class to represent a graph object class Graph { public: // a vector of vectors to represent an adjacency list vector<vector<int>> adjList; // Graph Constructor Graph(vector<Edge> const &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 on the graph on a graph void DFS(Graph const &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 non-zero degree in a graph // belong to a single connected component bool isConnected(Graph const &graph, int n) { // to keep track of whether a vertex is visited or not vector<bool> visited(n); // start DFS from the first vertex with a non-zero 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 a non-zero 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 total number of vertices with an odd degree // in a graph int countOddVertices(Graph const &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 the above diagram vector<Edge> edges = { {0, 1}, {0, 3}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4} }; // total number of nodes in the graph (labelled from 0 to 4) int n = 5; // create an undirected graph from the given edges Graph graph(edges, n); // check if all vertices with a non-zero degree belong to a single // connected component bool is_connected = isConnected(graph, n); // find the total number of vertices with an odd degree int odd = countOddVertices(graph); // An Eulerian path exists if all non-zero 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 an 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 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; // A class to store a graph edge class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // A 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 the current node as discovered discovered[v] = true; // do for every edge (v, u) for (int u: graph.adjList.get(v)) { // if `u` is not yet discovered if (!discovered[u]) { DFS(graph, u, discovered); } } } // Function to check if all vertices with a non-zero degree in a graph // belong to a single connected component public static boolean isConnected(Graph graph, int n) { // to keep track of whether a vertex is visited or not boolean[] visited = new boolean[n]; // start DFS from the first vertex with a non-zero 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 a non-zero 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 total 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 the 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)); // total number of nodes in the graph (labelled from 0 to 4) int n = 5; // create an undirected graph from the given edges Graph graph = new Graph(edges, n); // check if all vertices with a non-zero degree belong to a // single connected component boolean is_connected = isConnected(graph, n); // find the total number of vertices with an odd degree int odd = countOddVertices(graph); // An Eulerian path exists if all non-zero 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 an // 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 91 92 93 |
# A class to represent a graph object class Graph: def __init__(self, n, edges=[]): # resize the list 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) to the graph def addEdge(self, u, v): self.adjList[u].append(v) self.adjList[v].append(u) # Function to perform DFS traversal on the graph on a graph def DFS(graph, v, discovered): discovered[v] = True # mark the current node as discovered # do for every edge (v, u) for u in graph.adjList[v]: if not discovered[u]: # if `u` is not yet discovered DFS(graph, u, discovered) # Function to check if all vertices with a non-zero degree in a graph # belong to a single connected component def isConnected(graph, n): # to keep track of whether a vertex is discovered or not discovered = [False] * n # start DFS from the first vertex with a non-zero 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 a non-zero 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 total 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 the above diagram edges = [(0, 1), (0, 3), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)] # total number of nodes in the graph (labelled from 0 to 4) n = 5 # create an undirected graph from the given edges graph = Graph(n, edges) # check if all vertices with a non-zero degree belong to a single # connected component is_connected = isConnected(graph, n) # find the total number of vertices with an odd degree odd = countOddVertices(graph) # An Eulerian path exists if all non-zero 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 # an 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(V × E), where V and E are the total number of vertices and edges in the graph, respectively. Depending upon how dense the graph is, the total number of edges E may vary between O(1) and O(V2).
Also See:
References: Eulerian path – Wikipedia
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)