定理及其证明
有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。如图1所示就是一个强连通图。
定理：一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个节点一次。
证明：
（1）充分性：如果G中有一个回路，它至少包含每个节点一次，则G中任两个节点都是互相可达的，故G是强连通图。
（2）必要性：如果有向图是强连通的，则任两个节点都是相互可达。故必可做一回路经过图中所有各点。若不然则必有一回路不包含某一结点v，并且v与回路上的个节点就不是相互可达，与强连通条件矛盾。
强连通图的边问题
有n个顶点的强连通图最多有n（n-1）条边，最少有n条边。
（1）最多的情况：即n个顶点中两两相连，若不计方向，n个点两两相连有n（n-1）/2条边，而由于强连通图是有向图，故每条边有两个方向，n（n-1）/2×2=n（n-1），故有n个顶点的强连通图最多有n（n-1）条边。
（2）最少的情况：即n个顶点围成一个圈，且圈上各边方向一致，即均为顺时针或者逆时针，此时有n条边。
下面举例说明：如图1所示，设ABCD四个点构成强连通图，则：
（1）边数最多有4×3=12条，如图1所示。
（2）边数最少有4条，如图2所示。
强连通图的判断
问题：给一个有向图，判断给图是否是强连通的。
则是一个强连通图。
对于无向图则比较简单，只需要从某一个顶点出发，使用BFS或DFS搜索，如果可以遍历到所有的顶点，则给定的图是连通的。
但这种方法对有向图并不适用，例如 ： 1 -> 2 -> 3 -> 4，并不是强连通图。
方法一
可以调用DFS搜索 V 次，V是顶点的个数，就是对每个顶点都做一次DFS搜索，判断是否可达。这样的复杂度为O(V*(V+E))。
方法二
可以参考求解连通分量的算法Tarjan算法，我们可以在O(V+E) 的时间内找到所有的连通分量，如果连通分量的个数为1，则说明该图是强连通的。
#include
#include
#include
using namespace std;
class Graph
{
int V; // 顶点个数
list
// DFS遍历，打印以v为起点的 强连通分量
void DFSUtil(int v, bool visited[]);
public:
Graph(int V) { this->V = V; adj = new list
~Graph() { delete [] adj; }
void addEdge(int v, int w);
//判断是是否是强连通图
bool isSC();
// 得到当前图的逆置
Graph getTranspose();
};
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
list
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// 返回当前图的转置图
Graph Graph::getTranspose()
{
Graph g(V);
for (int v = 0; v < V; v++)
{
list
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
g.adj[*i].push_back(v);
}
}
return g;
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
bool Graph::isSC()
{
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
DFSUtil(0, visited);
//如果有没有被访问的点就返回false
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
// 创建当前图的转置图
Graph gr = getTranspose();
for(int i = 0; i < V; i++)
visited[i] = false;
gr.DFSUtil(0, visited);
// 查看是否是所有的点都被访问到
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
// 测试
int main()
{
// 创建图1
Graph g1(5);
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
g1.addEdge(3, 0);
g1.addEdge(2, 4);
g1.addEdge(4, 2);
g1.isSC()? cout << "Yesn" : cout << "Non";
// 创建图2
Graph g2(4);
g2.addEdge(0, 1);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
g2.isSC()? cout << "Yesn" : cout << "Non";
return 0;
}
