JS实现判断DAG图是否有环

更新日期: 2019-08-30阅读: 2.5k标签: 路径

业务场景

调度系统的任务可视化界面需要完成用户可在界面上连线作为任意两个job间的依赖关系,也就是DAG图DAG也就是有向无环图,有向无环图指的是一个无回路的有向图。环是一条至少含有一条边且起点和终点相同的路径。


问题描述

在添加依赖关系时,在向后端发送请求前,前端应该先判断当前添加的连线是否与已存在的依赖关系成为闭环(循环依赖为无效的任务流),减少无效的请求。
job可以任意依赖,也就是每个job可以有多个字节点或者父节点。


环的理解

刚开始以为肉眼能看到的回路就是环,如下图中最终汇合到王小虎4这个节点,但是从有向图的依赖关系来说,实际是1依赖4,1依赖2,2依赖3,3依赖4,只是在等待节点4的执行,并没有陷入死循环的依赖。但是下面这个如果是一个无向图那么就是有环。

有向图和无向图:从图上来说可以简单理解有箭头指向的就是有环图,无箭头指向的为无环图



判断有向图是否有环

有两种算法:
1.深度优先遍历该图,如果在遍历的过程中,发现某个节点有一条边指向已经访问过的节点,则判断为有环。

 //图的深度遍历函数
    function DFS(i) {
        console.log('正在访问结点' + nodes[i]);
        //结点i变为访问过的状态
        visited[nodes[i]] = 1;
        for (let j = 0; j < nodes.length; j++) {
            //如果当前结点有指向的结点
            if (graph[nodes[i]][nodes[j]] != 0) {
                //并且已经被访问过
                if (visited[nodes[j]] == 1) {
                    isDAG = false; //有环
                    break;
                } else if (visited[nodes[j]] == -1) {
                    //当前结点后边的结点都被访问过,直接跳至下一个结点
                    continue;
                } else {
                    DFS(j); //否则递归访问
                }
            }
        }
        //遍历过所有相连的结点后,把本节点标记为-1
        visited[nodes[i]] = -1;
    }

    //创建图,以邻接矩阵表示
    function create(nodes, edges) {
        for (let i = 0; i < nodes.length; i++) {
            const pre = nodes[i];
            graph[pre] = {};
            for (let j = 0; j < nodes.length; j++) {
                const next = nodes[j];
                graph[pre][next] = 0;
            }
        }
        for (let k = 0; k < edges.length; k++) {
            const edge = edges[k];
            graph[edge.source][edge.target] = 1;
        }
        //初始化color数组为0,表示一开始所有顶点都未被访问过
        for (let i = 0; i < nodes.length; i++) {
            visited[nodes[i]] = 0;
        }
    }
    //邻接矩阵
    const graph = {};
    //结点个数和边的个数
    //标记矩阵,0为当前结点未访问,1为访问过,-1表示当前结点后边的结点都被访问过。
    const visited = {};
    //是否是DAG(有向无环图)
    let isDAG = true;

    // 获取所有的节点
    const edges = [
        {
            source: 'node1',
            target: 'node3'
        },
        {
            source: 'node3',
            target: 'node5'
        }
    ];
    const nodes = [];
    edges.forEach(e => {
        const { source, target } = e;
        if (!nodes.includes(source)) {
            nodes.push(source);
        }
        if (!nodes.includes(target)) {
            nodes.push(target);
        }
    });
    create(nodes, edges);
    //保证每个节点都遍历到,排除有的结点没有边的情况
    for (let i = 0; i < nodes.length; i++) {
        //该结点后边的结点都被访问过了,跳过它
        if (visited[nodes[i]] == -1) {
            continue;
        }
        DFS(i);
        if (!isDAG) {
            console.log('有环');
            break;
        }
    }
    if (isDAG) {
        console.log('无环');
    }

这种算法由于矩阵元素个数为n^2, 因此时间复杂度就是O(n^2)


2.拓扑排序

找到一个没有前驱(入度为0)的节点,入度就是指向该节点的依赖,从图中删除该节点和所有以它为起点的有向边。

在删除该节点的有向边过程中更新节点入度,找到下一个入度为0的节点,直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止,否则就是有环。


