AlgorithmsInJava/DataStructures/Graphs/Cycles.java at master · csbase/AlgorithmsInJava

87 lines (74 loc) · 2.03 KB

package DataStructures.Graphs;

import java.util.ArrayList;
import java.util.Scanner;

class Cycle {

  private int nodes, edges;
  private int[][] adjacencyMatrix;
  private boolean[] visited;
  ArrayList<ArrayList<Integer>> cycles = new ArrayList<ArrayList<Integer>>();

  public Cycle() {
    Scanner in = new Scanner(System.in);
    System.out.print("Enter the no. of nodes: ");
    nodes = in.nextInt();
    System.out.print("Enter the no. of Edges: ");
    edges = in.nextInt();

    adjacencyMatrix = new int[nodes][nodes];
    visited = new boolean[nodes];

    for (int i = 0; i < nodes; i++) {
      visited[i] = false;
    }

    System.out.println("Enter the details of each edges <Start Node> <End Node>");

    for (int i = 0; i < edges; i++) {
      int start, end;
      start = in.nextInt();
      end = in.nextInt();
      adjacencyMatrix[start][end] = 1;
    }
    in.close();
  }

  public void start() {
    for (int i = 0; i < nodes; i++) {
      ArrayList<Integer> temp = new ArrayList<>();
      dfs(i, i, temp);
      for (int j = 0; j < nodes; j++) {
        adjacencyMatrix[i][j] = 0;
        adjacencyMatrix[j][i] = 0;
      }
    }
  }

  private void dfs(Integer start, Integer curr, ArrayList<Integer> temp) {
    temp.add(curr);
    visited[curr] = true;
    for (int i = 0; i < nodes; i++) {
      if (adjacencyMatrix[curr][i] == 1) {
        if (i == start) {
          cycles.add(new ArrayList<Integer>(temp));
        } else {
          if (!visited[i]) {
            dfs(start, i, temp);
          }
        }
      }
    }

    if (temp.size() > 0) {
      temp.remove(temp.size() - 1);
    }
    visited[curr] = false;
  }

  public void printAll() {
    for (int i = 0; i < cycles.size(); i++) {
      for (int j = 0; j < cycles.get(i).size(); j++) {
        System.out.print(cycles.get(i).get(j) + " -> ");
      }
      System.out.println(cycles.get(i).get(0));
      System.out.println();
    }
  }
}

public class Cycles {
  public static void main(String[] args) {
    Cycle c = new Cycle();
    c.start();
    c.printAll();
  }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Expand file tree

Search code, repositories, users, issues, pull requests...

Uh oh!

FilesExpand file tree

Cycles.java

Latest commit

History

Cycles.java

File metadata and controls

Expand file tree