javascript - 我应该如何在有向图中找到循环并列出形成循环的节点？

Question

我在 javascript 中有对象数组 我正在尝试绘制有向图 我应该如何确定它是否包含循环 如果包含形成循环的元素是什么图不是强连接的，节点可以像“f”一样被隔离

 array = {};
//operations   parents
    array[a] = [b,c]
    array[b] = [d,c]
    array[e] = [a,b]
    array[d] = [e]
    array[f] = []

我想找到操作之间的循环，就像这里我们有来自 e-d-b-e 的循环？我应该如何找到周期？我正在使用 javascript。

Answer 1

这是一个 BFS 解决方案，它将找到一个循环(如果有的话)，这将是最短的循环之一。

function getCycle(graph) {
    // Copy the graph, converting all node references to String
    graph = Object.assign(...Object.keys(graph).map( node =>
                ({ [node]: graph[node].map(String) }) 
    ));

    let queue = Object.keys(graph).map( node => [node] );
    while (queue.length) {
        const batch = [];
        for (const path of queue) {
            const parents = graph[path[0]] || [];
            for (const node of parents) {
                if (node === path[path.length-1]) return [node, ...path];
                batch.push([node, ...path]);
            }
        }
        queue = batch;
    }
}

// First example
var graph = {
    a: ['b', 'c'],
    b: ['d', 'c'],
    e: ['a', 'b'],
    d: ['e']
};
var result = getCycle(graph);
console.log(result);

// Second example (numeric node references)
var graph = {
    0: [4],
    1: [4,0],
    2: [0,1],
    3: [1],
    4: [3]
};
var result = getCycle(graph);
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

注意:如果您使用数字引用定义图表，则需要进行类型转换，因为对象属性始终为字符串类型。我们可以使用 == 而不是 ===，但是输出仍然是字符串和数字的混合；我认为首先将每个节点引用转换为字符串更好。