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
how we can convert a graph into tree

Range: A Structured Type in Ruby Ruby has a numerous structured types, comprising arrays, hashes, sets, classes, streams, and ranges. In this section we would only discuss rang

Preconditions assertion A precondition is an assertion which should be true at the initiation of an operation. For instance, a square root operation can't accept a negative a

Explain the Scan-Line Algorithm This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of fillin

Merging two sequence using CREW merge

Determine about the Post conditions assertion A  post condition is an assertion which should be true at completion of an operation. For instance, a post condition of the squ

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog

In the array implementation of lists, elements are stored into continuous locations. In order to add an element into the list at the end, we can insert it without any problem. But,

Properties of colour Colour descriptions and specifications generally include three properties: hue; saturation and brightness. Hue associates a colour with some position in th

Easy algorithm for beginner for quicksort with explanation