Finding Cycles Objective: With the given graph below use DFS to detect all possi

Question

Finding Cycles

Objective:

With the given graph below use DFS to detect all possible cycles. A cycle is a path (ordered set of vertices) that starts from an arbitrary vertex and ends at the same vertex. You may use either an ardency matrix or the linked form of a graph to achieve this.

Example Print Out:

The Cycles in this graph are

1 5 2 1

1 5 3 1

1 5 7 4 2 1

1 5 7 6 3 1

2 1 5 2

2 1 5 7 4 2

3 1 5 3

3 1 5 7 6 3

4 2 1 5 7 4

5 2 1 5

5 3 1 5

5 7 4 2 1 5

5 7 6 3 1 5

6 3 1 5 7 6

7 4 2 1 5 7

7 6 3 1 5 7

Explanation / Answer

package graph;

import java.util.ArrayList;
import java.util.List;

public class CycleInGraph {

   public static void main(String[] args) {
       // TODO Auto-generated method stub
       /*Scanner s = new Scanner(System.in);
       int m = s.nextInt();
       int n = s.nextInt();*/
       int[][] matrix= new int[][]{
           {0,0,0,0,1,0,0},
           {1,0,0,0,0,0,0},
           {1,0,0,0,0,0,0},
           {0,1,0,0,0,0,0},
           {0,1,1,0,0,0,1},
           {0,0,1,0,0,0,0},
           {0,0,0,1,0,1,0},
       };
      
       int vertices = 7;
      
       printLoop(matrix,vertices);
   }
  
   public static void printLoop(int[][] matrix, int vertices) {
       for (int i=0;i<vertices;i++){
           List<Integer> list = new ArrayList<Integer>();
           list.add(i);
           addChilds(matrix,i,list,vertices);
       }
   }
  
   public static void addChilds(int[][] matrix, int i, List<Integer> list, int vertices) {
       for (int j=0;j<vertices;j++) {
           if (matrix[i][j] == 1) {
               if (list.contains(j)) {
                   /*System.out.println(list.get(0));
                   System.out.println(j);*/
                   if (list.get(0) == j) {
                       //System.out.println(list);
                       for(int ele:list) {
                           System.out.print(ele+1+" ");
                       }
                       System.out.println(j+1);
                   }
                   //return;
               }
               else {
                   List<Integer> newlist = new ArrayList<>(list);
                   newlist.add(j);
                   addChilds(matrix, j, newlist, vertices);
               }
           }
       }
   }
  
  

}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.