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

Pseudocodes, how to write a pseudo code using Kramer''s rule

how to write a pseudo code using Kramer''s rule

Stack, how we will make projects on stack in c?

how we will make projects on stack in c?

Circularly linked lists implementation, CIRCULARLY LINKED LISTS IMPLEMENTAT...

CIRCULARLY LINKED LISTS IMPLEMENTATION A linked list wherein the last element points to the first element is called as CIRCULAR linked list. The chains do not specified first o

Sequential search of a list is preferred over binary search, What are the c...

What are the conditions under which sequential search of a list is preferred over binary search? Sequential Search is a preferred over binary search when the list is unordered

Determine the comparison of gouraud and phong shading, Comparison of Gourau...

Comparison of Gouraud and Phong Shading Phong shading requires more calculations, but produces better results for specular reflection than Gouraud shading in the form of more r

Define big oh notation, Big oh notation (O) : The upper bound for the funct...

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real

A binary tree of depth "d" is an almost complete binary tree, A binary tree...

A binary tree of depth "d" is an almost complete binary tree if  A) Every leaf in the tree is either at level "d" or at level "d-1"  B)  For any node "n" in the tree with a

Determine the precondition of a binary search, Determine the precondition o...

Determine the precondition of a binary search For instance, precondition of a binary search is that array searched is sorted however checking this precondition is so expensive

Linked list implementation of a dequeue, Double ended queues are implemente...

Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

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