知识卡片

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

图遍历只覆盖起点可达部分

理解等级:中级

带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:在邻接表中, “与该顶点相连的所有顶点”的顶点顺序是否有要求? 可以是任意顺序。但在实际应用中,可能需