Length of the longest path ending at vertex V in a Graph | Python3 program for the above approach ; Function to perform DFS Traversal from source node to the deepest node and update maximum distance to the deepest node ; Mark source as visited ; Update the maximum distance ; Traverse the adjacency list of the current source node ; Recursively call for the child node ; Backtracking step ; Function to calculate maximum length of the path ending at vertex V from any source node ; Stores the maximum length of the path ending at vertex V ; Stores the size of the matrix ; Stores the adjacency list of the given graph ; Traverse the matrix to create adjacency list ; Perform DFS Traversal to update the maximum distance ; Driver Code
visited = [ False for i in range ( 4 ) ] NEW_LINE def dfs ( src , Adj , level , distance ) : NEW_LINE INDENT global visited NEW_LINE visited [ src ] = True NEW_LINE distance = max ( distance , level ) NEW_LINE for child in Adj [ src ] : NEW_LINE INDENT if ( child != src and visited [ child ] == False ) : NEW_LINE INDENT dfs ( child , Adj , level + 1 , distance ) NEW_LINE DEDENT DEDENT visited [ src ] = False NEW_LINE DEDENT def maximumLength ( mat , V ) : NEW_LINE INDENT distance = 0 NEW_LINE N = len ( mat ) NEW_LINE Adj = [ [ ] for i in range ( N ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT if ( mat [ i ] [ j ] == 1 ) : NEW_LINE INDENT Adj [ i ] . append ( j ) NEW_LINE DEDENT DEDENT DEDENT dfs ( V , Adj , 0 , distance ) NEW_LINE return distance + 2 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT mat = [ [ 0 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 1 ] , [ 0 , 1 , 0 , 0 ] , [ 0 , 1 , 0 , 0 ] ] NEW_LINE V = 2 NEW_LINE print ( maximumLength ( mat , V ) ) NEW_LINE DEDENT