Find strongly connected components - dfs, Data Structure & Algorithms

Assignment Help:

A striking application of DFS is determine a strongly connected component of a graph.

Definition: For graph G = (V, E) , where V refer to the set of vertices and E refer to the set of edges, we described a strongly connected components as follows:

U refers to a sub set of V such that u, v linked to U such that, there is a path from u to v and v to u. That is, all of the pairs of vertices are reachable from each other.

In this section we shall use another concept called transpose of any graph. Given a directed graph G a transpose of G is described as GT. GT is described as a graph along with the same number of vertices & edges with only the direction of the edges being reversed. GT is attained by transposing the adjacency matrix of the directed graph G.

The algorithm for determining these strongly connected components uses the transpose of G, GT.

G = ( V, E ), GT = ( V, ET ), where ET = {  ( u, v ): ( v, u ) belongs to E }

1294_FINDING STRONGLY CONNECTED COMPONENTS.png

Figure: Transpose and strongly connected components of digraph of above Figure

Figure illustrates a directed graph along with sequence in DFS (first number of the vertex illustrates the discovery time and second number illustrates the finishing time of the vertex during DFS. Figure illustrates the transpose of the graph in Figure whose edges are reversed. The strongly connected components are illustrated in zig-zag circle in Figure.

1150_FINDING STRONGLY CONNECTED COMPONENTS1.png

To determine strongly connected component we begun with a vertex with the highest finishing time and begun DFS in the graph GT and then in decreasing order of finishing time. DFS along vertex with finishing time 14 as root determine a strongly connected component. Alike, vertices along finishing times 8 and then 5, while chosen as source vertices also lead to strongly connected components.


Related Discussions:- Find strongly connected components - dfs

Sorting, Define Hashing. Store the following values in a hash table of tabl...

Define Hashing. Store the following values in a hash table of table size 11 using division method: 25, 42, 96, 101, 102, 162, and 197. In case of collision, use other hash functio

Determine the space complexity of euclid algorithm, 1)      Why space compl...

1)      Why space complexity is comparatively more critical than time complexity? 2)      Determine the space complexity of Euclid Algorithm?

Binary search, An unsorted array is searched through linear search that sca...

An unsorted array is searched through linear search that scans the array elements one by one until the wanted element is found. The cause for sorting an array is that we search

Flow chart, that will determine the volume of the sphere or the volume of c...

that will determine the volume of the sphere or the volume of cone or volume of pyramid depending on the choice of the user

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

What is Oscillating Sort?, For the Oscillating sort to be applied, it is ne...

For the Oscillating sort to be applied, it is necessary for the tapes to be readable in both directions and able to be quickly reversed. The oscillating sort is superior to the po

Exact analysis of insertion sort, Exact analysis of insertion sort: Let...

Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s

Comparisions and assignments in worst case, Q. Calculate that how many key ...

Q. Calculate that how many key comparisons and assignments an insertion sort makes in its worst case?        Ans: The worst case performance occurs in insertion

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ...

Algorithm for Z-Buffer Method (a)  Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd