Connectivity in a directed graph - GeeksforGeeks

Connectivity in a directed graph - GeeksforGeeks
Given a directed graph, find out whether the graph is strongly connected or not. A directed graph is strongly connected if there is a path between any two pair of vertices.
It is easy for undirected graph, we can just do a BFS and DFS starting from any vertex. If BFS or DFS visits all vertices, then the given undirected graph is connected. This approach won’t work for a directed graph.

We can also do DFS V times starting from every vertex. If any DFS, doesn’t visit all vertices, then graph is not strongly connected. This algorithm takes O(V*(V+E)) time which can be same as transitive closure for a dense graph.

A better idea can be Strongly Connected Components (SCC) algorithm. We can find all SCCs in O(V+E) time. If number of SCCs is one, then graph is strongly connected. The algorithm for SCC does extra work as it finds all SCCs.

Following is Kosaraju’s DFS based simple algorithm that does two DFS traversals of graph:
1) Initialize all vertices as not visited.

2) Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn’t visit all vertices, then return false.

3) Reverse all arcs (or find transpose or reverse of graph)

4) Mark all vertices as not-visited in reversed graph.

5) Do a DFS traversal of reversed graph starting from same vertex v (Same as step 2). If DFS traversal doesn’t visit all vertices, then return false. Otherwise return true.

The idea is, if every node can be reached from a vertex v, and every node can reach v, then the graph is strongly connected. In step 2, we check if all vertices are reachable from v. In step 4, we check if all vertices can reach v (In reversed graph, if all vertices are reachable from v, then all vertices can reach v in original graph).

http://www.fgdsb.com/2015/01/03/connectivity-in-a-directed-graph/

一个更好的办法是强连通分量算法Strongly Connected Components (SCC) algorithm。我们可以用O(V+E)时间复杂度找出一个图中所有的SCC。如果SCC只有一个，那么这个图就是强连通图。

用Kosaraju算法，两个pass做DFS：

1. 开一个visited数组，标记所有点为unvisited.
2. 从任意顶点V走一次DFS，如果没有访问到所有顶点则返回false。
3. 将所有边reverse。
4. 把reverse后的图的所有定点重新标记为unvisited。
5. 继续对新图走一次DFS，起点跟2中的顶点V。如果DFS没有访问到所有点则返回false，否则返回true。

算法的整体思路是，如果一个点可以访问到其他所有点，同时其他所有点可以访问到这个点，那么这个图就是强连通图。时间复杂度为O(V+E)

    private int V;   // No. of vertices

    private LinkedList<Integer> adj[]; //Adjacency List

 

    //Constructor

    Graph(int v)

    {

        V = v;

        adj = new LinkedList[v];

        for (int i=0; i<v; ++i)

            adj[i] = new LinkedList();

    }

 

    //Function to add an edge into the graph

    void addEdge(int v,int w) {  adj[v].add(w); }

 

    // A recursive function to print DFS starting from v

    void DFSUtil(int v,Boolean visited[])

    {

        // Mark the current node as visited and print it

        visited[v] = true;

 

        int n;

 

        // Recur for all the vertices adjacent to this vertex

        Iterator<Integer> i = adj[v].iterator();

        while (i.hasNext())

        {

            n = i.next();

            if (!visited[n])

                DFSUtil(n,visited);

        }

    }

 

    // Function that returns transpose of this graph

    Graph getTranspose()

    {

        Graph g = new Graph(V);

        for (int v = 0; v < V; v++)

        {

            // Recur for all the vertices adjacent to this vertex

            Iterator<Integer> i = adj[v].listIterator();

            while (i.hasNext())

                g.adj[i.next()].add(v);

        }

        return g;

    }

 

    // The main function that returns true if graph is strongly

    // connected

    Boolean isSC()

    {

        // Step 1: Mark all the vertices as not visited

        // (For first DFS)

        Boolean visited[] = new Boolean[V];

        for (int i = 0; i < V; i++)

            visited[i] = false;

 

        // Step 2: Do DFS traversal starting from first vertex.

        DFSUtil(0, visited);

 

        // If DFS traversal doesn't visit all vertices, then

        // return false.

        for (int i = 0; i < V; i++)

            if (visited[i] == false)

                return false;

 

        // Step 3: Create a reversed graph

        Graph gr = getTranspose();

 

        // Step 4: Mark all the vertices as not visited (For

        // second DFS)

        for (int i = 0; i < V; i++)

            visited[i] = false;

 

        // Step 5: Do DFS for reversed graph starting from

        // first vertex. Staring Vertex must be same starting

        // point of first DFS

        gr.DFSUtil(0, visited);

 

        // If all vertices are not visited in second DFS, then

        // return false

        for (int i = 0; i < V; i++)

            if (visited[i] == false)

                return false;

 

        return true;

    }

Java Code: https://github.com/ajitkoti/Algorithms/blob/master/src/com/interview/algorithms/graph/ConnectivityInADirectedGraph.java

https://reeestart.wordpress.com/2016/06/09/graph-strongly-connected-component/

What is Strongly Connected Component?
A Graph is Strongly Connected Component if there is a PATH (not edge) between every pair of nodes.

[Undirected Graph]
For undirected graph, start at any vertex and do a DFS traversal, if every other vertices are reachable, then the graph is strongly connected.

[Directed Graph]
For directed graph, things become a little bit complicated. Because whether all other vertices are reachable is determined by the starting point.

For example, in the following example, which is not a strongly connected component. If we start from vertex 2, then every other vertices are reachable through one DFS traversal, but if we start at 4, we can not reach all other vertices.

[Algorithm] – Directed Graph
So a single DFS is not enough to check whether a Directed Graph is strongly connected.

Pseudo-Code
1. DFS from v, if any vertex is not reachable, return false
2. Reversed all arcs in the graph
3. DFS from the same v, if any vertex is not reachable, return false

Read full article from Connectivity in a directed graph - GeeksforGeeks