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

Array, how to define the size of array

how to define the size of array

Determine the algorithm for z-buffer method, Algorithm for Z-Buffer Method ...

Algorithm for Z-Buffer Method (a) Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

Circular queues and implement circular queues using array, Explain what are...

Explain what are circular queues? Write down routines required for inserting and deleting elements from a circular queue implemented using arrays. Circular queue:

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Difference between prism''s and kruskal''s algorithm, Difference among Pris...

Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

Write an algorithm inputs speed of cars using pseudocode, Write an algorith...

Write an algorithm by using pseudocode which: Inputs top speeds of 5000 cars Outputs fastest speed and the slowest speed Outputs average speed of all the 5000 cars

Write a function that performs the integer mod function, Write a function t...

Write a function that performs the integer mod function. Given the previous functions you have implemented already, this one should be a piece of cake. This function will find the

Recursion, differences between direct and indirect recursion

differences between direct and indirect recursion

EM13845162, Do you have a library solution for this problem?

Do you have a library solution for this problem?

Differentiate between nonpersistent and 1-persistent, Differentiate between...

Differentiate between Nonpersistent and 1-persistent Nonpersistent: If the medium is idle, transmit; if the medium is busy, wait an amount of time drawn from a probability dist

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages