算法模板

  1. // 计算从起点 start 到终点 target 的最近距离
  2. function BFS(start, target) {
  3.     let q: Queue = []; // 核心数据结构
  4.     let visited = new Set(); // 避免走回头路
  6.     q.add(start); // 将起点加入队列
  7.     visited.add(start);
  8.     let  step = 0; // 记录扩散的步数
  10.     while (q ) {
  11.         int sz = q.length;
  12.         /* 将当前队列中的所有节点向四周扩散 */
  13.         for (let i = 0; i < sz; i++) {
  14.             let cur = q.pop();
  15.             /* 划重点：这里判断是否到达终点 */
  16.             if (cur is target)
  17.                 return step;
  18.             /* 将 cur 的相邻节点加入队列 */
  19.             for ( let x of cur.adj())
  20.                 if (x not in visited) {
  21.                     q.offer(x);
  22.                     visited.add(x);
  23.                 }
  24.         }
  25.         /* 划重点：更新步数在这里 */
  26.         step++;
  27.     }
  28. }

练习