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

// 图的查找算法

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],
]