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

Depth-first search (dfs) , In this respect depth-first search (DFS) is the...

In this respect depth-first search (DFS) is the exact reverse process: whenever it sends a new node, it immediately continues to extend from it. It sends back to previously explore

Convert graph into tree, How can we convert a graph into a tree ? Do we hav...

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Stack and queue, write a algorithsm in c to perform push and pop operation...

write a algorithsm in c to perform push and pop operations stastic implementation using array ?

Bst created in pre- order, Q. Make a BST for the given sequence of numbe...

Q. Make a BST for the given sequence of numbers. 45,32,90,34,68,72,15,24,30,66,11,50,10 Traverse the BST formed in  Pre- order, Inorder and Postorder.

How to write binary search algorithm?, Q. Write down the binary search algo...

Q. Write down the binary search algorithm and trace to search element 91 in following given list: 13          30          62           73         81         88             91

Abstract data type- queue, A significant aspect of Abstract Data Types is t...

A significant aspect of Abstract Data Types is that they explain the properties of a data structure without specifying the details of its implementation. The properties might be im

Two-dimensional array, Two-dimensional array is shown in memory in followin...

Two-dimensional array is shown in memory in following two ways:  1.  Row major representation: To achieve this linear representation, the first row of the array is stored in th

Estimate best first search nodes , Given the following search tree, state t...

Given the following search tree, state the order in which the nodes will be searched for breadth first, depth first, hill climbing and best first search, until a solution is reache

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