知识卡片

普通读书笔记卡 · 5654.d.1.f.3.k · 生成模型:未记录

广度优先在发现时防止重复入队

理解等级:中级

广度优先用FIFO队列保存已发现但尚未完成的顶点,先扩展当前顶点的所有白色邻居,再继续队列中的下一项。白色表示未发现,灰色表示已发现/待扩展,黑色表示邻居已处理完。

起点应在入队时即标记已发现;每个新邻居也在首次入队前后立即由白转灰,不能等处理结束变黑才防重,否则多条入边可能让它被重复入队。原段起点直接涂黑及“涂黑时才发现”的说法与三色职责不一致,按发现/完成分开理解。

02918从1开始的队列变化为[1]→[2,3]→[3,4]→[4]→空,顶点5从1不可达,仍未发现。遍历邻居的顺序可能影响同层排列及选中父亲,不影响无权最少边数。

199的02942–02944实际起点gray/hops0,其他white/-1;队列保存AdjList地址。每个白邻居先gray并设当前hops+1再入队,当前顶点扩展后出队变black,符合发现防重规则。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      广度优先搜索和深度优先搜索。 广度优先搜索 广度优先搜索(见图11-6)在进一步探索图中的顶点之前先访问当前顶点的所有邻接结点。这种查找方法在很多应用中都非常有用,包括找出最小生成树以及最短路径问题(见第16章,以及本章中的第一个例子)。 图 11-6 从顶点1开始进行广度优先搜索,顶点5对于顶点1

    • · 查看原书依据

      着色为灰色。每个顶点的颜色和跳数信息都由邻接表结构链表中的BfsVertex来维护。最后,加载hops中所有跳数不为-1的顶点。这些就是从起始结点可到达的顶点。 bfs的时间复杂度为O(V+E),这里V是图中顶点的个数,E是边的个数。这是因为初始化顶点的颜色属性以及确保起始结点存在都需要O(V)的运

    参考来源

    - 位置:《算法精解:C语言描述》第11章《搜索方法》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u187-ch11-012)。 - 结论依据:187广度优先全部过程与02918五阶段图实读,颜色按白/灰/黑实际职责修正正文矛盾,未把图中简化黑白显示当反例。 - 原始内容:广度优先搜索和深度优先搜索。 广度优先搜索 广度优先搜索(见图11-6)在进一步探索图中的顶点之前先访问当前顶点的所有邻接结点。这种查找方法在很多应用中都非常有用,包括找出最小生成树以及最短路径问题(见第16章,以及本章中的第一个例子)。 图 11-6 从顶点1开始进行广度优先搜索,顶点5对于顶点1 - 位置:《算法精解:C语言描述》第11章《关于图的应用举例:计算网络跳数》(spine1332;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1299.html;u199-ch11-012)。 - 结论依据:199的02942–02944实际起点gray/hops0,其他white/-1;队列保存AdjList地址。每个白邻居先gray并设当前hops+1再入队,当前顶点扩展后出队变black,符合发现防重规则。 - 原始内容:着色为灰色。每个顶点的颜色和跳数信息都由邻接表结构链表中的BfsVertex来维护。最后,加载hops中所有跳数不为-1的顶点。这些就是从起始结点可到达的顶点。 bfs的时间复杂度为O(V+E),这里V是图中顶点的个数,E是边的个数。这是因为初始化顶点的颜色属性以及确保起始结点存在都需要O(V)的运