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

Aa-trees, Red-Black trees have introduced a new property in the binary sear...

Red-Black trees have introduced a new property in the binary search tree that means an extra property of color (red, black). However, as these trees grow, in their operations such

Present the algorithm of binary search. , B i n a ry Search Alg...

B i n a ry Search Algorithm is given as follows 1. if (low > high) 2.     return (-1) 3. mid = (low +high)/2; 4. if ( X = = a [mid]) 5.      return (mid); 6.

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

Inorder traversal, Inorder traversal: The left sub tree is visited, then t...

Inorder traversal: The left sub tree is visited, then the node and then right sub-tree. Algorithm for inorder traversal is following: traverse left sub-tree visit node

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

Convert a binary tree into its mirror image by traversing it, One can chang...

One can change a binary tree into its mirror image by traversing it in Postorder is the only proecess whcih can convert binary tree into its mirror image.

Searching, Searching is the procedure of looking for something: Finding one...

Searching is the procedure of looking for something: Finding one piece of data that has been stored inside a whole group of data. It is frequently the most time-consuming part of m

Deletion of a node from an avl tree, For AVL trees the deletion algorithm i...

For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

Representation of a polynomial with a singly linked list, List areutilized ...

List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

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