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 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.


Related Discussions:- Algorithm for determining strongly connected components

Write an algorithm for binary search., Write an algorithm for binary search...

Write an algorithm for binary search. Algorithm for Binary Search 1.  if (low> high) 2.  return (-1) 3.  Mid = (low + high)/2 4.  if ( X = = a[mid]) 5.  return (mid); 6.

Heights of 500 students `Algorithms`, Write an algorithm, using a flowchart...

Write an algorithm, using a flowchart, which inputs the heights of all 500 students and outputs the height of the tallest person and the shortest p erson in the school.

State about the pseudocode, State the Introduction to pseudocode No spe...

State the Introduction to pseudocode No specific programming language is referred to; development of algorithms by using pseudocode uses generic descriptions of branching, loop

Define a b-tree, Define a B-Tree Justas AVL trees are balanced binary s...

Define a B-Tree Justas AVL trees are balanced binary search trees, B-trees are balanced M-way search trees. A B-Tree of order M is either the empty tree or it is an M-way searc

Stack, Explain the array and linked list implementation of stack

Explain the array and linked list implementation of stack

Relationship between shortest path distances of modified, a) Given a digrap...

a) Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same. Do this by usin

Sorting algorithm, Sorting Algorithm A sorting algorithm is an algorit...

Sorting Algorithm A sorting algorithm is an algorithm which puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Eff

Tree, application of threaded binary treee

application of threaded binary treee

Graph & optimal scheduling, You are given an undirected graph G = (V, E) in...

You are given an undirected graph G = (V, E) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight of either {1,2,...,W}, where W

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd