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