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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void dfs ( int src , vector < int > Adj [ ] , vector < bool > & visited , int level , int & distance ) { visited [ src ] = true ; distance = max ( distance , level ) ; for ( auto & child : Adj [ src ] ) { if ( child != src and visited [ child ] == false ) { dfs ( child , Adj , visited , level + 1 , distance ) ; } } visited [ src ] = false ; } int maximumLength ( vector < vector < int > > & mat , int V ) { int distance = 0 ; int N = ( int ) mat . size ( ) ; vector < int > Adj [ N ] ; vector < bool > visited ( N , false ) ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { if ( mat [ i ] [ j ] == 1 ) { Adj [ i ] . push_back ( j ) ; } } } dfs ( V , Adj , visited , 0 , distance ) ; return distance ; } int main ( ) { vector < vector < int > > mat = { { 0 , 1 , 0 , 0 } , { 1 , 0 , 1 , 1 } , { 0 , 1 , 0 , 0 } , { 0 , 1 , 0 , 0 } } ; int V = 2 ; cout << maximumLength ( mat , V ) ; return 0 ; }