Algorithm for determining strongly connected components, Data Structure & Algorithms

Assignment Help:

Algorithm for determining strongly connected components of a Graph:

Strongly Connected Components (G)

where d[u] = discovery time of the vertex u throughout DFS , f[u] = finishing time of a vertex u throughout DFS, GT    = Transpose of the adjacency matrix

Step 1: Use DFS(G) to calculate f[u] ∀u∈V

Step 2: calculate GT

Step 3: Execute DFS in GT

Step 4: Output the vertices of each of tree within the depth-first forest of Step 3 as a separate strongly connected component.


Related Discussions:- Algorithm for determining strongly connected components

BST has two children, If a node in a BST has two children, then its inorder...

If a node in a BST has two children, then its inorder predecessor has No right child

State the output of avaerage value of numbers, Draw trace table and determi...

Draw trace table and determine output from the subsequent flowchart using below data:  X = 5, -3, 0, -3, 7, 0, 6, -11, -7, 12

Dqueue, how can i delete from deque while deletion is restricted from one e...

how can i delete from deque while deletion is restricted from one end

First class Abstract data type , 3. A function to convert a complex number ...

3. A function to convert a complex number in algebraic form to a complex number in phasor form

Basic organization of computer system, what happen''s in my computer when ...

what happen''s in my computer when i input any passage

Need help with working out. I dont really get it, Suppose there are exactly...

Suppose there are exactly five packet switches (Figure 4) between a sending host and a receiving host connected by a virtual circuit line (shown as dotted line in figure 4). The tr

C++, 7. String manipulation 7.a Write a C Program using following strin...

7. String manipulation 7.a Write a C Program using following string manipulation functions a) strcpy b) strncpy c) strcmp d) strncmp e) strlen f) strcat

Circular linklist, write an algorithm to insert an element at the beginning...

write an algorithm to insert an element at the beginning of a circular linked list?

Number of leaf nodes in a complete binary tree, The number of leaf nodes in...

The number of leaf nodes in a complete binary tree of depth d is    2 d

Program of implementation of stack using arrays, include int choice, st...

include int choice, stack[10], top, element; void menu(); void push(); void pop(); void showelements(); void main() { choice=element=1; top=0; menu()

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