JavaScript：检测层次图中的循环

Question

请注意，我已经完成了在我们的例子中，我们处理的不是链表，而是层次图，其中每个节点可能有多个子节点链接到它。例如，

const graph = {
   a: {value: Va, children: {b, d}},
   b: {value: Vb, children: {c}},
   c: {value: Vc, children: {a, d, e}}
}

在此图中，我们应该检测循环 a -> b -> c -> a。

Answer 1

您共享的图形对象中存在一些语法错误，但假设子对象是由字符串标识的，您通常会使用深度优先遍历来确定您是否碰到了作为反向引用的边已经在当前路径上的节点。

如果发生这种情况，您就有了一个循环，并且循环可以很容易地从当前路径和反向引用节点导出。

为了避免重复遍历，您还需要跟踪已访问过的节点（无论是否在当前路径上）。不需要从已经访问过的节点继续搜索。

要将节点标记为已访问，您可以使用集合。

function findCycle(graph) {
    let visited = new Set;
    let result;
    
    // dfs set the result to a cycle when the given node was already on the current path.
    //    If not on the path, and also not visited, it is marked as such. It then 
    //    iterates the node's children and calls the function recursively.
    //    If any of those calls returns true, exit with true also
    function dfs(node, path) {
        if (path.has(node)) {
            result = [...path, node]; // convert to array (a Set maintains insertion order)
            result.splice(0, result.indexOf(node)); // remove part that precedes the cycle
            return true;
        }
        if (visited.has(node)) return;
        path.add(node);
        visited.add(node);
        if ((graph[node]?.children || []).some(child => dfs(child, path))) return path;
        // Backtrack
        path.delete(node);
        // No cycle found here: return undefined
    }
    
    // Perform a DFS traversal for each node (except nodes that get 
    //   visited in the process)
    for (let node in graph) {
        if (!visited.has(node) && dfs(node, new Set)) return result;
    }
}

// Your example graph (with corrections):
const graph = {
   a: {value: 1, children: ["b", "d"]},
   b: {value: 2, children: ["c"]},
   c: {value: 3, children: ["a", "d", "e"]}
};

// Find the cycle
console.log(findCycle(graph)); // ["a","b","c","a"]

// Break the cycle, and run again
graph.c.children.shift(); // drop the edge c->a
console.log(findCycle(graph)); // undefined (i.e. no cycle)

Answer 2

如果您只需要确定一个图是否有环，而不需要报告环是什么，您可以通过简单的递归对图的特定节点执行此操作并将其包装在测试所有节点的调用。

这是一种实现方式：

const hasCycle = (graph, name, path = []) =>
  path .includes (name)
    ? true
   : (graph?.[name]?.children ?? []) .some (c => hasCycle (graph, c, [...path, name]))

const anyCycles = (graph) =>
  Object .keys (graph) .some (k => hasCycle (graph, k))

const graph1 = {a: {value: 1, children: ['b', 'd']}, b: {value: 2, children: ['c']}, c: {value: 3, children: ['a', 'd', 'e']}}
const graph2 = {a: {value: 1, children: ['b', 'd']}, b: {value: 2, children: ['c']}, c: {value: 3, children: ['d', 'e']}}

console .log (anyCycles (graph1))
console .log (anyCycles (graph2))

JavaScript：检测层次图中的循环

JavaScript: Detect a Loop in a Hierarchical Graph

javascript

algorithm

directed-graph

hierarchy

network-analysis