图由顶点和边组成，可用邻接表或矩阵表示；JavaScript中常用邻接表实现无向图。1. 广度优先搜索（BFS）使用队列逐层遍历，适合查找未加权图的最短路径。2. 深度优先搜索（DFS）通过递归或栈深入遍历，适用于连通分量与拓扑排序。3. Dijkstra算法利用优先队列计算带权图的单源最短路径，维护距离表并持续更新邻居节点的最短距离。
图是一种用来表示对象之间多对多关系的非线性数据结构，由顶点（节点）和边（连接）组成。在JavaScript中实现图及其常见算法，有助于解决路径查找、依赖分析等问题。下面介绍图的基本实现以及常用的图算法：广度优先搜索（BFS）、深度优先搜索（DFS）和最短路径（Dijkstra算法）。
图的表示与基本结构
图可以用邻接表或邻接矩阵表示。邻接表更节省空间，适合稀疏图；邻接矩阵适合稠密图。这里使用邻接表实现无向图。
代码实现：
class Graph {
constructor() {
this.vertices = new Map(); // 存储顶点及其邻接列表
}
// 添加顶点
addVertex(v) {
if (!this.vertices.has(v)) {
this.vertices.set(v, []);
}
}
// 添加边（无向图）
addEdge(v1, v2) {
this.addVertex(v1);
this.addVertex(v2);
this.vertices.get(v1).push(v2);
this.vertices.get(v2).push(v1);
}
// 获取邻接列表
getAdjacencyList() {
return this.vertices;
}
}
广度优先搜索（BFS）
BFS从起始顶点出发，逐层遍历相邻节点，常用于找最短路径（未加权图）。
立即学习“Java免费学习笔记（深入）”；
实现说明：
- 使用队列存储待访问节点
- 用Set记录已访问节点，避免重复处理
- 返回遍历顺序或从起点到目标的路径
bfs(start, callback) {
const visited = new Set();
const queue = [start];
const result = [];
visited.add(start);
while (queue.length > 0) {
const vertex = queue.shift();
result.push(vertex);
const neighbors = this.vertices.get(vertex);
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
if (callback) callback(result);
return result;
}
深度优先搜索（DFS）
DFS沿一个方向深入到底，再回溯，适合拓扑排序或连通分量分析。
实现方式： 使用递归或栈。以下是递归版本。
dfs(start, callback) {
const visited = new Set();
const result = [];
const traverse = (vertex) => {
if (!vertex) return;
visited.add(vertex);
result.push(vertex);
const neighbors = this.vertices.get(vertex);
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
traverse(neighbor);
}
}
};
traverse(start);
if (callback) callback(result);
return result;
}
Dijkstra最短路径算法
适用于带权图，找出从起点到其他所有顶点的最短路径。
实现要点：
- 使用优先队列（最小堆），按距离排序
- 维护每个顶点的最短距离和前驱节点
- 不断更新邻居的距离值
dijkstra(start) {
const distances = new Map();
const previous = new Map();
const pq = new MinPriorityQueue(); // 可使用简单数组模拟或自定义类
// 初始化
for (const vertex of this.vertices.keys()) {
distances.set(vertex, Infinity);
previous.set(vertex, null);
}
distances.set(start, 0);
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
const { element: current } = pq.dequeue();
const neighbors = this.vertices.get(current);
for (const neighbor of neighbors) {
const edgeWeight = this.getWeight(current, neighbor); // 假设有权重存储
const newDist = distances.get(current) + edgeWeight;
if (newDist < distances.get(neighbor)) {
distances.set(neighbor, newDist);
previous.set(neighbor, current);
pq.enqueue(neighbor, newDist);
}
}
}
return { distances, previous };
}
注：MinPriorityQueue需额外实现，可用数组排序模拟，或引入外部库简化。
基本上就这些。图的实现灵活，结合实际需求调整边的存储方式（如加入权重）即可扩展功能。算法选择取决于具体问题：BFS求无权最短路径，DFS用于探索结构，Dijkstra处理加权最短路径。不复杂但容易忽略细节，比如访问标记和初始化。
