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
using System ; using System . Collections . Generic ; class GFG { static void findpath ( int [ , ] graph , int n ) { List < int > numofadj = new List < int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) numofadj . Add ( accumulate ( graph , i , 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 ) { Console . WriteLine ( " No ▁ Solution " ) ; return ; } Stack < int > stack = new Stack < int > ( ) ; List < int > path = new List < int > ( ) ; int cur = startPoint ; while ( stack . Count != 0 || accumulate ( graph , cur , 0 ) != 0 ) { if ( accumulate ( graph , cur , 0 ) == 0 ) { path . Add ( cur ) ; cur = 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 ; } } } } foreach ( int ele in path ) Console . Write ( ele + " ▁ - > ▁ " ) ; Console . WriteLine ( cur ) ; } static int accumulate ( int [ , ] matrix , int row , int sum ) { int [ ] arr = GetRow ( matrix , row ) ; foreach ( int i in arr ) sum += i ; return sum ; } public static int [ ] GetRow ( int [ , ] matrix , int row ) { var rowLength = matrix . GetLength ( 1 ) ; var rowVector = new int [ rowLength ] ; for ( var i = 0 ; i < rowLength ; i ++ ) rowVector [ i ] = matrix [ row , i ] ; return rowVector ; } public static void Main ( String [ ] args ) { int [ , ] graph1 = { { 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 = graph1 . GetLength ( 0 ) ; findpath ( graph1 , n ) ; int [ , ] graph2 = { { 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 = graph2 . GetLength ( 0 ) ; findpath ( graph2 , n ) ; int [ , ] graph3 = { { 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 = graph3 . GetLength ( 0 ) ; findpath ( graph3 , n ) ; } }