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.

PSEUDO CODE ONLY

Explanation / Answer

To finding connected components for an undirected graph,We need to do either Breadth First Search or Depth First Search starting from every unvisited vertex,
and we will get all the strongly connected components. Below are steps based on DFS.

1) Initialize all vertices as not visited.
2) Repaet below steps for every vertex 'v'.
(a) If vertex 'v' is not visited before, call DepthFirstSearchUtil(v)
(b) Print new line character

DepthFirstSearchUtil(v)
1) Mark vertex 'v' as visited.
2) Print vertex 'v'
3) Do following for every adjacent vertex 'u' of the currecnt vertex 'v'.
If vertex 'u' is not visited, then recursively call DepthFirstSearhUtiil(u)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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