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

Perform inorder, QUESTION (a) Construct a binary tree for the following...

QUESTION (a) Construct a binary tree for the following numbers assuming that a number greater than the node (starting from the root) goes to the left else it goes to the right.

Lilz, I need to know about data structure and algorithms. can you help me?

I need to know about data structure and algorithms. can you help me?

Multiple Queues in a single dimension array, Implement multiple queues in a...

Implement multiple queues in a single dimensional array. Write algorithms for various queue operations for them.

Explain best - fit method, Best - Fit Method: - This method obtains the sma...

Best - Fit Method: - This method obtains the smallest free block whose size is greater than or equal to get such a block by traversing the whole free list follows.

Linked list, create aset of ten numbers.then you must divide it into two s...

create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

String pattern matching, Document processing is quickly becoming one of the...

Document processing is quickly becoming one of the dominant functions of computers. Computers are utilized to edit, search & transport documents over the Internet, and to display d

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("%

Algorithm for stack using array, write an algorithm for stack using array p...

write an algorithm for stack using array performing the operations as insertion ,deletion , display,isempty,isfull.

Explain thread, Thread By changing the NULL lines in a binary tree to ...

Thread By changing the NULL lines in a binary tree to special links known as threads, it is possible to perform traversal, insertion and deletion without using either a stack

Pseudocodes, how to draw a 5 inch square on the screen using * symbol

how to draw a 5 inch square on the screen using * symbol

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages