graph

简介

graph 是 Yuka js 库中使用 Dijkstra 算法实现的图数据结构。该数据结构支持添加节点、添加边、获取最短路径等操作，可用于解决一些最短路径问题。

安装

在引入 Yuka js 库后，可以直接使用 graph 数据结构。只需将 graph.js 文件复制到项目中，即可使用该数据结构。

使用

创建图实例

在使用 graph 数据结构前，需先创建一个图实例。创建图实例时可以传入一个可选参数 directed，表示是否为有向图，默认为无向图。

import Graph from './graph.js';

const graph = new Graph(); // 创建无向图实例
const directedGraph = new Graph({ directed: true }); // 创建有向图实例

添加节点

使用 addNode 方法添加节点，节点的标识符可以是任何类型的数据，不重复。

graph.addNode('A');
graph.addNode('B');
graph.addNode('C');

添加边

使用 addEdge 方法添加边，边的两个连接节点的标识符需要已经存在于图中，且边不能重复。

graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('A', 'C');

获取最短路径

使用 shortestPath 方法获取从起点到终点的最短路径。该方法接受两个参数，起点和终点节点的标识符。

const path = graph.shortestPath('A', 'C');
console.log(path); // ['A', 'C']

API

属性

• nodes: 图中所有节点的集合。

方法

• addNode(id): 添加一个节点。
  • id: 节点的标识符。
• addEdge(from, to, weight): 添加一条边。
  • from: 起点节点的标识符。
  • to: 终点节点的标识符。
  • weight(可选): 边的权重，默认为1。
• shortestPath(start, end): 获取从起点到终点的最短路径。
  • start: 起点节点的标识符。
  • end: 终点节点的标识符。

示例

const graph = new Graph();

graph.addNode('A');
graph.addNode('B');
graph.addNode('C');
graph.addNode('D');
graph.addNode('E');
graph.addNode('F');

graph.addEdge('A', 'B', 4);
graph.addEdge('A', 'C', 2);
graph.addEdge('B', 'E', 3);
graph.addEdge('C', 'D', 2);
graph.addEdge('C', 'F', 4);
graph.addEdge('D', 'E', 3);
graph.addEdge('D', 'F', 1);
graph.addEdge('E', 'F', 1);

const path1 = graph.shortestPath('A', 'F');
console.log(path1); // ['A', 'C', 'D', 'F']

const directedGraph = new Graph({ directed: true });

directedGraph.addNode('A');
directedGraph.addNode('B');
directedGraph.addNode('C');
directedGraph.addNode('D');
directedGraph.addNode('E');

directedGraph.addEdge('A', 'B', 1);
directedGraph.addEdge('A', 'C', 3);
directedGraph.addEdge('B', 'D', 2);
directedGraph.addEdge('C', 'D', 2);
directedGraph.addEdge('D', 'E', 1);

const path2 = directedGraph.shortestPath('A', 'E');
console.log(path2); // ['A', 'B', 'D', 'E']

参考资料

• Dijkstra's algorithm - Wikipedia