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

Search engines - applications of linear and binary search, Search engines e...

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

State about the pre- and post conditions, State about the pre- and post con...

State about the pre- and post conditions Programmers can easily document other pre- and post conditions and class invariants, though, and insert code to check most value preco

Assignment, How do I submit a three page assignment

How do I submit a three page assignment

Using array to execute the queue structure, Q. Using array to execute the q...

Q. Using array to execute the queue structure, write down an algorithm/program to (i) Insert an element in the queue. (ii) Delete an element from the queue.

Quick sort, 24 56 47 35 10 90 82 31

24 56 47 35 10 90 82 31

Data structure for representing numbers, Your first task will be to come up...

Your first task will be to come up with an appropriate data structure for representing numbers of arbitrary potential length in base 215. You will have to deal with large negative

Linear search, Linear search is not the most efficient way to search an ite...

Linear search is not the most efficient way to search an item within a collection of items. Though, it is extremely simple to implement. Furthermore, if the array elements are arra

Write a program for linear search, In the book the following methods are pr...

In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

Implementation of queue, For a queue a physical analogy is a line at bookin...

For a queue a physical analogy is a line at booking counter. At booking counter, customers go to the rear (end) of the line & customers are attended to several services from the fr

State a algorithm that inputs the heights of all 500 student, As part of an...

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou

Write Your Message!

Name

Email id

Message

Verfication Code

User Account

All Pages