CODEWITHSUNDEEP
algorithmsearchgraphtime-complexitybig-o
Oweys
Oweys

Reputation: 97

Creating an algorithm which checks if a graph is connected or not

So an old exam question was asked like that. I was wondering what that means, because a graph can be directed or not. In a directed graph it should be working like that (I guess):

Create two Arrays: A[], A_inverse[] //both in size N (N nodes exists), both arrays initalized with NULL
Run depth-first search on Graph G
     save in A[] all Nodes which are visted
         If(A.size < |N|) return false
G' = Reverse all edges of G
Run depth-first search on Graph G'  
     save in A_inverse[] all Nodes which are visted
         If(A_inverse.size < |N|) return false
return true

For the time-complexity it is T(N) = 2*DFS + |E| + c. 2*DFS because im calling it twice (once for the G and once for G'). |E| because I need to reverse all Edges. c are all conditions and initializings. Is my algorithm correct?

Upvotes: 0

Views: 437

Answers (1)

Lorenz
Lorenz

Reputation: 1303

In a strongly connected graph G, there must be a path from any node A to any (other) node B.

To start, note that there is a path from B to A in the flipped graph G' if and only if there is a path from A to B in the original graph G.

Assume the DFS starts at some origin node O.

First we show that if G is strongly connected, the algorithm returns true.

  • The first DFS will reach all the nodes, since by assumption there is a path from O to every other node.
  • Again by assumption, there's a path from every node to O. It follows that in G' (where all edges are flipped), there's a path from O to every other node. The second DFS will therefore also reach all nodes, and the algorithm returns true.

Now consider a graph G that is not strongly connected, i.e., there's a pair of nodes (A, B) such that there exists no path from A to B. We have to show that the algorithm returns false. There are two cases to consider:

  • There is no path from A to O. In this case, the flipped graph G' cannot contain a path from O to A. Therefore, the second DFS will not reach A from O and the algorithm returns false.
  • There is a path from A to O: In this case, there cannot be a path from O to B because if there were, our assumption that there is no path from A to B would be wrong. Since there is no path from O to B, the first DFS will not reach B from O and the algorithm returns false.

We proved that the algorithm returns true if G is strongly connected and false otherwise. It is therefore correct.

Upvotes: 1

Related Questions