Graph - strongly connected components

tags:

views:

125

answers:

1

+2 Q:

Graph - strongly connected components

Hello!

Is there any fast way to determine the size of the largest strongly connected component in a graph?

I mean, like, the obvious approach would mean determining every SCC (could be done using two DFS calls, I suppose) and then looping through them and taking the maximum.

I'm pretty sure there has to be some better approach if I only need to have the size of that component and only the largest one, but I can't think of a good solution. Any ideas?

Thanks.

+1 A:

Let me answer your question with another question -
How can you determine which value in a set is the largest without examining all of the values?

Rubys 2010-05-22 22:30:48

Well, sometimes it's possible, e.g. if you have additional information about your set / smth like that. I don't know, maybe determining - maximizing approach would be the only and the best at the same time, but my intuition says that there must be a better way. If you're absolutely sure this can't be done faster, I would trust you :)

HardCoder1986 2010-05-22 22:33:53

I am not sure, this is intuition. There are algorithms to get the components in one DFS if I recall. I am highly doubtful you will find an algorithm that does it in less than a single scan. If you do have some information about the graph, post it, and maybe we can come up with something.

Rubys 2010-05-22 23:19:20

ansaurus

tags:

views:

answers:

Graph - strongly connected components

related questions