知识卡片

普通读书笔记卡 · 5654.d.1.f.1

图的连通要先说明方向

理解等级:中级

无向图若任意顶点之间都有路径就是连通;有向图则要区分沿方向彼此可达的强连通与忽略方向后的弱连通。仅从一个特定起点能到达全部顶点,不足以推出有向图强连通。

自环是否允许也取决于图模型,原书无自环的简单图只是其中一种约定。路径、连通性与边权是不同属性,不能由一张示例图替代问题定义。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      根据所有顶点是否连通,可分为「连通图connected graph」和「非连通图 disconnected graph」 ,如图 9‑3 所示。 ‧ 对于连通图,从某个顶点出发,可以到达其余任意顶点。 ‧ 对于非连通图,

    参考来源

    - 位置:《Hello 算法--Go版本》第09章《图》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[24507,24617)) - 结论依据:原文连通分类与简单无向矩阵限制,按方向限定概念。 - 原始内容:根据所有顶点是否连通,可分为「连通图connected graph」和「非连通图 disconnected graph」 ,如图 9‑3 所示。 ‧ 对于连通图,从某个顶点出发,可以到达其余任意顶点。 ‧ 对于非连通图,