知识卡片
图遍历只覆盖起点可达部分
带visited的BFS或DFS从一个起点开始,只能访问沿允许方向能到达的顶点。要遍历全部非连通图,应从尚未访问的顶点继续开启新的遍历。
邻接表下扫描每个可达顶点及其边,成本与V+E相关;矩阵检查邻居可能达到V平方。起点也必须属于图,不能把缺失起点仍加入结果当正常覆盖。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
在非连通图中,从某个顶点出发,至少有一个顶点无法到达。遍历非连通图需要设置多个起点,以遍历到图 的所有连通分量。 Q:在邻接表中, “与该顶点相连的所有顶点”的顶点顺序是否有要求? 可以是任意顺序。但在实际应用中,可能需
参考来源
- 位置:《Hello 算法--Go版本》第09章《图》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[8732,8842))
- 结论依据:实际非连通问答与BFS/DFS代码共同支持可达范围和多起点。
- 原始内容:在非连通图中,从某个顶点出发,至少有一个顶点无法到达。遍历非连通图需要设置多个起点,以遍历到图 的所有连通分量。 Q:在邻接表中, “与该顶点相连的所有顶点”的顶点顺序是否有要求? 可以是任意顺序。但在实际应用中,可能需