Hello 算法 1.2.0 typescript版

# Hello 算法 1.2.0 TypeScript 版 ## 第9章 图 图的广度优先遍历（BFS）是一种常用算法，用于从一个起点访问所有其他顶点。以下是关键点总结： ### 广度优先遍历的核心要点 1. **顺序不唯一**：相同距离的顶点可以按任意顺序被访问。 2. **时间复杂度**：O(|V| + |E|)，其中|V|是顶点数，|E|是边的数量。 3. **实现步骤**： - 使用队列（que）来管理待访问的顶点。 - 记录已访问过的顶点以避免重复访问。 4. **代码示例**： ```typescript // 队列初始化为空 let que = []; // 初始化结果数组 let res: (Vertex | null)[] = []; // 访问队列中的每个顶点 while (que.length > 0) { const node = que.shift(); if (node === undefined) continue; // 遍历当前节点的所有邻接顶点 for (let neighbor of node.adjacent) { if (!visited[neighbor]) { visited[neighbor] = true; res.push(neighbor); que.push(neighbor); } } } ``` ### 广度优先遍历的示例图解 图9‑10展示了从顶点1、3出发时，广度优先遍历的具体步骤。例如： - 顶点1和3的访问顺序可以交换； - 顶点2、4、6的访问顺序也可以任意调整。 ### 相关代码实现 本书配套代码托管在GitHub仓库中，相关文件如`graph.ts`提供了图的表示和广度优先遍历算法的具体实现： ```typescript class Vertex { id: number; } class Edge { to: Vertex; weight?: number; } class Graph { vertices: Vertex[]; edges: Edge[]; } // 初始化图的邻接表表示 graph = new Graph(); graph.vertices.push(new Vertex(1)); graph.vertices.push(new Vertex(2)); // 添加边（示例） graph.edges.push(new Edge(graph.vertices[0], graph.vertices[1])); ``` ### 广度优先遍历的优缺点 - **优点**：保证按“由近及远”的顺序访问顶点，适用于无权图中的最短路径问题。 - **缺点**：对于大规模图或稀疏图来说，广度优先遍历可能效率不高。 通过以上总结可以看出，广度优先遍历是一种基础且实用的算法，适合处理许多图相关的问题。