什么是强连通图介绍

强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。

强连通图定理及其证明

定理：一个有向图是强连通的，当且仅当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所示。

强连通图强连通图的判断

问题：给一个有向图，判断给图是否是强连通的。

如图3所示，则是一个强连通图。

对于无向图则比较简单，只需要从某一个顶点出发，使用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 *adj;    // 邻接表存储    // 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 = true;    list::iterator i;    for (i = adj.begin(); i != adj.end(); ++i)        if (!visited)            DFSUtil(*i, visited);}// 返回当前图的转置图Graph Graph::getTranspose(){    Graph g(V);    for (int v = 0; v < V; v++)    {        list::iterator i;        for(i = adj.begin(); i != adj.end(); ++i)        {            g.adj.push_back(v);        }    }    return g;}void Graph::addEdge(int v, int w){    adj.push_back(w);}bool Graph::isSC(){    bool visited;    for (int i = 0; i < V; i++)        visited = false;    DFSUtil(0, visited);     //如果有没有被访问的点就返回false    for (int i = 0; i < V; i++)        if (visited == false)             return false;    // 创建当前图的转置图    Graph gr = getTranspose();    for(int i = 0; i < V; i++)        visited = false;    gr.DFSUtil(0, visited);    // 查看是否是所有的点都被访问到    for (int i = 0; i < V; i++)        if (visited == 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;}