Eulerian Path in undirected graph | 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
def findpath ( graph , n ) : NEW_LINE INDENT numofadj = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT numofadj . append ( sum ( graph [ i ] ) ) NEW_LINE DEDENT startpoint , numofodd = 0 , 0 NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( numofadj [ i ] % 2 == 1 ) : NEW_LINE INDENT numofodd += 1 NEW_LINE startpoint = i NEW_LINE DEDENT DEDENT if ( numofodd > 2 ) : NEW_LINE INDENT print ( " No ▁ Solution " ) NEW_LINE return NEW_LINE DEDENT stack = [ ] NEW_LINE path = [ ] NEW_LINE cur = startpoint NEW_LINE while ( len ( stack ) > 0 or sum ( graph [ cur ] ) != 0 ) : NEW_LINE INDENT if ( sum ( graph [ cur ] ) == 0 ) : NEW_LINE INDENT path . append ( cur ) NEW_LINE cur = stack [ - 1 ] NEW_LINE del stack [ - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT if ( graph [ cur ] [ i ] == 1 ) : NEW_LINE INDENT stack . append ( cur ) NEW_LINE graph [ cur ] [ i ] = 0 NEW_LINE graph [ i ] [ cur ] = 0 NEW_LINE cur = i NEW_LINE break NEW_LINE DEDENT DEDENT DEDENT DEDENT for ele in path : NEW_LINE INDENT print ( ele , end = " ▁ - > ▁ " ) NEW_LINE DEDENT print ( cur ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT 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 ] ] NEW_LINE n = len ( graph1 ) NEW_LINE findpath ( graph1 , n ) NEW_LINE 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 ] ] NEW_LINE n = len ( graph2 ) NEW_LINE findpath ( graph2 , n ) NEW_LINE 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 ] ] NEW_LINE n = len ( graph3 ) NEW_LINE findpath ( graph3 , n ) NEW_LINE DEDENT