定理：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。
证明：
（1）充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。
（2）必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。
强连通图的边问题图1
有n个顶点的强连通图最多有条边，最少有n条边。（1）最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有条边，而由于强连通图是有向图，故每条边有两个方向，，故有n个顶点的强连通图最多有条边。
（2）最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。
下面举例说明：如图1所示，设ABCD四个点构成强连通图，则：
（1）边数最多有条，如图1所示。
图2
（2）边数最少有4条，如图2所示。强连通图的判断问题：给一个有向图，判断给图是否是强连通的。
如图3所示，则是一个强连通图。
对于无向图则比较简单，只需要从某一个顶点出发，使用BFS或DFS搜索，如果可以遍历到所有的顶点，则给定的图是连通的。
但这种方法对有向图并不适用，例如：，并不是强连通图。方法一
可以调用DFS搜索 V 次，V是顶点的个数，就是对每个顶点都做一次DFS搜索，判断是否可达。这样的复杂度为。方法二
可以参考求解连通分量的算法Tarjan算法，我们可以在 的时间内找到所有的连通分量，如果连通分量的个数为1，则说明该图是强连通的。
