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

Applications of binary trees, In computer programming, Trees are utilized ...

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam

Estimate the probability that the noncritical path , An advertising project...

An advertising project manager developed the network diagram shown below for a new advertising campagign. In addition, the manager gathered the time information for each activity,

Write down the procedure to reverse a singly linked list. , Ans: A pr...

Ans: A procedure to reverse the singly linked list: reverse(struct node **st) { struct node *p, *q, *r; p = *st; q = NULL; while(p != NULL) { r =q;

The various ways in which lc code can be accessed, Problem Your LC code...

Problem Your LC code is stored in a memory location as shown and the variable name is LC LC Memory address Content(LC code)

Algorithm, implement multiple stack in one dimensional array

implement multiple stack in one dimensional array

Complexity classes, Complexity classes All decision problems fall in se...

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

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.

Algorithm for insertion into the circular queue, Algorithm for insertion of...

Algorithm for insertion of any element into the circular queue: Step-1: If "rear" of the queue is pointing at the last position then go to step-2 or else Step-3 Step-2: make

Trees, Have you ever thought about the handling of our files in operating s...

Have you ever thought about the handling of our files in operating system? Why do we contain a hierarchical file system? How do files saved & deleted under hierarchical directories

Several operations on a aa-tree, The following are several operations on a ...

The following are several operations on a AA-tree: 1. Searching: Searching is done using an algorithm which is similar to the search algorithm of a binary search tree. 2. Ins

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages