🏷️ 知识点：连通图
课后题 年第 2 题
数据结构
选择题
若从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ ）。
A. 强连通图 B. 连通图 C. 有回路 D. 一棵树
[tag_link]
正确答案：B
结论
该图是连通图。
推导
无向图中，从任意起点 DFS 能访问全部顶点，说明每个顶点都存在到起点的路径，因此任意两点间可达，图连通。
易错点
连通不等于有回路，也不要求是树；强连通是有向图术语。
课后题 年第 6 题
数据结构
选择题
对于一个有 n 个顶点的图：若是连通无向图，其边的个数至少为（ ）；若是强连通有向图，则其边的个数至少为（ ）。
A. n−1，n B. n−1，n(n−1) C. n，n D. n，n(n−1)
[tag_link]
正确答案：A
结论
连通无向图最少有 n−1 条边，强连通有向图最少有 n 条边。
推导
无向图取一棵生成树即可连通 n 个顶点，树恰有 n−1 条边。有向图要让每个顶点可沿方向回到其他顶点，最少可用包含全部顶点的有向环，每个顶点一条出边和一条入边，共 n 条边。
易错点
不要把有向图的“强连通”误当作无向连通；n−1 条有向边至多形成有向路径，不能让所有顶点互相可达。