Let G be a directed graph. The directed subgraph induced by X V , has X as verti

Question

Let G be a directed graph. The directed subgraph induced by X V , has X as vertice, and has all edges with both endpoint in X. This graph is denoted by G(X). We say that the graoh G(X)) is strongly connected if the distance between any pair of vertices is finite (thus for every x, y there is a finite path from x to y and a finite path from y to x). G(X) is a strongly connected componnent if:

1. G(X) is strongly connected and,

2. For every X so that X X and X 6= X X is not a strongly connected graph. Give an algorithm (and describe a data structure if needed) to find the connected componnents in a graph.

Warning: NO DEPTH SEARCH ALGORITHM, Pseudocode only please!

Explanation / Answer

Input: Graph G is represented using Adjacency list representation.
Output: Connected components of Graph

visited[V] // checks if node is visited or not

1) Do following for every vertex i in visited
   visited[i] = 0
2) Do following for every vertex i in visited
       (a) If visited[i] != 0 call DFSUtil(G, i, visited)
       (b) Print new line character

     
DFSUtil(G, i, visited)
1) visited[i] = 1
2) Print i
3) Do following for every adjacent j of i.
     If visited[j] != 1 then call DFSUtil(G, j, visited)
  
  
  
Complexity:
   Here, each vertex is explored only one time,
   time complexity to explore vertex i is O(1) while of exploring its adjacent vertex is O(degree(i)).
   so, total time complexity over all nodes will be
   O((1+degree(i))) 1<=i<=V
   As degree(i) = 2*E = O(E)
   So, O( (1+degree(i)) ) = O(V+E)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.