← 全部问题如何判断一个有向图是否是强连通的？
要判断一个有向图是否是强连通的，必须验证每一对顶点是否相互可达。如果发现哪怕一对顶点中一个无法到达另一个，该图就不是强连通的。
理解与推导
- 选择一对顶点 u 和 v。
- 检查是否存在从 u 到 v 的有向路径。
- 检查是否存在从 v 到 u 的有向路径。
- 对所有顶点对重复此过程。
- 如果任何一对未能通过相互可达性测试，则图不是强连通的。
- 如果所有对都通过，则图是强连通的。
例子
在图 1 中，A 可以到达 D，但 D 无法到达 A。因此，图 1 不是强连通的。在图 2 中，B 可以到达 A，但 A 无法到达 B，所以它也不是强连通的。
容易误解的地方
- 只检查一个方向的可达性。
- 假设如果图中有环，它就自动是强连通的。
相关问题
认识概念↗ 具有 n 个顶点的强连通有向图的最大边数是 n(n−1)。这对应于一个完全有向图，其中每一对不同顶点都有双向的边。
适用条件：图是有向图。；图是强连通的。；图有 n 个顶点。
认识概念↗ 具有 n 个顶点的无向连通图至少有 n-1 条边。当图形成树结构时，达到这个最小值。
适用条件：图是无向图。；图是连通的。；图有 n 个顶点。
认识概念↗ 具有 n 个顶点的无向简单图的最大边数是 n(n−1)/2。当图是完全图时，达到这个最大值。
适用条件：图是无向图。；图是简单图（没有自环或同一对顶点之间的多重边）。；图有 n 个顶点。
连通图是指任意两个顶点之间都存在路径的无向图。如果有一对顶点之间没有路径相连，则该图称为非连通图。
适用条件：图是无向图。；判断标准是任意两个顶点之间是否存在路径。
认识概念↗ 具有 n 个顶点的强连通有向图至少有 n 条边。当图形成一个单一的有向环时，达到这个最小值。
适用条件：图是有向图。；图是强连通的。；图有 n 个顶点。
答案依据视频资料生成并经过独立核验。若有疑问，请核对原视频或联系原作者。