// 获取所有的节点
    const edges = [
        {
            source: 'node1',
            target: 'node3'
        },
        {
            source: 'node3',
            target: 'node4'
        },
        {
            source: 'node1',
            target: 'node4'
        }
    ];
    const nodes = [];
    const list = {}; // 邻接表
    const queue = []; // 入度为0的节点集合
    const indegree = {};
    edges.forEach(e => {
        const { source, target } = e;
        if (!nodes.includes(source)) {
            nodes.push(source);
        }
        if (!nodes.includes(target)) {
            nodes.push(target);
        }
        addEdge(source, target);
    });
    const V = nodes.length;

    nodes.forEach(node => {
        if (!indegree[node]) indegree[node] = 0;
        if (!list[node]) list[node] = [];
    });

    function addEdge(source, target) {
        if (!list[source]) list[source] = [];
        if (!indegree[target]) indegree[target] = 0;
        list[source].push(target);
        indegree[target] += 1;
    }
    function sort() {
        Object.keys(indegree).forEach(id => {
            if (indegree[id] === 0) {
                queue.push(id);
            }
        });
        let count = 0;
        while (queue.length) {
            ++count;
            const currentNode = queue.pop();
            const nodeTargets = list[currentNode];
            for (let i = 0; i < nodeTargets.length; i++) {
                const target = nodeTargets[i];
                indegree[target] -= 1;
                if (indegree[target] === 0) {
                    queue.push(target);
                }
            }
        }
        // false 没有输出全部顶点,有向图中有回路
        return !(count < V);
    }
    console.log(sort());

由于输出每个顶点的同时还要删除以它为起点的边,故上述拓扑排序的时间复杂度为O(V+E)。


扩展:判断无向图是否有环

1.遍历当前所有的依赖边,将所有相关节点的依赖节点加入到邻接表,这里用一个数组去存储
2.边有起点source和终点target,假设起点为a,终点为b,则沿着a节点去深度遍历当前图a节点的相邻依赖都没有找到终点为b的点,则这条依赖加入后也是无环图。
3.为了防止陷入死循环,在边单次循环中需要加如visited数组表示此节点被访问过。

const edges = [
    {
        source: 1,
        target: 3
    },
    {
        source: 3,
        target: 5
    },
    {
        source: 2,
        target: 3
    },
    {
        source: 4,
        target: 1
    },
    {
        source: 1,
        target: 6
    },
    {
        target: 5,
        source: 6
    }
];

function findRedundantConnection(edges) {
    // 使用邻接表存储图的信息
    const graph = new Map();

    // 遍历每一条边
    for (let i = 0; i < edges.length; i++) {
        const edge = edges[i];
        // Each element of edges is a pair [u, v] with u < v
        // const u = edge[0];
        // const v = edge[1];
        const u = edge.source;
        const v = edge.target;

        // 深度优先遍历该图,判断u到v之间是否已经存在了一条路径
        let hasPath = dfs(graph, u, v, []);

        if (hasPath == true) {
            return edge;
        } else {
            // 将该边加入到邻接表中
            if (!graph.has(u)) {
                graph.set(u, []);
            }
            const uArr = graph.get(u);
            uArr.push(v);
            graph.set(u, uArr);

            if (!graph.has(v)) {
                graph.set(v, []);
            }
            const vArr = graph.get(v);
            vArr.push(u);
            graph.set(v, vArr);
        }
    }

    return null;
}

// 深度优先遍历该图,判断start到end之间是否已经存在了一条路径
function dfs(graph, start, end, visited) {
    if (!graph.has(start) || !graph.has(end)) {
        return false;
    }

    if (start == end) {
        return true;
    }

    visited.push(start);

    // 遍历start的所有相邻节点
    const startArr = graph.get(start);
    for (let i = 0; i < startArr.length; i++) {
        const adj = startArr[i];
        if (!visited.includes(adj)) {
            if (dfs(graph, adj, end, visited) == true) {
                return true;
            }
        }
    }

    return false;
}
console.log(findRedundantConnection(edges));

原文:https://segmentfault.com/a/1190000020241908

链接: https://www.fly63.com/article/detial/5048

Node.js中的路径问题

在前端学习过程中,涉及到路径的问题非常多,相对路径,绝对路径等。有时候明明觉得没问题,但是还是会出错。或者说线下没问题,但是到了线上就出现问题,因此弄懂路径问题,非常关键

html中的路径:相对路径,绝对路径

html中的路径:指文件存放的位置,在网页中利用路径可以引用文件,完成:插入图像、视频等功能。表示在html中路径的使用方式有两种:相对路径,绝对路径。

webpack中路径的理解

webpack 前端打包工具, 开发人员要面对的路径主要是: 打包前的路径(开发环境路径)和打包后的路径(生产环境路径),在webpack.config.js中配置的output.path, output.publicPath, 以及各种插件, loader中的outputPath, publicPath

vue-cli3+工具中,配置路径别名(vue.config.js)

vue-cli 2.x 版本创建项目时,我们可以在 build 文件夹下找到 webpack.base.conf.js 文件,在里面修改 resolve.alias 即可。但是vue-cli 3.0 创建项目时,目录结构精简化,找不到 build 和 config 文件夹

HTML相对路径怎么写

所谓相对路径,就是相对于自己的目标文件位置。那么在HTML中如何写相对路径呢?相对路径的几种写法:1、如果是在同一目录下,有两个文件A.html和B.html:

HTML引入文件的绝对路径、相对路径、根目录

绝对路径指的是文件的真正路径,使用绝对路径链接外部资源,如:图片、超级链接、flash、音频、视频等等。使用绝对路径必须输入完整的描述路径,这种方法指向的链接目标地址清晰明确

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!