知识卡片
图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