Cycles of length n in an undirected and connected graph | Java program to calculate cycles of length n in a given graph ; Number of vertices ; mark the vertex vert as visited ; if the path of length ( n - 1 ) is found ; mark vert as un - visited to make it usable again ; Check if vertex vert end with vertex start ; For searching every possible path of length ( n - 1 ) ; DFS for searching path by decreasing length by 1 ; marking vert as unvisited to make it usable again ; Count cycles of length N in an undirected and connected graph . ; all vertex are marked un - visited initially . ; Searching for cycle by using v - n + 1 vertices ; ith vertex is marked as visited and will not be visited again ; driver code
public class Main { public static final int V = 5 ; static int count = 0 ; static void DFS ( int graph [ ] [ ] , boolean marked [ ] , int n , int vert , int start ) { marked [ vert ] = true ; if ( n == 0 ) { marked [ vert ] = false ; if ( graph [ vert ] [ start ] == 1 ) { count ++ ; return ; } else return ; } for ( int i = 0 ; i < V ; i ++ ) if ( ! marked [ i ] && graph [ vert ] [ i ] == 1 ) DFS ( graph , marked , n - 1 , i , start ) ; marked [ vert ] = false ; } static int countCycles ( int graph [ ] [ ] , int n ) { boolean marked [ ] = new boolean [ V ] ; for ( int i = 0 ; i < V - ( n - 1 ) ; i ++ ) { DFS ( graph , marked , n - 1 , i , i ) ; marked [ i ] = true ; } return count / 2 ; } public static void main ( String [ ] args ) { int graph [ ] [ ] = { { 0 , 1 , 0 , 1 , 0 } , { 1 , 0 , 1 , 0 , 1 } , { 0 , 1 , 0 , 1 , 0 } , { 1 , 0 , 1 , 0 , 1 } , { 0 , 1 , 0 , 1 , 0 } } ; int n = 4 ; System . out . println ( " Total ▁ cycles ▁ of ▁ length ▁ " + n + " ▁ are ▁ " + countCycles ( graph , n ) ) ; } }