强连通图最多有几条边？

有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。

解释如下：强连通图是指一个有向图中任意两点v1、v2间存在v1到v2的路径（path）及v2到v1的路径的图。

最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。

最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。

如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。强连通图具有如下定理：一个有向图G是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。

扩展资料：

如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。

如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾

对于无向图则比较简单，只需要从某一个顶点出发，使用BFS或DFS搜索，如果可以遍历到所有的顶点，则给定的图是连通的。但这种方法对有向图并不适用，例如 ： 1 ->2 ->3 ->4，并不是强连通图。

参考资料来源：百度百科——强连通图

至少要有（N-1）条边。

在数据结构中，N个顶点的连通图至少要有（N-1）条边（也就是树）才能保证图为连通图。

强连通图最多n(n-1)条边，最少n-1条边。

强连通图：任意两个顶点都相互连通的图。

数据结构知识

基本特性：输入，输出，有穷型，确定性可行性。

设计要求：正确性，可读性，健壮性，时间效率高，存储量低。

时间复杂度：随着输入规模n的增加，算法的执行时间的增长率和算法执行次数的增长率保持一致，我们成为算法的渐进时间复杂度，简称为算法的时间复杂度。

大O推导：使用常数1去替代表达式中的常数项；在修改后的表达式中，只保留最高阶次项；如果最高阶次项存在且不为1，去掉最高阶次项的系数。