知识卡片

普通读书笔记卡 · 5654.d.1.a.1.c.1.d.3

图BFS在入队时标记访问

理解等级:中级

从起点入队,取出一个顶点后,把尚未发现的邻居加入队尾,并立即标记已发现。这样同一个顶点即使有多条入边,也不会在出队前重复加入队列。

队列保证按无权最少边数的层次推进,邻接访问顺序会影响同层次的实际排列。但不能任意打乱同层所有顶点还声称必为某次合法BFS,因为父队列的顺序也约束孩子入队。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      只入队未访问的顶点 if !isExist { queue = append(queue, adjVet ) visited[adjVet] = struct {}{} } } } // 返回顶点遍历序列 return

    参考来源

    - 位置:《Hello 算法--Go版本》第09章《图》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[6002,6111)) - 结论依据:实际graphBFS visited写入时机与队列代码,纠正同层任意排列的过强说明。 - 原始内容:只入队未访问的顶点 if !isExist { queue = append(queue, adjVet ) visited[adjVet] = struct {}{} } } } // 返回顶点遍历序列 return