Calculate number of nodes between two vertices in an acyclic Graph by DFS method | Java program for the above approach ; Function to return the count of nodes in the path from source to destination ; Mark the node visited ; If dest is reached ; Traverse all adjacent nodes ; If not already visited ; If there is path , then include the current node ; Return 0 if there is no path between src and dest through the current node ; Function to return the count of nodes between two given vertices of the acyclic Graph ; Initialize an adjacency list ; Populate the edges in the list ; Mark all the nodes as not visited ; Count nodes in the path from src to dest ; Return the nodes between src and dest ; Driver Code ; Given number of vertices and edges ; Given source and destination vertices ; Given edges
import java . util . Vector ; class GFG { static int dfs ( int src , int dest , int [ ] vis , Vector < Integer > [ ] adj ) { vis [ src ] = 1 ; if ( src == dest ) { return 1 ; } for ( int u : adj [ src ] ) { if ( vis [ u ] == 0 ) { int temp = dfs ( u , dest , vis , adj ) ; if ( temp != 0 ) { return temp + 1 ; } } } return 0 ; } static int countNodes ( int V , int E , int src , int dest , int edges [ ] [ ] ) { Vector < Integer > [ ] adj = new Vector [ V + 1 ] ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < E ; i ++ ) { adj [ edges [ i ] [ 0 ] ] . add ( edges [ i ] [ 1 ] ) ; adj [ edges [ i ] [ 1 ] ] . add ( edges [ i ] [ 0 ] ) ; } int vis [ ] = new int [ V + 1 ] ; int count = dfs ( src , dest , vis , adj ) ; return count - 2 ; } public static void main ( String [ ] args ) { int V = 8 , E = 7 ; int src = 5 , dest = 2 ; int edges [ ] [ ] = { { 1 , 4 } , { 4 , 5 } , { 4 , 2 } , { 2 , 6 } , { 6 , 3 } , { 2 , 7 } , { 3 , 8 } } ; System . out . print ( countNodes ( V , E , src , dest , edges ) ) ; } }