Empresas
Empleos
  • Sobre nosotros
  • Soluciones
    • Publicación de vacantes
      Publica tu vacante y recibe candidatos calificados en 48h.
    • Evaluación de candidatos
      500+ pruebas técnicas y psicológicas, más anti-fraude.
    • Headhunting
      Búsqueda ejecutiva a la medida de principio a fin.
    • Nómina + EOR
      Dispersión de nómina y EOR en más de 15 países de LATAM.
  • Precios
  • Empleos

0

242
Vistas
Detect loops (including their nodes) in undirected graph

I'm looking for a way to detect loops (including the nodes that form them) in an undirected graph.

This answer suggests that we can detect a loop during a depth-first-search "If an unexplored edge leads to a node visited before."

So with the code below I can successfully detect loops. My question is: once I have detected a loop, how can I know which are the nodes that form that loop?

class LoopFinder {
  nodes = "A B C D E F".split(" ");
  
  edges = [
    ["A", "B"],
    ["A", "D"],
    ["B", "C"],
    ["C", "D"],
    ["C", "E"],
    ["D", "E"],
    ["D", "F"],
    ["F", "E"]
  ];
  
  adjacencyList = new Map();
  
  addNode(point) {
    this.adjacencyList.set(point, []);
  }
  
  addEdge(nodeOne, nodeTwo) {
    this.adjacencyList.get(nodeOne).push(nodeTwo);
    this.adjacencyList.get(nodeTwo).push(nodeOne);
  }
  
  setupGraph() {
    this.nodes.forEach((point) => this.addNode(point));
    this.edges.forEach((route) => this.addEdge(route[0], route[1]));
  }
  
  visitedEdges = [];
  
  dfs(startNode, visitedNodes = new Set()) {
    console.log(startNode);
  
    visitedNodes.add(startNode);
  
      const adjacentNodes = this.adjacencyList.get(startNode);
  
      for (const adjacentNode of adjacentNodes) {
      
      const edgeId = [startNode, adjacentNode].sort().join("-");
  
      console.log("exporing edge", edgeId);
  
      const edgeIsUnexplored = !this.visitedEdges.includes(edgeId);
      const destinationHasBeenVisited = visitedNodes.has(adjacentNode);
  
      if (edgeIsUnexplored && destinationHasBeenVisited) {
        console.log('DETECTED LOOP - But which nodes form the loop?' );
      }
  
      this.visitedEdges.push(edgeId);
  
        if (!destinationHasBeenVisited) {
        this.dfs(adjacentNode, visitedNodes);
      }
    }
  }
  
  constructor() {
    this.setupGraph();
    this.dfs("A");
  }
}
  
new LoopFinder()

Also on Codepen.

The graph used in the example below looks like this:

  B---C---F
 /  /  \ /
A--D----E  

So the expected output would be 3 loops made of the following nodes:

  • ABCD
  • CDE
  • CEF
about 4 years ago · Juan Pablo Isaza
Responde la pregunta
Encuentra empleos remotos

¡Descubre la nueva forma de encontrar empleo!

Top de empleos
Top categorías de empleo
Empresas
Publicar vacante Precios Comercial
Legal
Términos y condiciones Política de privacidad
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomiéndame algunas ofertas
Necesito ayuda