Length of the longest path ending at vertex V in a Graph | C # 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
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static int distance ; static void dfs ( int src , List < List < int > > Adj , List < bool > visited , int level ) { visited [ src ] = true ; distance = Math . Max ( distance , level ) ; foreach ( int child in Adj [ src ] ) { if ( ( child != src ) && ( visited [ child ] == false ) ) { dfs ( child , Adj , visited , level + 1 ) ; } } visited [ src ] = false ; } static int maximumLength ( int [ , ] mat , int v ) { distance = 0 ; int N = mat . GetLength ( 0 ) ; List < bool > visited = new List < bool > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { visited . Add ( false ) ; } List < List < int > > Adj = new List < List < int > > ( N ) ; for ( int i = 0 ; i < N ; i ++ ) { Adj . Add ( new List < int > ( ) ) ; } for ( int i = 0 ; i < mat . GetLength ( 0 ) ; i ++ ) { for ( int j = 0 ; j < mat . GetLength ( 0 ) ; j ++ ) { if ( mat [ i , j ] == 1 ) { Adj [ i ] . Add ( j ) ; } } } dfs ( v , Adj , visited , 0 ) ; return distance ; } static void Main ( ) { int [ , ] mat = { { 0 , 1 , 0 , 0 } , { 1 , 0 , 1 , 1 } , { 0 , 1 , 0 , 0 } , { 0 , 1 , 0 , 0 } } ; int v = 2 ; Console . Write ( maximumLength ( mat , v ) ) ; } }