Estoy buscando una forma de detectar bucles (incluidos los nodos que los forman) en un gráfico no dirigido.

Esta respuesta sugiere que podemos detectar un bucle durante una búsqueda en profundidad "si un borde inexplorado conduce a un nodo visitado antes".

Entonces, con el código a continuación, puedo detectar bucles con éxito. Mi pregunta es: una vez que he detectado un bucle, ¿cómo puedo saber cuáles son los nodos que forman ese bucle?

 class LoopFinder { nodes = "ABCDE 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()

También en Codepen .

El gráfico utilizado en el siguiente ejemplo se ve así:

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

Entonces, la salida esperada sería 3 bucles hechos de los siguientes nodos:

• A B C D
• CDE
• MCE