Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Test Euler Graph
// A C++ program to check if a given graph is Eulerian or not #include<iostream> #include <list> using namespace std; // A class that represents an undirected graph class Graph { int V; // No. of vertices list<int> *adj; // A dynamic array of adjacency lists public: // Constructor and destructor Graph(int V) {this->V = V; adj = new list<int>[V]; } ~Graph() { delete [] adj; } // To avoid memory leak // function to add an edge to graph void addEdge(int v, int w); // Method to check if this graph is Eulerian or not int isEulerian(); // Method to check if all non-zero degree vertices are connected bool isConnected(); // Function to do DFS starting from v. Used in isConnected(); void DFSUtil(int v, bool visited[]); }; void Graph::addEdge(int v, int w) { adj[v].push_back(w); adj[w].push_back(v); // Note: the graph is undirected } void Graph::DFSUtil(int v, bool visited[]) { // Mark the current node as visited and print it visited[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited); } // Method to check if all non-zero degree vertices are connected. // It mainly does DFS traversal starting from bool Graph::isConnected() { // Mark all the vertices as not visited bool visited[V]; int i; for (i = 0; i < V; i++) visited[i] = false; // Find a vertex with non-zero degree for (i = 0; i < V; i++) if (adj[i].size() != 0) break; // If there are no edges in the graph, return true if (i == V) return true; // Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); // Check if all non-zero degree vertices are visited for (i = 0; i < V; i++) if (visited[i] == false && adj[i].size() > 0) return false; return true; } /* The function returns one of the following values 0 --> If grpah is not Eulerian 1 --> If graph has an Euler path (Semi-Eulerian) 2 --> If graph has an Euler Circuit (Eulerian) */ int Graph::isEulerian() { // Check if all non-zero degree vertices are connected if (isConnected() == false) return 0; // Count vertices with odd degree int odd = 0; for (int i = 0; i < V; i++) if (adj[i].size() & 1) odd++; // If count is more than 2, then graph is not Eulerian if (odd > 2) return 0; // If odd count is 2, then semi-eulerian. // If odd count is 0, then eulerian // Note that odd count can never be 1 for undirected graph return (odd)? 1 : 2; } // Function to run test cases void test(Graph &g) { int res = g.isEulerian(); if (res == 0) cout << "graph is not Eulerian\n"; else if (res == 1) cout << "graph has a Euler path\n"; else cout << "graph has a Euler cycle\n"; } // Driver program to test above function int main() { // Let us create and test graphs shown in above figures Graph g1(5); g1.addEdge(1, 0); g1.addEdge(0, 2); g1.addEdge(2, 1); g1.addEdge(0, 3); g1.addEdge(3, 4); test(g1); Graph g2(5); g2.addEdge(1, 0); g2.addEdge(0, 2); g2.addEdge(2, 1); g2.addEdge(0, 3); g2.addEdge(3, 4); g2.addEdge(4, 0); test(g2); Graph g3(5); g3.addEdge(1, 0); g3.addEdge(0, 2); g3.addEdge(2, 1); g3.addEdge(0, 3); g3.addEdge(3, 4); g3.addEdge(1, 3); test(g3); // Let us create a graph with 3 vertices // connected in the form of cycle Graph g4(3); g4.addEdge(0, 1); g4.addEdge(1, 2); g4.addEdge(2, 0); test(g4); // Let us create a graph with all veritces // with zero degree Graph g5(3); test(g5); return 0; }
run
|
edit
|
history
|
help
0
PalindromePair-s1
Dar
Bin Tree playground
Reminder
Best time to buy and sell stocks
c++
Dar
std_minmax_unexpected_behaviour.cpp
Complete Over-Use of Functor Templates (Academic Experiment)
runtime template mode processor