How to use the Cycle Check Algorithm in Graphs?

There are several algorithms that can be used to identify cycles in graphs. The simplest is the search in produndity (DFS). Simply implement an in-depth search that returns true if it finds an already visited node.

One limitation of this algorithm is performance. Because DFS needs a root node, it is necessary to run DFS for each node in the graph.

Here is an implementation I wrote in Python:

from collections import defaultdict

class Grafo():
    def __init__(self):
        self._data = defaultdict(list)

    def conectar(self, nodo_origem, nodo_destino):
        self._data[nodo_origem].append(nodo_destino)

    def vizinhos(self, nodo):
        return self._data[nodo]

    def verificar_ciclos(self, nodo_inicial):
        nodos_visitados = set()
        nodos_restantes = [nodo_inicial]

        while nodos_restantes:
            nodo_atual = nodos_restantes.pop()
            nodos_visitados.add(nodo_atual)

            for vizinho in self.vizinhos(nodo_atual):
                if vizinho in nodos_visitados:
                    return True

                nodos_restantes.append(vizinho)

        return False

This class correctly detects the graph cycle displayed in the question:

grafo = Grafo()

grafo.conectar('A', 'R1')
grafo.conectar('R2', 'B')
grafo.conectar('B', 'R2')
grafo.conectar('R1', 'A')

if grafo.verificar_ciclos('A'):
    print('Encontrou um ciclo')
else:
    print('Não encontrou ciclo')

There are other more sophisticated algorithms, but DFS solves the problem and is a good start for anyone who is studying graphs.