Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Check if there are any nodes that point back to already visited nodes
var detectGraphCycles = function(graph, rootId) {
if (typeof graph[rootId] === 'undefined') { return false };
var currentNode = graph[rootId];
var visited = {};
var graphHasCycles = false;
while (currentNode && currentNode.next) {
if (typeof currentNode.id !== 'undefined') {
if (visited[currentNode.id] === true) {
currentNode = false;
graphHasCycles = true;
} else {
visited[currentNode.id] = true;
currentNode = graph[currentNode.next];
}
} else {
// so that we stop here
currentNode = false;
}
}
return graphHasCycles;
}
var testCases = [
{},
{
1: {
id: 1,
next: 3
},
2: {
id: 2,
next: 3
},
3: {
id: 3,
next: 1
},
},
{
1: {
id: 1,
next: 2
},
2: {
id: 2,
next: 3
},
3: {
id: 3,
next: null
},
},
{
1: {
id: 1,
next: 2
},
2: {
id: 2,
next: 3
},
3: {
id: 3,
next: 1
},
}
]
for (var test of testCases) {
let result = detectGraphCycles(test, 1);
console.log(test);
if (result) {
console.log('This graph has cycles');
} else {
console.log('no cycles');
}
console.log('');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.