How to use the Graph Cycle Verification Algorithm?

Question

Hello, I would like to know how to use the Graph Cycle Check Algorithm to find a cyclic condition, if you can put me the use of the algorithm in this graph below:

Answer 1

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

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

Here’s 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', 'R2')
grafo.conectar('R2', 'B')
grafo.conectar('B', 'R1')
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 those studying graphs.

Answer 2

   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
   
   grafo = Grafo()
    
nodos = ['2','3','5','7','8','9','10','11']
   
   grafo.conectar('7','11')
   grafo.conectar('7','8')
   grafo.conectar('5','11')
   grafo.conectar('3','8')
   grafo.conectar('3','10')
   grafo.conectar('11','2')
   grafo.conectar('11','9')
   grafo.conectar('11','10')
   grafo.conectar('8','9')
   
   for i in range(len(nodos)): 
       if grafo.verificar_ciclos(nodos[i]):
           print('Existe Cilo no Vertice: ',nodos[i])
       else:
           print('Sem Ciclos para: ',nodos[i])

I did this test using his answer to a graph without Cycles, and he returned that there was a Cycle, the 7, but it is not to exist: I made a mistake?

Sem Ciclos para:  2
Sem Ciclos para:  3
Sem Ciclos para:  5
Existe Cilo no Vertice:  7
Sem Ciclos para:  8
Sem Ciclos para:  9
Sem Ciclos para:  10
Sem Ciclos para:  11