假设我给定pairs的array(其中pair[0]取决于pair[1])。我想检测在任何一对依赖关系之间是否存在循环。
循环:[[0,1], [1,2], [2, 1]]
说明:在1 -> 2和2 -> 1之间存在一个循环
Not a Cycle:[[0,1], [1,2], [0, 2]]
TLDR;
我遇到的问题是……一旦我"检测到"一个循环，我似乎不知道如何"返回"。它。调用堆栈继续执行"other";孩子们，但我想停止。你可以跳到底部(The Algorithm)
)方法:
- 使用
Map创建对的图形表示✅
/**
* @param { array } [ [intA, intB] ] - Nested array of integers pairs
* @return { Map } (representing a Graph)
*/
function createGraph(array) {
const nodes = new Map();
// Create Verticies
array.map(pair => {
const aClass = pair[0];
const bClass = pair[1];
nodes.set(aClass, []);
nodes.set(bClass, []);
})
// Create Edges
array.map(pair => {
const aClass = pair[0];
const bClass = pair[1];
nodes.get(aClass).push(bClass);
});
return nodes;
}
到目前为止，它正在按预期工作:
// Create Graph
const array = [[0,1], [1,2], [0, 2]];
const graph = createGraph(array);
console.log(graph);
// Map(3) { 0 => [ 1, 2 ], 1 => [ 2 ], 2 => [] }
- 对所有未访问的节点(在
GreySet中)执行DFS(直到我们检测到一个循环)。⚠️
我使用了3个颜色集合的方法。我真的很喜欢这个算法，真的很想实现它。从我的理解，内容如下:
WhiteSet包含所有未被触碰的节点。GreySet包含当前正在探索的节点。因此，在我们的DFS中，"父"&;BlackSet将保存已经被探索的节点(到没有循环的点)。
所以…如果我们探索BlackSet中的一个孩子，我们就没有理由进一步探索它(它已经被探索过了，无论如何它都没有任何循环)。然而，如果我们遇到一个子元素不在WhiteSet中，并且它存在于GreySet中，这意味着我们有一个循环。
这是我的代码，我在下面添加了console.logs。我遇到的问题是……一旦我"检测到"一个循环，我似乎不知道如何"返回"。它。如您所见，它将继续执行。
算法:
// Create Graph
const graph = createGraph(array);
console.log(graph); // Looks Good
// Detect Cycle
// Create 3 Sets
const whtSet = new Set(graph.keys()); // Put all the Integer "node values" the set.
const grySet = new Set();
const blkSet = new Set();
const unvisitedValues = whtSet.keys(); // Iterator
while (whtSet.size > 0) {
const doesItHaveCycle = hasCycle(unvisitedValues.next().value); // Expore any unexplored nodeVal
console.log('whtSet', whtSet);
console.log('grySet', grySet);
console.log('blkSet', blkSet);
console.log('does it have a cycle', doesItHaveCycle);
}
function hasCycle(nodeVal) {
// Blackset means it has been compltely explored :)
if (blkSet.has(nodeVal)) return false;
// This means we have found a cycle
if (!whtSet.has(nodeVal) && grySet.has(nodeVal)) return true;
// Remove it from the whiteSet, into the greySet.
whtSet.delete(nodeVal);
grySet.add(nodeVal);
// Recurse Children
graph.get(nodeVal).forEach((child) => {
let doesHaveCycle = hasCycle(child);
console.log(
'doesHaveCycle result: ',
doesHaveCycle,
'when exploring nodeVal',
nodeVal,
'and child',
child
);
if (doesHaveCycle === true) return true; // RETURN THIS PLS lol
});
// If above was true, I DO NOT want it to come here, but it still does.
console.log('if above was true... shouldnt come here');
// Now, that we have explored all of the children, remove it from Grey Set...
// Add it to the Black Set
grySet.delete(nodeVal);
blkSet.add(nodeVal);
return false; // IDK
}
console.log结果
doesHaveCycle result: true when exploring nodeVal 2 and child 1
if above was true... shouldnt come here
doesHaveCycle result: false when exploring nodeVal 1 and child 2
if above was true... shouldnt come here
doesHaveCycle result: false when exploring nodeVal 0 and child 1
if above was true... shouldnt come here
whtSet Set(0) {}
grySet Set(0) {}
blkSet Set(3) { 2, 1, 0 }
does it have a cycle false
我是100%开放修改代码，它现在是一个烂摊子。但是，我还是想用3 color Set"方式。
为了了解更多的背景，我试图尝试解决这个可爱的算法问题，叫做课程安排。
// Recurse Children
graph.get(nodeVal).forEach((child) => {
let doesHaveCycle = hasCycle(child);
console.log(
'doesHaveCycle result: ',
doesHaveCycle,
'when exploring nodeVal',
nodeVal,
'and child',
child
);
if (doesHaveCycle === true) return true; // RETURN THIS PLS lol
});
命令"RETURN THIS PLS";通常都有用，但这是个特例。foreach只调用每个元素的回调函数，而忽略回调函数的返回值。
您需要的函数称为some。它像foreach一样对每个元素调用给定的函数，一旦其中一个调用返回true，它就返回true。(它基本上告诉某个元素的回调是否为真。)否则返回false。
some的用法:
// Recurse Children
const cycle = graph.get(nodeVal).some((child) => {
let doesHaveCycle = hasCycle(child);
console.log(
'doesHaveCycle result: ',
doesHaveCycle,
'when exploring nodeVal',
nodeVal,
'and child',
child
);
return doesHaveCycle;
});
if (cycle) return true;
// now this obviously works
console.log('if above was true... shouldnt come here');
您可能还想在找到一个循环后跳出while循环:
let doesItHaveCycle = false;
while (whtSet.size > 0) {
doesItHaveCycle = hasCycle(unvisitedValues.next().value); // Expore any unexplored nodeVal
if (doesItHaveCycle) break;
}
因为，我们没有做一个完整的DFS，而是在我们看到周期时返回。这使得当前节点为灰色，并且它的一些子节点未被访问。如果我们想在检测到一个循环后继续，我们需要访问所有的子节点，将当前节点更改为黑色，然后然后