The Gateway to Computer Science Excellence
+1 vote
53 views

 

 

 

 

 

 

 

 

 

 

What are the strongly connected components in the above figure ?

in Algorithms by Junior (729 points)
recategorized by | 53 views
+1

strongly connected component  of a directed graph is a maximal strongly connected subgraph

1. svw 

2. qty 

3. xz

4. r

5. u

 

+1

https://gateoverflow.in/3589/gate2006-it-46

you can check the above question for more info how to find strongly connected components using algorithm or intuitively.

1 Answer

+2 votes
Best answer

5 stronglly component.

by Boss (35.7k points)
selected by
+1

@abhishekmehta4u

Using Kosaraju's Algorithm 

1> step find the DFS of  G.and store their finishing time

2>compute Transpose  of G and after that perform DFS of  Transpose  of G and then perform then perform the traversal in such a way that for each node the adjacent nodes should be visited in decreasing order of their finishing time.

And we are comparing the number of connected components in the 2 graphs G and $G^{T}$  right??

0
Yes you are right.
0
how many cross edges and forward edges are present in the above graph??

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,523 answers
195,608 comments
101,286 users