2
$\begingroup$

I'm trying to solve this question for practising purposes:

"Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, describe a simple quadratic-time algorithm for computing the strong components of a digraph."

The question can be found here . It is question 31.

They give a couple of hints:

"Partial solution: To compute the strong component containing s

  • Find the set of vertices reachable from s
  • Find the set of vertices that can reach s
  • Take the intersection of the two sets

Using this as a subroutine, you can find all strong components in time proportional to t(E+V), where t is the number of strong components."

My thoughts so far:

  1. In order to find the vertices reachable from s, I can to DFS (or BFS, but will stick with DFS) from s. If n is the number of vertices and m is the number of edges this takes O(n+m) time, which seem fine for the purpose. I need to safe every discovered vertex somewhere. Not sure which datastructure works best for this. I will come back to this problem later.
  2. In order to find all vertices that can reach s, I could bild/compute the reverse of the graph and to another DFS from a again. Computing the reverse of the graph should be O(n+m) and the DFS is O(n+m). So in total I have 3*O(n+m) which is just O(n+m). Of course the discovered vertices also need to be safed.
  3. I'm not sure about how to build the intersection. Of course this is going to depend on how I saved the nodes before. So here are my ideas:

Building the intersection:

  • If I saved the nodes in two separate arrays (one for the first DFS and one for the second) I possibly could use a Hash-Table. This should be O(|firstNodes| + |secondNodes|) time. Maybe this would be ok, since O(|firstNodes| + |secondNodes|) is smaller than O(n+m), but it doesn't seem optimal to me and it need extra space.
  • What if I mark the nodes I discoverd with the first DFS. Then I do the second DFS and check if nodes are already marked. If yes, I mark them "special" as belonging the the strong component? I wouldn't have a list afterward that gives me the vertices of the strong component s belongs to but the strong component is still computed? For this approach I would need extra space at every node (in order to mark it).
  • In order to find all strong compoonents in time proportional to t(E+V) I could then to the same procedure on a vertex that is not yet marked as belonging to a strong component -> as long as there are such vertices, therefore t times. I would need to make sure, that every strong component is marked differently (e.g. increaing integers) and that the "I fould you" marks from the DFS are gone after each iteration (but not the marks for the strong components).

What do you think? What have I missed?
Thank you and happy Easter!

$\endgroup$
1
$\begingroup$

Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the multiplicative constant, but not the asymptotic space complexity.

All your ideas are sound. During a BFS, since you need to check if vertices are seen or not, the common way to do it is to use a boolean array. Now for a strongly connected component, you will run two BFS's, and use two boolean arrays. The intersection can be computed by a index-wise AND.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.