Обратите внимание, что граф представлен в виде списка смежности.

Я слышал о 2 подходах, чтобы найти цикл на графике:

Сохраняйте массив логических значений, чтобы отслеживать, посещали ли вы ранее узел. Если у вас заканчиваются новые узлы для перехода (без попадания на узел, которым вы уже были), просто вернитесь назад и попробуйте другую ветвь.

Один из CLRS Cormen или Skiena: для поиска в глубину в неориентированных графах, есть два типа ребер, дерево и обратно. Граф имеет цикл тогда и только тогда, когда существует задний край.

Может кто-нибудь объяснить, что является задними краями графа и в чем разница между двумя вышеуказанными методами.

Благодарю.

Обновить: Вот код для обнаружения циклов в обоих случаях. Graph - это простой класс, который для простоты представляет все узлы графа как уникальные числа, каждый узел имеет смежные соседние узлы (g.getAdjacentNodes (int)):

public class Graph {

  private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};

  public int[] getAdjacentNodes(int v) {
    return nodes[v];
  }

  // number of vertices in a graph
  public int vSize() {
    return nodes.length;
  }

}

Java-код для обнаружения циклов в неориентированном графе:

    public class DFSCycle {

    private boolean marked[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    // s - starting node
    public DFSCycle(Graph g, int s) {
        this.g = g;
        this.s = s;
        marked = new boolean[g.vSize()];
        findCycle(g,s,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v, int u) {

        marked[v] = true;

        for (int w : g.getAdjacentNodes(v)) {
            if(!marked[w]) {
                marked[w] = true;
                findCycle(g,w,v);
            } else if (v != u) {
                hasCycle = true;
                return;
            }
        }

    }  
}

Java-код для обнаружения циклов в ориентированном графе:

public class DFSDirectedCycle {

    private boolean marked[];
    private boolean onStack[];
    private int s;
    private Graph g;
    private boolean hasCycle;

    public DFSDirectedCycle(Graph g, int s) {
        this.s = s
        this.g = g;
        marked = new boolean[g.vSize()];
        onStack = new boolean[g.vSize()];
        findCycle(g,s);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public void findCycle(Graph g, int v) {

        marked[v] = true;
        onStack[v] = true;

        for (int w : g.adjacentNodes(v)) {
            if(!marked[w]) {
                findCycle(g,w);
            } else if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }

        onStack[v] = false;
    }
}