Hierholzer 's Algorithm for directed graph | Python3 program to print Eulerian circuit in given directed graph using Hierholzer algorithm ; adj represents the adjacency list of the directed graph edge_count represents the number of edges emerging from a vertex ; find the count of edges to keep track of unused edges ; empty graph Maintain a stack to keep vertices ; vector to store final circuit ; start from any vertex ; Current vertex ; If there 's remaining edge ; Push the vertex ; Find the next vertex using an edge ; and remove that edge ; Move to next vertex ; back - track to find remaining circuit ; Back - tracking ; we 've got the circuit, now print it in reverse ; Driver Code ; Input Graph 1 ; Build the edges ; Input Graph 2
def printCircuit ( adj ) : NEW_LINE INDENT edge_count = dict ( ) NEW_LINE for i in range ( len ( adj ) ) : NEW_LINE INDENT edge_count [ i ] = len ( adj [ i ] ) NEW_LINE DEDENT if len ( adj ) == 0 : NEW_LINE INDENT return NEW_LINE DEDENT curr_path = [ ] NEW_LINE circuit = [ ] NEW_LINE curr_path . append ( 0 ) NEW_LINE curr_v = 0 NEW_LINE while len ( curr_path ) : NEW_LINE INDENT if edge_count [ curr_v ] : NEW_LINE INDENT curr_path . append ( curr_v ) NEW_LINE next_v = adj [ curr_v ] [ - 1 ] NEW_LINE edge_count [ curr_v ] -= 1 NEW_LINE adj [ curr_v ] . pop ( ) NEW_LINE curr_v = next_v NEW_LINE DEDENT else : NEW_LINE INDENT circuit . append ( curr_v ) NEW_LINE curr_v = curr_path [ - 1 ] NEW_LINE curr_path . pop ( ) NEW_LINE DEDENT DEDENT for i in range ( len ( circuit ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT print ( circuit [ i ] , end = " " ) NEW_LINE if i : NEW_LINE INDENT print ( " ▁ - > ▁ " , end = " " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT adj1 = [ 0 ] * 3 NEW_LINE for i in range ( 3 ) : NEW_LINE INDENT adj1 [ i ] = [ ] NEW_LINE DEDENT adj1 [ 0 ] . append ( 1 ) NEW_LINE adj1 [ 1 ] . append ( 2 ) NEW_LINE adj1 [ 2 ] . append ( 0 ) NEW_LINE printCircuit ( adj1 ) NEW_LINE print ( ) NEW_LINE adj2 = [ 0 ] * 7 NEW_LINE for i in range ( 7 ) : NEW_LINE INDENT adj2 [ i ] = [ ] NEW_LINE DEDENT adj2 [ 0 ] . append ( 1 ) NEW_LINE adj2 [ 0 ] . append ( 6 ) NEW_LINE adj2 [ 1 ] . append ( 2 ) NEW_LINE adj2 [ 2 ] . append ( 0 ) NEW_LINE adj2 [ 2 ] . append ( 3 ) NEW_LINE adj2 [ 3 ] . append ( 4 ) NEW_LINE adj2 [ 4 ] . append ( 2 ) NEW_LINE adj2 [ 4 ] . append ( 5 ) NEW_LINE adj2 [ 5 ] . append ( 0 ) NEW_LINE adj2 [ 6 ] . append ( 4 ) NEW_LINE printCircuit ( adj2 ) NEW_LINE print ( ) NEW_LINE DEDENT