Detectando ciclos em um gráfico usando DFS: 2 abordagens diferentes e qual a diferença

Observe que um gráfico é representado como uma lista de adjacência.

Já ouvi duas abordagens para encontrar um ciclo em um gráfico:

Mantenha uma matriz de valores booleanos para acompanhar se você visitou um nó antes. Se você ficar sem novos nós para acessar (sem atingir um nó que você já esteve), basta voltar atrás e tentar uma ramificação diferente.

A do CLRS ou Skiena de Cormen: para uma pesquisa profunda em gráficos não direcionados, existem dois tipos de arestas, árvore e verso. O gráfico possui um ciclo se, e somente se, houver uma borda traseira.

Alguém pode explicar quais são as arestas de um gráfico e qual a diferença entre os dois métodos acima.

Obrigado.

Atualizar: Aqui está o código para detectar ciclos nos dois casos. Graph é uma classe simples que representa todos os nós do gráfico como números exclusivos para simplificar, cada nó tem seus nós vizinhos adjacentes (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;
  }

}

Código Java para detectar ciclos em um gráfico não direcionado:

    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;
            }
        }

    }  
}

Código Java para detectar ciclos em um gráfico direcionado:

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;
    }
}