当前位置：首页 > news >正文

【JavaScript 算法】图的遍历：理解图的结构

news 2025/6/27 1:53:31

在这里插入图片描述

🔥 个人主页：空白诗

在这里插入图片描述

文章目录

- 一、深度优先搜索（DFS）
- - 深度优先搜索的步骤
  - 深度优先搜索的JavaScript实现
- 二、广度优先搜索（BFS）
- - 广度优先搜索的步骤
- 三、应用场景
- 四、总结

在这里插入图片描述

图的遍历是图论中的基本操作之一，通过遍历图中的所有节点和边，可以理解图的结构并解决实际问题。常见的图遍历方法有深度优先搜索（DFS）和广度优先搜索（BFS）。本文将详细介绍这两种遍历方法的原理、实现及其应用。

一、深度优先搜索（DFS）

深度优先搜索是一种从起始节点出发，沿着图的分支尽可能深入，然后回溯并继续探索其他分支的遍历方法。

深度优先搜索的步骤

从起始节点开始，将其标记为已访问。
对于当前节点的每个相邻节点：
- 如果相邻节点未被访问，递归地执行深度优先搜索。
回溯到上一个节点，继续探索其他未被访问的相邻节点。

深度优先搜索的JavaScript实现

/*** 深度优先搜索算法* @param {Object} graph - 图的邻接表表示* @param {string} start - 起始节点* @param {Set} visited - 已访问节点集合*/
function depthFirstSearch(graph, start, visited = new Set()) {console.log(start); // 访问节点visited.add(start); // 将节点标记为已访问for (const neighbor of graph[start]) {if (!visited.has(neighbor)) {depthFirstSearch(graph, neighbor, visited); // 递归访问相邻节点}}
}// 示例
const graph = {A: ['B', 'C'],B: ['D', 'E'],C: ['F'],D: [],E: ['F'],F: []
};depthFirstSearch(graph, 'A'); // 输出: A B D E F C

二、广度优先搜索（BFS）

广度优先搜索是一种从起始节点开始，逐层向外扩展，直到遍历完所有节点的遍历方法。

广度优先搜索的步骤

从起始节点开始，将其标记为已访问，并加入队列。
当队列不为空时，取出队列的头节点，访问该节点的所有相邻节点。
对于每个相邻节点，如果未被访问过，将其标记为已访问并加入队列。
重复步骤2和3，直到队列为空。

### 广度优先搜索的JavaScript实现

/*** 广度优先搜索算法* @param {Object} graph - 图的邻接表表示* @param {string} start - 起始节点*/
function breadthFirstSearch(graph, start) {const queue = [start]; // 初始化队列，将起始节点加入队列const visited = new Set(); // 用于记录已访问的节点visited.add(start); // 将起始节点标记为已访问while (queue.length > 0) {const node = queue.shift(); // 取出队列的头节点console.log(node); // 访问节点// 访问当前节点的所有相邻节点for (const neighbor of graph[node]) {// 如果相邻节点未被访问过，将其标记为已访问并加入队列if (!visited.has(neighbor)) {visited.add(neighbor);queue.push(neighbor);}}}
}// 示例
breadthFirstSearch(graph, 'A'); // 输出: A B C D E F