Answer in pseudo code Let G be a directed graph. The directed subgraph induced b

Question

Answer in pseudo code

Let G be a directed graph. The directed subgraph induced by X V, has X as vertices, and has all edges with both endpoint in X. This graph is denoted by G(X). We say that the graph 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 component if: 1. G(X) is strongly connected. 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 components in a graph

Explanation / Answer

In short we can use DFS algorithm to find connected components Here is algorithm

1) Initialize all vertices as not visited.

2) Do following for every vertex 'v'.

       (a) If 'v' is not visited before, call myDFS(v)

myDFS(v)

1) Mark 'v' as visited.

2) Print 'v'

3) Do following for every adjacent 'u' of 'v'.

     If 'u' is not visited, then recursively call myDFS(u)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---