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: You are allowed to use only things tought in class. In particular any algorithm that uses the depth first seatch procedure, will not get any points

PSEUDO CODE ONLY

Explanation / Answer

1. For each vertex X of the graph, mark X as unvisited. Let L be empty list.

2. For each vertex X of the graph do Visit (X), where Visit (X) is the recursive subroutine.

If X is unvisited then:

             1. Mark X as visited.

             2. For each out-neighbor v of X, do Visit(v).

            3. Prepend the X to L. Otherwise do nothing.

3. For each element X of L in order, do Assign (X, X) where Assign (X, root) is the recursive subroutine:

If X has not been assigned to a component then:

             1. Assign X as belongs to the component whose root is root.

             2. For each in-neighbor v of X, do Assign (v, root).

Otherwise do nothing.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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