知识卡片
图的连通要先说明方向
无向图若任意顶点之间都有路径就是连通;有向图则要区分沿方向彼此可达的强连通与忽略方向后的弱连通。仅从一个特定起点能到达全部顶点,不足以推出有向图强连通。
自环是否允许也取决于图模型,原书无自环的简单图只是其中一种约定。路径、连通性与边权是不同属性,不能由一张示例图替代问题定义。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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 所示。 ‧ 对于连通图,从某个顶点出发,可以到达其余任意顶点。 ‧ 对于非连通图,