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 G^T

Step 3: Execute DFS in G^T

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

State about the simple types - built-in types, State about the Simple types...

State about the Simple types - Built-In Types Values of the carrier set are atomic, that is, they can't be divided into parts. Common illustrations of simple types are inte

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

Create accessors for this data structure, Create a Money data structure tha...

Create a Money data structure that is made up of amount and currency. (a) Write a constructor for this data structure (b) Create accessors for this data structure (c) Writ

LINKED LIST, HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENT...

HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENTS IN LINKED LIST?

Define binary tree, Define Binary Tree A binary tree T is explained as...

Define Binary Tree A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

Interest rate, explain the determination of interest rate in the classical ...

explain the determination of interest rate in the classical system.

#title.structured programming, what do you understand by structured program...

what do you understand by structured programming?explain with eg. top down and bottem up programming technique

B-tree of minimum degree t can maximum pointers in a node, A B-tree of mini...

A B-tree of minimum degree t can maximum pointers in a node T pointers in a node.

Process of channel access, Channel access In first generation systems, ...

Channel access In first generation systems, every cell supports a number of channels. At any given time a channel is allocated to only one user. Second generation systems also

Sort wars - sorting algorithm, If quicksort is so quick, why bother with an...

If quicksort is so quick, why bother with anything else? If bubble sort is so bad, why even mention it? For that matter, why are there so many sorting algorithms? Your mission (sho

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages