js实现图的广度优先搜索算法的动画演示效果
时间: 2024-05-12 07:17:40 浏览: 112
当然可以!以下是js实现图的广度优先搜索算法的动画演示效果的代码:
```javascript
// 创建一个图的类
class Graph {
constructor() {
// 使用邻接列表存储图中的节点和边
this.adjacencyList = new Map();
}
// 添加顶点
addVertex(vertex) {
// 如果图中已经存在该顶点,则不添加
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
// 添加边
addEdge(vertex1, vertex2) {
// 如果两个顶点都在图中,则添加边
if (this.adjacencyList.has(vertex1) && this.adjacencyList.has(vertex2)) {
this.adjacencyList.get(vertex1).push(vertex2);
this.adjacencyList.get(vertex2).push(vertex1);
}
}
// 广度优先搜索算法
bfs(startingNode) {
// 使用队列存储待遍历的节点
let queue = [];
// 存储已经遍历过的节点
let visited = new Set();
// 先将起点入队
queue.push(startingNode);
// 标记起点已经遍历过
visited.add(startingNode);
while (queue.length) {
// 出队一个节点
let currentNode = queue.shift();
console.log(currentNode);
// 遍历当前节点的所有邻居节点
let neighbors = this.adjacencyList.get(currentNode);
for (let neighbor of neighbors) {
// 如果邻居节点没有遍历过,则入队并标记为已遍历
if (!visited.has(neighbor)) {
queue.push(neighbor);
visited.add(neighbor);
}
}
}
}
}
// 创建一个图的实例
let graph = new Graph();
// 添加顶点
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
// 添加边
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(2, 4);
// 广度优先搜索
graph.bfs(1);
```
动画演示效果可以上网查找各种可视化工具,比如d3.js等。
阅读全文