Eulerian Path in undirected graph | Efficient C ++ program to find out Eulerian path ; Function to find out the path It takes the adjacency matrix representation of the graph as input ; Find out number of edges each vertex has ; Find out how many vertex has odd number edges ; If number of vertex with odd number of edges is greater than two return " No ▁ Solution " . ; If there is a path find the path Initialize empty stack and path take the starting current as discussed ; Loop will run until there is element in the stack or current edge has some neighbour . ; If current node has not any neighbour add it to path and pop stack set new current to the popped element ; If the current vertex has at least one neighbour add the current vertex to stack , remove the edge between them and set the current to its neighbour . ; print the path ; Driver Code ; Test case 1 ; Test case 2 ; Test case 3
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findpath ( int graph [ ] [ 5 ] , int n ) { vector < int > numofadj ; for ( int i = 0 ; i < n ; i ++ ) numofadj . push_back ( accumulate ( graph [ i ] , graph [ i ] + 5 , 0 ) ) ; int startpoint = 0 , numofodd = 0 ; for ( int i = n - 1 ; i >= 0 ; i -- ) { if ( numofadj [ i ] % 2 == 1 ) { numofodd ++ ; startpoint = i ; } } if ( numofodd > 2 ) { cout << " No ▁ Solution " << endl ; return ; } stack < int > stack ; vector < int > path ; int cur = startpoint ; while ( ! stack . empty ( ) or accumulate ( graph [ cur ] , graph [ cur ] + 5 , 0 ) != 0 ) { if ( accumulate ( graph [ cur ] , graph [ cur ] + 5 , 0 ) == 0 ) { path . push_back ( cur ) ; cur = stack . top ( ) ; stack . pop ( ) ; } else { for ( int i = 0 ; i < n ; i ++ ) { if ( graph [ cur ] [ i ] == 1 ) { stack . push ( cur ) ; graph [ cur ] [ i ] = 0 ; graph [ i ] [ cur ] = 0 ; cur = i ; break ; } } } } for ( auto ele : path ) cout << ele << " ▁ - > ▁ " ; cout << cur << endl ; } int main ( ) { int graph1 [ ] [ 5 ] = { { 0 , 1 , 0 , 0 , 1 } , { 1 , 0 , 1 , 1 , 0 } , { 0 , 1 , 0 , 1 , 0 } , { 0 , 1 , 1 , 0 , 0 } , { 1 , 0 , 0 , 0 , 0 } } ; int n = sizeof ( graph1 ) / sizeof ( graph1 [ 0 ] ) ; findpath ( graph1 , n ) ; int graph2 [ ] [ 5 ] = { { 0 , 1 , 0 , 1 , 1 } , { 1 , 0 , 1 , 0 , 1 } , { 0 , 1 , 0 , 1 , 1 } , { 1 , 1 , 1 , 0 , 0 } , { 1 , 0 , 1 , 0 , 0 } } ; n = sizeof ( graph1 ) / sizeof ( graph1 [ 0 ] ) ; findpath ( graph2 , n ) ; int graph3 [ ] [ 5 ] = { { 0 , 1 , 0 , 0 , 1 } , { 1 , 0 , 1 , 1 , 1 } , { 0 , 1 , 0 , 1 , 0 } , { 0 , 1 , 1 , 0 , 1 } , { 1 , 1 , 0 , 1 , 0 } } ; n = sizeof ( graph1 ) / sizeof ( graph1 [ 0 ] ) ; findpath ( graph3 , n ) ; }