首页 > 图论 > 连通性问题 > 判断强连通图
2014
09-16

判断强连通图

问题:

给一个有向图,判断给图是否是强连通的。

如下图所示,则是一个强连通图:

connectivity3

 

对于无向图则比较简单,只需要从某一个顶点出发,使用BFS或DFS搜索,如果可以遍历到所有的顶点,则给定的图是连通的。

但这种方法对有向图并不使用,例如 : 1 -> 2 -> 3 -> 4,并不是强连通图。

方法一

可以调用DFS搜索 V 次,V是顶点的个数,就是对每个顶点都做一次DFS搜索,判断是否可达。这样的复杂度为O(V*(V+E))

方法二

可以参考求解连通分量的算法,我们可以在O(V+E) 的时间内找到所有的连通分量,如果连通分量的个数为1,则说明该图是强连通的。

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class Graph
{
    int V;    // 顶点个数
    list<int> *adj;    // 邻接表存储

    // DFS遍历,打印以v为起点的 强连通分量
    void DFSUtil(int v, bool visited[]);
public:
    Graph(int V) { this->V = V;  adj = new list<int>[V];}
    ~Graph() { delete [] adj; }

    void addEdge(int v, int w);

    //判断是是否是强连通图
    bool isSC();

    // 得到当前图的逆置
    Graph getTranspose();
};

void Graph::DFSUtil(int v, bool visited[])
{
    visited[v] = true;
    list<int>::iterator i;
    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<int>::iterator i;
        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 << "Yes\n" : cout << "No\n";
    // 创建图2
    Graph g2(4);
    g2.addEdge(0, 1);
    g2.addEdge(1, 2);
    g2.addEdge(2, 3);
    g2.isSC()? cout << "Yes\n" : cout << "No\n";

    return 0;
}

参考:http://www.geeksforgeeks.org/connectivity-in-a-directed-graph/


  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false