Length of the longest path ending at vertex V in a Graph | Java 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
import java . util . ArrayList ; class GFG { static int distance ; private static void dfs ( int src , ArrayList < ArrayList < Integer > > Adj , ArrayList < Boolean > visited , int level ) { visited . set ( src , true ) ; distance = Math . max ( distance , level ) ; for ( int child : Adj . get ( src ) ) { if ( ( child != src ) && ( visited . get ( child ) == false ) ) { dfs ( child , Adj , visited , level + 1 ) ; } } visited . set ( src , false ) ; } private static int maximumLength ( int [ ] [ ] mat , int v ) { distance = 0 ; int N = mat [ 0 ] . length ; ArrayList < Boolean > visited = new ArrayList < Boolean > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { visited . add ( false ) ; } ArrayList < ArrayList < Integer > > Adj = new ArrayList < ArrayList < Integer > > ( N ) ; for ( int i = 0 ; i < N ; i ++ ) { Adj . add ( new ArrayList < Integer > ( ) ) ; } int i , j ; for ( i = 0 ; i < mat [ 0 ] . length ; i ++ ) { for ( j = 0 ; j < mat . length ; j ++ ) { if ( mat [ i ] [ j ] == 1 ) { Adj . get ( i ) . add ( j ) ; } } } dfs ( v , Adj , visited , 0 ) ; return distance ; } public static void main ( String [ ] args ) { int [ ] [ ] mat = { { 0 , 1 , 0 , 0 } , { 1 , 0 , 1 , 1 } , { 0 , 1 , 0 , 0 } , { 0 , 1 , 0 , 0 } } ; int v = 2 ; System . out . print ( maximumLength ( mat , v ) ) ; } }