rinetd Shell脚本 方法 微信直播 volatile namespace wavedorm xcode express javafx websocket neo4j uiview cassandra x86 建站一条龙 react脚手架 河南普通话考试报名官网 cmd查看mysql版本 android调试工具 docker查看所有容器 python for循环 mysql函数 java的string java覆盖 java连数据库 java语言简介 java泛型方法 java中random java删除 linux命令 linuxls命令 linux镜像安装 凯立德地图免费下载 java电子书下载 typemonkey xs颜色 键盘模拟器 qq免安装 网络工程师教程
当前位置: 首页 > 学习教程  > 编程语言

es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法

2020/12/5 10:55:20 文章标签:

// 图的查找算法class Node {constructor(value) {this.value value;this.neighbors [];}/*** 深度优先查询 查询图* param target {String | Number}* returns {boolean} 结果*/searchByDepth(target ) {if (!this || target.length 0) return false;// 用于保存已经找到的…

// 图的查找算法

class Node {
    constructor(value) {
        this.value = value;
        this.neighbors = [];
    }

    /**
     * 深度优先查询 查询图
     * @param target {String | Number}
     * @returns {boolean} 结果
     */
    searchByDepth(target = '') {
        if (!this || target.length === 0) return false;
        // 用于保存已经找到的节点
        let exits = [];

        function _searchByDepth(node) {
            if (exits.includes(node)) return false;// 如果已经找过的节点,不用在继续查找
            else if (node.value === target) return true; // 找到了
            else {
                // 去找附近的节点,看看有没有
                exits.push(node);
                for (let i = 0, l = node.neighbors.length; i < l; i++) {
                    if (_searchByDepth(node.neighbors[i])) {
                        return true;
                    }
                }
            }
        }

        return !!_searchByDepth(this);
    }

    /**
     * 图的广度优先搜索
     * @param target {String | Number}
     * @returns {boolean} 结果
     */
    searchByWidth(target = '') {
        if (!this || target.length === 0) return false;
        let exits = []; // 用于保存已经存在的节点
        function _searchByWidth(nodesArr) {
            if (nodesArr.length === 0) return false;
            let nextNodesArr = [];
            for (let i = 0, l = nodesArr.length; i < l; i++) {
                if (nodesArr[i].value === target) return true;
                else {
                    exits.push(nodesArr[i]);
                    nextNodesArr = [...new Set([...nextNodesArr, ...nodesArr[i].neighbors])];
                    for (let j = 0, jl = nextNodesArr.length; j < jl; j++) {
                        if (exits.includes(nextNodesArr[i])) {
                            nextNodesArr.splice(i, 1);
                            j--;
                        }
                    }
                }
            }
            return _searchByWidth(nextNodesArr);
        }

        return _searchByWidth([this]);
    }

    // 普利姆算法
    /**
     * 普利姆算法 最小 生成树 加点法
     * @param nodeArr {Array} 所有的点集
     * @param distance {Array} 所有点的位置
     * @returns {Node}
     */
    prim(nodeArr, distance) {
        if (nodeArr.length !== distance.length || nodeArr.length === 0) return false;
        // 选一个开始的部落
        let nodeGroup = [nodeArr[0]];
        while (nodeGroup.length < nodeArr.length) {
            // 找到离部落最近的点
            let minDisNode = _minDisToGroup();
            // 将点放入到部落
            nodeGroup.push(minDisNode.node);
            // 将找到的点,与部落中的某个点进行连接
            minDisNode.node.neighbors.push(minDisNode.connectNode);
            minDisNode.connectNode.neighbors.push(minDisNode.node);
        }

        /**
         * 找到距离最近的点
         * @returns {{node: null, connectNode: null, dis: number}}
         * @private
         */
        function _minDisToGroup() {
            let result = {
                dis: Infinity, // 距离
                node: null,  // 找到的点
                connectNode: null, // 与部落的哪个点进行连接
            }
            for (let i = 0, l = nodeArr.length; i < l; i++) {
                let findNode = nodeArr[i];
                // 如果找到的当前点在部落中,跳出当前循环
                if (nodeGroup.includes(findNode)) continue;
                // 接下来的点不在部落中,需要进行该点到部落哪个点的距离最近
                let getNodeInfo = _compareNodeDis(findNode);
                if (getNodeInfo.dis < result.dis) {
                    result.dis = getNodeInfo.dis;
                    result.node = findNode;
                    result.connectNode = getNodeInfo.connectNode;
                }
            }
            return result;
        }

        /**
         * 找到离部落最小的距离,并且找到连接部落的哪个点
         * @param node
         * @returns {{connectNode: null, dis: number}}
         * @private
         */
        function _compareNodeDis(node) {
            let res = {
                dis: Infinity,
                connectNode: null,
            }
            // 找到该点距离部落哪个点最近
            for (let j = 0, jl = nodeGroup.length; j < jl; j++) {
                // 拿到部落的点
                let groupNode = nodeGroup[j];
                // 获取部落的点在部落的行
                let row = nodeArr.indexOf(groupNode);
                let col = nodeArr.indexOf(node);
                let dis = distance[row][col];
                if (dis < res.dis) {
                    res.dis = dis;
                    res.connectNode = groupNode;
                }
            }
            return res;
        }

        return this;
    }
}

测试:

let a = new Node('A');
let b = new Node('B');
let c = new Node('C');
let d = new Node('D');
let e = new Node('E');

a.neighbors.push(c, b);
b.neighbors.push(a, e);
c.neighbors.push(a, e, d);
d.neighbors.push(c, e);
e.neighbors.push(b, c, d);

console.log(b.searchByWidth('A')); // true
console.log(b.searchByWidth('F')); // false

console.log(b.searchByDepth('A')); // true
console.log(b.searchByDepth('F')); // false

// 图的最小生成树之prim算法
let a = new Node('A');
let b = new Node('B');
let c = new Node('C');
let d = new Node('D');
let e = new Node('E');
let nodeArr = [a, b, c, d, e];
let distance = [
    [0, 4, 6, Infinity, Infinity],
    [4, 0, Infinity, Infinity, 10],
    [6, Infinity, 0, 3, 7],
    [Infinity, Infinity, 3, 0, 2],
    [Infinity, 10, 7, 2, 0],
]

在这里插入图片描述

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_450344.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?