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

Designed to manage the booking, Beauty Salon is a system to be designed to...

Beauty Salon is a system to be designed to manage the booking and the payment of a single beauty parlour. Beauty Therapists: A beauty parlour has a number of staff members mo

A bst is traversed in which order recursively, A  BST is traversed in the ...

A  BST is traversed in the following order recursively: Right, root, left e output sequence will be in In Descending order

Enumerate the types in ruby, Enumerate the Types in Ruby Ruby is a pure...

Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

Find error for curious number, #include #include int sumFact(int numb);...

#include #include int sumFact(int numb); int calculateFactorial(int digit); main() { int numb, sumfact; do{ printf ("Enter a number 1 to 9999\n"); scanf("%

Whether the infix expression has balanced parenthesis or not, Using stacks,...

Using stacks, write an algorithm to determine whether the infix expression has balanced parenthesis or not Algorithm parseparens This algorithm reads a source program and

Queue be represented by circular linked list, Q. Can a Queue be represented...

Q. Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example. A n s . Yes a

Depth first search and breadth first search, Q. Illustrate the result of ru...

Q. Illustrate the result of running BFS and DFS on the directed graph given below using vertex 3 as source.  Show the status of the data structure used at each and every stage.

Question, A binary search tree is used to locate the number 43. Which of th...

A binary search tree is used to locate the number 43. Which of the following probe sequences are possible and which are not? Explain. (a) 61 52 14 17 40 43 (b) 2 3 50 40 60 43 (c)

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