es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3836字,纯文字阅读大概需要6分钟。
内容图文
![es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法](/upload/InfoBanner/zyjiaocheng/619/d67fff6807ca402b808ece7588f68c75.jpg)
// 图的查找算法
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],
]
内容总结
以上是互联网集市为您收集整理的es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法全部内容,希望文章能够帮你解决es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。