Algorithm for determining strongly connected components, Data Structure & Algorithms

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.

Posted Date: 4/11/2013 5:10:37 AM | Location : United States







Related Discussions:- Algorithm for determining strongly connected components, Assignment Help, Ask Question on Algorithm for determining strongly connected components, Get Answer, Expert's Help, Algorithm for determining strongly connected components Discussions

Write discussion on Algorithm for determining strongly connected components
Your posts are moderated
Related Questions
For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

GIVE TRACE OF BINARY SEARCH ALGORITHM BY USING A SUITABLE EXAMPLE.

Q. Draw  the structures of complete  undirected  graphs  on  one,  two,  three,  four  and  five vertices also prove that the number of edges in an n vertex complete graph is n(n-1

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Question 1 Explain the use of algorithms in computing Question 2 Explain time complexity and space complexity of an algorithm Question 3 Explain how you can analyz

Before programming a problem solution those employees a stack, we have to decide how to represent a stack by using the data structures which exist in our programming language. Stac

how to implement prims algorithm dynamically

Question 1 Describe the following- Well known Sorting Algorithms Divide and Conquer Techniques Question 2 Describe in your own words the different asymptotic func

What is an Algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for getting a needed output for any legitimate input in a finite amoun

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